Silly Fibonacci loops

Hello Math-Fun,

Here are the 31 first Fibonacci numbers: n — a(n) 0 — 0 1 — 1 2 — 1 3 — 2 4 — 3 5 — 5 6 — 8 7 — 13 8 — 21 9 — 34 10 — 55 11 — 89 12 — 144 13 — 233 14 — 377 15 — 610 16 — 987 17 — 1597 18 — 2584 19 — 4181 20 — 6765 21 — 10946 22 — 17711 23 — 28657 24 — 46368 25 — 75025 26 — 121393 27 — 196418 28 — 317811 29 — 514229 30 — 832040 31 — 1346269 A loop with 7: The first substring 7 appears in Fibo# 14 (=377) The first substring 14 appears in Fibo# 12 (=144) The first substring 12 appears in Fibo# 26 (=121393) The first substring 26 appears in Fibo# 31 (=1346269) The first substring 31 appears in Fibo# 28 (=317811) The first substring 28 appears in Fibo# 23 (=28657) The first substring 23 appears in Fibo# 13 (=233) The first substring 13 appears in Fibo# 7 (=13) Loop. I guess all positive integers loop here. But some loops will be bigger than others. As we are in November, is there a loop of size 89? Best, É.

_______________________________________________ math-fun mailing list -- math-fun@mailman.xmission.com To unsubscribe send an email to math-fun-leave@mailman.xmission.com

_______________________________________________

December 8th, 2022 update (long – Hans, Maximilian, Chris, Allan)

> On Mon, Nov 21, 2022 at 7:03 PM Hans Havermann wrote: > > Be aware that a lot of start numbers will never appear again because some > subsequent term in the evolution is what loops. For example, in (17, 22, > 29, 29, ...), the 29 loops; in (20, 30, 32, 30, ...), the 30-32 loops. If > your "loop with 7" is size 8, for other starts I'm only seeing loops of > size 1 (first example), 2 (second example), and 8. 

> On 11/21/22 17:39, M F Hasler wrote:

>

> I confirm that the only loops appear to be : > > length 1: > [0], [1], [29], [5], [43], [48], [53], > > length 2: > [30, 32], > > length 8: > [7, 14, 12, 26, 31, 28, 23, 13]. > > All other numbers (up to 10^4 at least, and beyond) "transit" to one of these. > > - Maximilian

____________________

Christopher L. (08/12/2022 03:11)

> hihi, all - I was intrigued by Eric Angelini's "silly Fibonacci question'', so i worked on it since it was posted (the message arrived 07:23 PST 21 Nov). The question asks what is the minimal m for which all non-negative integers (i like using fib[0] = 0) up to a given n, written without leading 0 unless it is 0, are contained (as consecutive digit subsequences) among the digit sequences fib[0-m], each also written without leading 0 unless it is 0, for various n, and what is the most recalcitrant sequence less than m for each n (the last one seen). 

(1) At least up to n = 2 ^ 23 - 1, every value goes into one of the periodic cycles posted (that message arrived 19:03 PST, also 21 Nov) by M F Hasler (i see that the cycle containing 0 was included), and all of those cycles first occur in fib[0-53]. Some small answers to the original question 0-n are contained in fib[0-m], last one found:

0-8191  fib[0-925],  last one 1562

0-16383 fib[0-3023], last one 11267 0-32767 fib[0-3148], last one 24242 0-65535 fib[0-3148], same last one (that means that when the program finds the last value less than 32768, it has already found all other values less than 65536) Some medium answers to the original question 0-n are contained in fib[0-m], last one found cpu time 0-131071  fib[0-11527], last one 105940 8m 0-262143  fib[0-11527], same last one 24m50s 0-524287  fib[0-11527], same last one 1h30s 0-1048575 fib[0-33773], last one 1004344 2h30m 0-2097151 fib[0-36041], last one 1804140 13h40m 0-4194303 fib[0-37115], last one 3716373 35h35m 0-8388607 fib[0-40260], last one 6648086 78h3m As you can see in the last column just above, these last completed runs take dozens of hours (i tried to get away with quite naive algorithms all written in gawk), and often run out of system resources (i am using three ancient (built 2009) dual Xeon PC servers with 192GB main memory and 27TB disk space each), so i'll stop here. (Hint: i didn't, so this is current progress). It should be noted that fib[98] is already 21 digits, fib[40300] has 8422 digits, and fib[2^20 - 1] has 219139 digits, so the times should not have been as much of a surprise as they were to me. 

