<HTML>
<HEAD>
<TITLE>TR : [math-fun] Sum of last ten digits</TITLE>
</HEAD>
<BODY>
<FONT FACE="Courier, Courier New"><SPAN STYLE='font-size:18.0px'><BR>
<BR>
Received from Mike Beeler <BR>
- a correction to his finding concerning the loop s=7. The new conclusion is no less interessant than the preceding (erroneous) one. <BR>
- new results about loops s=7. <BR>
<BR>
It's time to stop this branch of discussion on seqfan, and pursue it separately; any one is welcome of course.<BR>
<BR>
Have a nice week end, all.<BR>
<BR>
A.<BR>
<BR>
<BR>
<BR>
------ Message transféré<BR>
De : Michael D Beeler <mbeeler@csc.com><BR>
Date : Wed, 28 Dec 2005 10:43:42 -0500<BR>
À : Alexandre Wajnberg <alexandre.wajnberg@skynet.be><BR>
Cc : Michele Dondi <blazar@pcteor1.mi.infn.it>, Eric ANGELINI <keynews.tv@skynet.be>, Léon Brenig <lbrenig@ulb.ac.be>, Seqfan <seqfan@ext.jussieu.fr>, Michael D Beeler <mbeeler@csc.com><BR>
Objet : RE: [math-fun] Sum of last ten digits<BR>
<BR>
<BR>
<FONT COLOR="#800000">Alexandre and others,<BR>
<BR>
There is an error in what I reported. My sincere apologies.<BR>
<BR>
For next term = sum of last 7 digits in decimal, there are THREE loops, not<BR>
two.<BR>
<BR>
There is the zero-loop, 0000000.<BR>
<BR>
There is the loop of 461 terms, whose numerically smallest term is 0121410.<BR>
9,999,270 states lead into this loop or are already in it.<BR>
<BR>
There is also a loop of 1 term, 7373737.<BR>
All states of the form (a)(10-a)(b)(10-b)(c)(10-c)(7), for a, b, c in 1..9,<BR>
lead into this loop or are already in it.<BR>
That is 9*9*9 = 729 states.<BR>
<BR>
1 + 9,999,270 + 729 = 10,000,000 as it should.<BR>
<BR>
I don't know how I missed the 7373737 loop. I will have to re-check my<BR>
programs.<BR>
<BR>
-- Mike<BR>
</FONT><BR>
------ Fin du message transféré<BR>
<BR>
<BR>
<FONT COLOR="#800000">(...)<BR>
I have some more results about the trees of states feeding into the 461<BR>
loop. If we say the states in the loop are at "distance 0" from the loop,<BR>
then immediate predecessors of states in the loop (but not in the loop<BR>
themself) are at "distance 1" from the loop. There are 2512 of those.<BR>
States at "distance 2" feed into those at distance 1, and there are 15984<BR>
at distance 2. The number of states per distance is:<BR>
<BR>
distance 0 -- 461 states<BR>
distance 1 -- 2512 states<BR>
distance 2 -- 15984 states<BR>
distance 3 -- 103257 states (the largest number of states for any distance)<BR>
distance 4 -- 43216 states<BR>
distance 5 -- 53652 states<BR>
distance 6 -- 66920 states<BR>
distance 7 -- 27884 states<BR>
distance 8 -- 23984 states<BR>
distance 9 -- 18184 states<BR>
distance 10 -- 12977 states<BR>
... (slow decrease, and occasional small increase, in number of states for<BR>
each larger distance)<BR>
distance 1160 -- 540 states<BR>
distance 1161 -- 540 states<BR>
distance 1162 -- 486 states<BR>
distance 1163 -- 280 states<BR>
distance 1164 -- 360 states<BR>
distance >1164 -- 0 states<BR>
<BR>
The 360 states at maximum distance are of two forms:<BR>
(2d-sum=17) (2d-sum=9) (2d-sum=15) 8<BR>
(2d-sum=6) (2d-sum=9) (2d-sum=15) 9<BR>
where "2d-sum=N" means two digits whose sum is N.<BR>
For example, 8909698 is an example of the first form.<BR>
There are 80 states of the first form, and 280 of the second<BR>
(that is easy to show by hand). In just 4 steps, all these 360 states<BR>
become 9454539,<BR>
so from there on they all follow the same path into the loop.<BR>
<BR>
Of the 461 states in the loop, the number of predecessors at distance 1 is:<BR>
4 states have 0 predecessors<BR>
24 states have 1 predecessor<BR>
49 states have 2 predecessors<BR>
47 states have 3 predecessors<BR>
41 states have 4 predecessors<BR>
45 states have 5 predecessors<BR>
49 states have 6 predecessors<BR>
85 states have 7 predecessors<BR>
82 states have 8 predecessors<BR>
35 states have 9 predecessors<BR>
<BR>
The 4 states with no predecessors at distance 1 are:<BR>
1214109 2012139 2120128 2020127<BR>
<BR>
The states that fall into the "7373737" loop can be described using the<BR>
above notation as:<BR>
(2d-sum=10) (2d-sum=10) (2d-sum=10) 7<BR>
<BR>
There are large groups of equivalent states, related by the 2-digit sum<BR>
concept. If the sum of the 7 digits is a two-digit number, then the<BR>
original first two digits will move out when the sum is appended to form<BR>
the next state. Because both digits move out, the next state does not<BR>
depend on what those two digits are, only what their sum is. This is a<BR>
major theme in this sum-of-last-digits process. Because there are large<BR>
groups of equivalent states, based on the sum of the first two digits, or<BR>
second two digits, or third two digits, the state space is not really as<BR>
big as it seems.<BR>
<BR>
The "7373737" loop made me think of looking for similar loops with s=9<BR>
(next term is sum of last 9 digits, in decimal). I quickly found three<BR>
similar loops:<BR>
(2d-sum=5) (2d-sum=5) (2d-sum=5) (2d-sum=5) 3 --> loop is 3 2 3 2 3 2 3 2 3<BR>
(2d-sum=10) (2d-sum=10) (2d-sum=10) (2d-sum=10) 6 --> loop is 6 4 6 4 6 4 6<BR>
4 6<BR>
(2d-sum=15) (2d-sum=15) (2d-sum=15) (2d-sum=15) 9 --> loop is 9 6 9 6 9 6 9<BR>
6 9<BR>
Each of these loops has a loop length of 1, but a fairly large number of<BR>
states feed into each loop.<BR>
<BR>
The above three loops tell us something new about the case of s=9,<BR>
radix=decimal. Earlier I wrote to you about results for starting with<BR>
various digits. In this case, the starting states 000000001, 000000002,<BR>
000000003, ... 000000009 all fall into loop(s) of length 12203. This is<BR>
similar to the nine starting states with s=7 falling into the loop of<BR>
length 461. And, just as there is another loop (7373737) for s=7, there<BR>
also are at least the three loops above for s=9. This is a simple disproof<BR>
of my thought that maybe all s=9 states (except all zeros) fall into one<BR>
loop.<BR>
<BR>
One of the people in your emails suggested looking at the predecessors of a<BR>
state. That is a very powerful technique. It made most of the new results<BR>
I mention above possible. It is very easy to analyze, for any s (number of<BR>
digits to sum) and b (base, radix), how to test whether predecessors exist,<BR>
and if so, what they are. I break it into different cases, depending on<BR>
the number of digits in the predecessor: a predecessor that is one digit;<BR>
predecessor(s) that are 2 digits; etc.<BR>
<BR>
I will be away for a few days. I wish you a Happy New Year for 2006!<BR>
<BR>
-- Mike<BR>
<BR>
</FONT>------ Fin du message transféré<BR>
<BR>
<BR>
</SPAN></FONT>
</BODY>
</HTML>