[math-fun] Sum of last ten digits

[Alexandre Wajnberg]

Graeme, Hans, Neil, ...

About "Sum of last x digits" and loops, findings by Michaël Beeler.

Alexandre

----------------------------

Michael Beeler wrote:
> On a related topic, I was puzzled by my results to your previous question
> about starting with zeros followed by 2, 3, 4... to 9.  In particular, for
> the cases s=7, s=9, s=11 and s=13, the loop length does not change for
> using the nine digits 1 through 9.  I looked more carefully at the smallest
> of these, s=7.  I changed my program to run faster, but restricted to s=7,
> b=10, and examine all 10^7 starting states.  Amazingly, ALL states fall
> into the same loop, of length 461.  (That is, all 9,999,999 states.  The
> all-zeros state is the simple zero-loop of length 1.)


I wrote:
The  same loop of lenght 461, is it
‹ the very "same" loop, fully identical (all same terms) and beginning by
the same "first term" of the loop?
‹ the same loop, same terms, fully identical, but in which the sequence
enters in another "first term" of the loop?
‹ a different loop (different terms) having the same lenght.

My feeling is that it's the second case...
Is it possible to check some cases of these 9,999,999 beginning states?



Michael Beeler writes:

It is the same loop.  All 9,999,999 starting states eventually fall into
the loop of the same 461 states.

I do not yet know whether it is case 1 or case 2, but I strongly expect it
is case 2 -- various starting states enter the loop at different places
among the 461 states.  There are some things I would like to compute about
the loop and the states falling into it.  One of them is how many of the
461 states have predecessors outside the loop -- that is, states that enter
the loop at that place.  Maybe also how many immediate predecessors each of
the 461 states has -- that is, states that become that state of the loop in
one step.

I would also like to compute the number of states that are two steps away
from the loop -- that is, they become a loop state in two steps.  And the
number that are three steps away, and four steps away, and so on.  I'd like
to know how many states are at the maximum distance from the loop, and what
that distance is.  If there are not too many of those at the maximum
distance, I'd like to list them.

There are more statistics that can be computed about the graph.  For
instance, at each distance from the graph, the number of states that have
NO predecessor can be counted.  And the maximum number of predecessors that
any state at that distance has.  And averages and standard deviations, and
so on.  But I think this graph is not significant enough to bother with
these additional statistics.


Meanwhile, I had a chance to run the two cases that were so big I gave up
on them earlier.  These results are for starting with (s-1) zeros followed
by a 1.

size = 15 digits, radix = 14, loop length = 55702156
size = 16 digits, radix = 14, loop length = 62748516


-------------------




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20051223/de6b2112/attachment-0001.htm>