(2) A related question: what is the smallest n for which the sequences fib[0-n], written without leading 0 unless it is 0, contain all of the 10 ^ d sequences of d digits (these include those with leading zeroes), for each d>0 separately (of course, if all d-sequences are contained, then all shorter sequences are contained). fibs[0-15] contain all 1-digit sequences, last one 6 fibs[0-94] contain all 2-digit sequences, last one 82 fibs[0-261] contain all 3-digit sequences, last one 133 fibs[0-925] contain all 4-digit sequences, last one 1562 fibs[0-3148] contain all 5-digit sequences, last one 24242 fibs[0-12223] contain all 6-digit sequences, last one 608395 fibs[0-40260] contain all 7-digit sequences, last one 6648086  

(3) The same two sequence containment questions can be asked for any integer radix at least 2 (the previous question could be rephrased as looking for every single digit in base 10 ^ d). I have not studied any of these questions, but they sound like fun, especially if all of them have this same kind of small set of small cycles for all trajectories. 

(4) Finally, what is special about the Fibonacci numbers in this context? Could it be that any sequence of integers whose size is increasing at least exponentially can have this kind of property? Certainly not, but what is an appropriate restriction on the sequence? 

more later, chris landauer 

PS - i also learned from snooping the Web that the "related question'' (2) above is called the "coupon collector's'' problem when the input is assumed to be random from a known finite set, and there is an extensive literature about it, but none of the papers i read specifically answers the question for the fibonacci sequence (or any other non-randomly generated sequence) - however, the estimates did help enormously in limiting the search space for this problem.

____________________

Allan W. (08/12/2022 03:30)  

> If you just repeat the exercise with powers of 2 instead of Fibonacci numbers, don't you get behavior that is statistically the same (though, of course, different in detail)? I think it was Gosper who used to complain that representing numbers in any base was essentially a kind of encryption, and that there was almost never anything special in the sequences of digits that make up various kinds of numbers. (He was especially complaining about pi and people's fetish for learning zillions of base-10 digits, as opposed to zillions of continued fraction denominators, for instance.)

____________________

Chris L. (08/12/2022 04:12)

