TR : [math-fun] Sum of last ten digits

[Alexandre Wajnberg]

Received from Mike Beeler
- a correction to his finding concerning the loop s=7. The new conclusion is
no less interessant than the preceding (erroneous) one.
- new results about loops s=7.

It's time to stop this branch of discussion on seqfan, and pursue it
separately; any one is welcome of course.

Have a nice week end, all.

A.



------ Message transféré
De : Michael D Beeler <mbeeler at csc.com>
Date : Wed, 28 Dec 2005 10:43:42 -0500
À : Alexandre Wajnberg <alexandre.wajnberg at skynet.be>
Cc : Michele Dondi <blazar at pcteor1.mi.infn.it>, Eric ANGELINI
<keynews.tv at skynet.be>, Léon Brenig <lbrenig at ulb.ac.be>, Seqfan
<seqfan at ext.jussieu.fr>, Michael D Beeler <mbeeler at csc.com>
Objet : RE: [math-fun] Sum of last ten digits


Alexandre and others,

There is an error in what I reported.  My sincere apologies.

For next term = sum of last 7 digits in decimal, there are THREE loops, not
two.

There is the zero-loop, 0000000.

There is the loop of 461 terms, whose numerically smallest term is 0121410.
9,999,270 states lead into this loop or are already in it.

There is also a loop of 1 term, 7373737.
All states of the form (a)(10-a)(b)(10-b)(c)(10-c)(7), for a, b, c in 1..9,
lead into this loop or are already in it.
That is 9*9*9 = 729 states.

1 + 9,999,270 + 729 = 10,000,000 as it should.

I don't know how I missed the 7373737 loop.  I will have to re-check my
programs.

-- Mike

------ Fin du message transféré


(...)
I have some more results about the trees of states feeding into the 461
loop.  If we say the states in the loop are at "distance 0" from the loop,
then immediate predecessors of states in the loop (but not in the loop
themself) are at "distance 1" from the loop.  There are 2512 of those.
States at "distance 2" feed into those at distance 1, and there are 15984
at distance 2.  The number of states per distance is:

distance 0 -- 461 states
distance 1 -- 2512 states
distance 2 -- 15984 states
distance 3 -- 103257 states (the largest number of states for any distance)
distance 4 -- 43216 states
distance 5 -- 53652 states
distance 6 -- 66920 states
distance 7 -- 27884 states
distance 8 -- 23984 states
distance 9 -- 18184 states
distance 10 -- 12977 states
... (slow decrease, and occasional small increase, in number of states for
each larger distance)
distance 1160 -- 540 states
distance 1161 -- 540 states
distance 1162 -- 486 states
distance 1163 -- 280 states
distance 1164 -- 360 states
distance >1164 -- 0 states

The 360 states at maximum distance are of two forms:
(2d-sum=17) (2d-sum=9) (2d-sum=15) 8
(2d-sum=6) (2d-sum=9) (2d-sum=15) 9
where "2d-sum=N" means two digits whose sum is N.
For example, 8909698 is an example of the first form.
There are 80 states of the first form, and 280 of the second
(that is easy to show by hand).  In just 4 steps, all these 360 states
become 9454539,
so from there on they all follow the same path into the loop.

Of the 461 states in the loop, the number of predecessors at distance 1 is:
 4 states have 0 predecessors
24 states have 1 predecessor
49 states have 2 predecessors
47 states have 3 predecessors
41 states have 4 predecessors
45 states have 5 predecessors
49 states have 6 predecessors
85 states have 7 predecessors
82 states have 8 predecessors
35 states have 9 predecessors

The 4 states with no predecessors at distance 1 are:
1214109   2012139   2120128   2020127

The states that fall into the "7373737" loop can be described using the
above notation as:
(2d-sum=10) (2d-sum=10) (2d-sum=10) 7

There are large groups of equivalent states, related by the 2-digit sum
concept.  If the sum of the 7 digits is a two-digit number, then the
original first two digits will move out when the sum is appended to form
the next state.  Because both digits move out, the next state does not
depend on what those two digits are, only what their sum is.  This is a
major theme in this sum-of-last-digits process.  Because there are large
groups of equivalent states, based on the sum of the first two digits, or
second two digits, or third two digits, the state space is not really as
big as it seems.

The "7373737" loop made me think of looking for similar loops with s=9
(next term is sum of last 9 digits, in decimal).  I quickly found three
similar loops:
(2d-sum=5) (2d-sum=5) (2d-sum=5) (2d-sum=5) 3 --> loop is 3 2 3 2 3 2 3 2 3
(2d-sum=10) (2d-sum=10) (2d-sum=10) (2d-sum=10) 6 --> loop is 6 4 6 4 6 4 6
4 6
(2d-sum=15) (2d-sum=15) (2d-sum=15) (2d-sum=15) 9 --> loop is 9 6 9 6 9 6 9
6 9
Each of these loops has a loop length of 1, but a fairly large number of
states feed into each loop.

The above three loops tell us something new about the case of s=9,
radix=decimal.  Earlier I wrote to you about results for starting with
various digits.  In this case, the starting states 000000001, 000000002,
000000003, ... 000000009 all fall into loop(s) of length 12203.  This is
similar to the nine starting states with s=7 falling into the loop of
length 461.  And, just as there is another loop (7373737) for s=7, there
also are at least the three loops above for s=9.  This is a simple disproof
of my thought that maybe all s=9 states (except all zeros) fall into one
loop.

One of the people in your emails suggested looking at the predecessors of a
state.  That is a very powerful technique.  It made most of the new results
I mention above possible.  It is very easy to analyze, for any s (number of
digits to sum) and b (base, radix), how to test whether predecessors exist,
and if so, what they are.  I break it into different cases, depending on
the number of digits in the predecessor: a predecessor that is one digit;
predecessor(s) that are 2 digits; etc.

I will be away for a few days.  I wish you a Happy New Year for 2006!

-- Mike

------ Fin du message transféré



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20051229/89010bdb/attachment.htm>