[seqfan] Re: Computing sequences up to first non-distinct element: re-inventing the wheel?

[Marc LeBrun]

An interesting loop detector, quoted in its entirety from HAKMEM below.
Requires just one generator, plus space O(LOG longest possible period).
========
ITEM 132 (Gosper): LOOP DETECTOR
If a function F maps a finite set into itself, then its flow must always be
cyclic.  If F is one step of a pseudorandom number generator, or the CDR
operation on a self referent list, or any function where it is easy to
supply former values as arguments, then there are easy ways to detect
looping of the flow (Knuth, The Art of Computer Programming, volume 2,
Seminumerical Algorithms, sec. 3.1, prob. 7, page 7).  If, however, the
process or iterated application of the function is inexorable, (i.e., there
is no easy way to switch arguments to the function), then the following
algorithm will detect repetition before the third occurrence of any value.

Set aside a table TAB(J), 0 <= J <= log 2 (Largest possible period).  Let C
= the number of time F has been applied, initially 0.  Compare each new
value of F for equality with those table entries which contain old values of
F. These will be the first S entries, where S is the number of times C can
be right shifted before becoming 0.  No match means F hasn't been looping
very long, so increment C and store this latest value of F into TAB(J),
where J is the number of trailing zero bits in the binary of C.  (The first
16 values of J are: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...;
Eric Jensen calls this the RULER function.)  A match with entry E means the
loop length is 1 more than the low E+2 bits of C - 2^(E+1).
========

>="Ron Hardin" <rhhardin at att.net>

> Not Mathematica but what I did for Collatz sequences was run two, one at half
> speed, and check for equality.
> 
> It solves the memory problem at some cost in speed.
> 
> In the case of Collatz, you only have to start running two if you've broken
> the 
> previous record for number of steps, getting most of the speed back.
> 
>  rhhardin at mindspring.com
> rhhardin at att.net (either)
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/