Puzzle time - the Fibonacci numbers
-
wrote on 15 Sept 2020, 22:23 last edited by jon-nyc
No, the cycle length of Fib mod (2^n) = 3*2^(n-1))
Check Fmod2, Fmod4, Fmod8, Fmod16 etc for their cycle lengths. You’ll get 3,6,12,24,48 etc. I’m wondering if it holds. I think it will.
-
wrote on 15 Sept 2020, 22:31 last edited by
Here's a list of pairs where the first number shows the "n" (but only for powers of 2) and the second one the associated cycle length. Maybe I missunderstood something but your conjecture doesn't seem to hold.
[(2,6),(4,24),(8,60),(16,24),(32,36),(64,120),(128,420),(256,264),(512,516),(1024,72),(2048,600),(4096,1368),(8192,720)] -
wrote on 16 Sept 2020, 00:00 last edited by jon-nyc
But your original list is this one:
(left side numbering mine, right side list yours)
-
wrote on 16 Sept 2020, 09:05 last edited by
Ah, looks like an "off by two" error somewhere. Hmm....
-
wrote on 16 Sept 2020, 09:11 last edited by Klaus
Turned out to be two "off by 1" errors that have to do with indices starting at 0 and not 1.
What about this result?
[(2,3),(4,6),(8,12),(16,24),(32,48),(64,96),(128,192),(256,384),(512,768),(1024,1536),(2048,3072),(4096,6144),(8192,12288)] -
wrote on 16 Sept 2020, 09:15 last edited by Klaus
It looks like linear relations between the cycle length happen quite frequently. This is a scatter plot of the cycle lengths I computed above (haven't used R in a while - fun for plotting data!). Observe all the dotted lines. The points you identified are on one of those lines. Also interesting to see a few outliers.
I have marked the points you are interested in in red. You see that there are way more points on that line.
-
wrote on 16 Sept 2020, 10:45 last edited by
Interesting.
So it turns out Fibonacci cycle lengths a thing people study. They’re called Pisano numbers and understanding them is really about understanding Pisano numbers for prime powers.
A neat property is that if n and m are coprime then period(mn) is least common multiple of period(n) and period(m).
-
wrote on 16 Sept 2020, 10:48 last edited by
Wait a minute, is that really your graph up there? This is from Wiki
-
wrote on 16 Sept 2020, 10:59 last edited by Klaus
Yes, it's my graph. I haven't seen the WIki graph yet, but it shows the same data, so of course it's similar. It's an interesting coincidence that they also cut off at 10,000.
-
wrote on 16 Sept 2020, 11:37 last edited by
Just for fun, here's the continuation of the dataset for cycle lengths up to 20000.