> yes - that is my feeling also (of course powers of 2 get larger faster, but i don't see how that should change things) however, in base 10, final sequences (means last few digits of each value) become restricted, though in any base relatively prime to 2, the same sort of statistics should hold, with corresponding caveats for other bases (defining ``digits'') and generators (defining growth rate) more later, chris

____________________

Allan W. (08/12/2022 04:35)  

> The restricted region at the least significant end grows very slowly. For example, for powers of two, the 1-digit cycle length is 4, but the 2-digit period is 20. So it doesn't cut into the fertile churning fields of pseudorandomness to any serious extent. I didn't do a careful survey, but I think *most* of the two-digit patterns occur in the powers of 2 before about 2^45. There may be a couple of stragglers. Christopher is probably better set up to look than I am.

____________________

Chris L. (08/12/2022 08:37)

> hihi, all - yes (i agree more with Allan Wechsler than i did at first) - the period for powers of 2 (mod 10 ^ d) is observed to be 4 * 10 ^ (d-1) = phi(10^d), and the first repeated value is 2^d (at least up to d==12) - i suspect it follows fairly easily from fermat's little theorem that the period always divides phi(10^d), and similarly for other bases, though for any generator g and base b, one has to separate the part of g relatively prime to b from the rest - but i suspect that the proof that the period is phi(b) is a little harder, and is likely not true in general (the structure of multiplication by g (mod b) is somewhat peculiar) so the last digits are restricted, but the rest are not, and i now believe that the same distribution properties should hold in the long run more soon, chris 

____________________

Chris L. (27/12/2022 08:37)

hihi, all - first, thanx to Eric for a problem that was more interesting than it first seemed (to me) then, to expand on Alan Wechsler's ``suspicion'' (arrived 22 dec 13:55 PST), i think the following things can be proven about an integer sequence a(n) (digits can be digits [0..b-1] in any integer radix b >= 2) (1) IF the number of digits in a(n) grows linearly (as both fib(n) and 2 ^ n do), THEN the number of contiguous subsequences of a(n) of any given length d, called d-sequences, (eventually) also increases linearly, and the total number of d-sequences that occur in a(m) for m up to n (eventually) increases quadratically (i think that this one is easy) (2) IF the number of digits in a(n) grows linearly, AND they are (eventually or at least mostly) pseudo-random, THEN all d-sequences are (expected to be) seen before ...some function of n... (i think that this one should be relatively easy, depending on the function) (3) faster growth implies more d-sequences for smaller n, which should imply things happen sooner (a guess, likely provable) (4) since all d-sequences are seen before some bound, that should help show that cycles are small, if the bound is small enough (a guess, likely true, possibly provable) all of this depends on something that i am pretty sure is well known (to the people who know it well, to quote one of our illustrious members), but have had the devil of a time trying to derive (nasty nasty algebra) - (0) for a given finite set S of size s, and a repeated experiment in which one element of S is selected uniformly randomly (with replacement), the expected time at which all elements of S have been found is ...some known function of s... (also expected variance is interesting, and other distribution parameters, including median and percentiles) using this for the set S (of size s = b ^ d) of d-sequences for the a(n) considered above is the key and i wonder about the related (not entirely well-defined) question - (5) does this work if the number of digits increases less than linearly? how much less works? more later, chris

 __________

On 12/22/22 13:55, Allan Wechsler wrote: > If a sequence grows fast, but its digits are mostly pseudorandom, then we > are more likely to find any given substring early. That crowds the values > in Angelini's iteration downward, and I suspect it would reduce the number > of cycles, since there are fewer possibilities. I wonder if this effect is > enough to explain the reduction in the number of cycles that Mike Beeler > reports. > > On Thu, Dec 22, 2022 at 2:02 PM Michael Beeler<mikebeeler2@gmail.com> > wrote: > >> Back on November 21, Eric Angelini asked about loops formed by: >> take a value; find the first Fibonacci number that contains that >> digit-string; >> replace the value with the index of that Fibonacci number; iterate. >> >> Various people speculated on bases other than decimal; I posted >> results (tediously long) on December 14. Earlier, Christopher Landauer >> and Allan Wechsler speculated about whether powers of 2 would have the >> same statistics, and the same property. I found that yes, they do, >> with a few quirky differences. >> >> For powers of 2, and any radix 3 through 99 (except 4, 8, 16, 32, 64), all >> values >> through 2^20-1 fall into one of a fairly small number of cycles (loops), >> each >> cycle with at most a modest number of members, and members are of modest >> size. >> >> The Fibonacci behavior versus the powers of 2 behavior: >> >> Radixes of interest: >> Fib: any > 1; I tested 98 radixes, 2..99 >> 2^n: any > 2 but not powers of 2; I tested the 92 in range 3..99 >> >> Cycles common to all radixes I tested: >> Fib: [0] [1] [5] >> 2^n: none >> >> Average cycles per radix (difference seems strangely large): >> Fib: 7.84 >> 2^n: 4.27 >> >> Average members per cycle, over all radixes tested: >> Fib: 2.48 >> 2^n: 2.84 >> >> Values never seen as a member of a loop (maybe provable?): >> Fib: 2 and 4 >> 2^n: 0, 1, 2, and 4 >> >> Curiosities: >> Fib: >> radixes 30-33 have the 2-cycle [7, 13] >> radixes 40-42 have the 3-cycle [6, 21, 8] >> unusually large 1-cycle values: [601] for radix 24; >> [1122] for radix 31; [3512] for radix 57; [4685] for radix 67 >> 2^n: >> radixes 33-36 have the 3-cycle [3, 7, 8] >> radixes 65-85 have the 2-cycle [3, 8] >> unusually large 1-cycle values: [666] for radix 99; [703] for radix 21 >> radixes with a single 1-cycle: radix 3 has [11]; radix 59 has [407] >> (Fib has none, as all radixes have [0] [1] [5]) >> 11 radixes have the 1-cycle [10] (only 2 such radixes with Fib) >> >> A few of the powers of 2 results: >> radix 3: [11] >> radix 5: [3] [5, 7] >> radix 6: [3, 7, 8] [5] [9, 11, 13] [19] >> radix 7: [6, 10, 9] [33] [55] >> radix 9: [5] [17] [34] >> radix 10: [3, 5, 8] [10] [22, 43] >> radix 11: [3, 8] [6, 9] [7] [34] >> radix 12: [3, 9, 8] [7, 10] >> >> For example, consider "radix 3: [11]" >> value 11 (base 10) = 102 (base 3) >> powers of 2 are: >> power base 10 base 3 >> 0 1 1 >> 1 2 2 >> 2 4 11 >> 3 8 22 >> 4 16 121 >> 5 32 1012 >> 6 64 2101 >> 7 128 11202 >> 8 256 100111 >> 9 512 200222 >> 10 1024 1101221 >> 11 2048 2210212 >> And "102" first appears in 2^(11 base 10) (base3). >> That is, entirely in base 3, value 102 first appears in 2^102, making a >> loop.