Puzzle time - the Fibonacci numbers
-
wrote on 15 Sept 2020, 13:36 last edited by Klaus
I did a tiny bit of programming, and I think it's a nice programming exercise to come up with an elegant way to compute the cycle length of "Fib mod n" sequences.
Here's a 4-liner I came up with.
fibsmod n = map ((`mod` n) . fst) $ iterate (\(a,b) -> (b,a+b)) (0,1) pairIndex a b (x:y:ys) m = if (a == x) && (b == y) then m else pairIndex a b (y:ys) (m+1) p (x:y:ys) = pairIndex x y ys 2 take 100 $ map (p . fibsmod) [2..]
It computes the first 100 cycle length:
[3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60,16,30,48,24,100,84,72,48,14,120,30,48,40,36,80,24,76,18,56,60,40,48,88,30,120,48,32,24,112,300,72,84,108,72,20,48,72,42,58,120,60,30,48,96,140,120,136,36,48,240,70,24,148,228,200,18,80,168,78,120,216,120,168,48,180,264,56,60,44,120,112,48,120,96,180,48,196,336,120,300,50]
-
wrote on 15 Sept 2020, 14:01 last edited by
What language is that?
-
wrote on 15 Sept 2020, 14:59 last edited by
It's a computer language. Computer programmers use computer languages to "talk" to computers and tell them what to do!
-
wrote on 15 Sept 2020, 15:17 last edited by
Interesting observation:
Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?
-
wrote on 15 Sept 2020, 17:22 last edited by Klaus
@jon-nyc said in Puzzle time - the Fibonacci numbers:
What language is that?
Haskell.
I bet if you do the same thing in your favorite language you need at least twice as much code, and the code will be less extensible. (throws gauntlet)
-
wrote on 15 Sept 2020, 17:56 last edited by
I use 8086 assembler for such tasks.
-
wrote on 15 Sept 2020, 19:09 last edited by
Are you two about to have a 'my dick is smaller' contest?
-
Are you two about to have a 'my dick is smaller' contest?
wrote on 15 Sept 2020, 19:18 last edited by@Doctor-Phibes Did you know that dick sizes have a Fibonacci distribution? It's a distribution with a very long tail...
<insert @George-K rimshot image macro here>
-
Interesting observation:
Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?
wrote on 15 Sept 2020, 21:44 last edited by@jon-nyc said in Puzzle time - the Fibonacci numbers:
Interesting observation:
Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?
bump for Klaus and his little 4 line program.
-
@jon-nyc said in Puzzle time - the Fibonacci numbers:
Interesting observation:
Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?
bump for Klaus and his little 4 line program.
wrote on 15 Sept 2020, 22:06 last edited by Klaus@jon-nyc said in Puzzle time - the Fibonacci numbers:
@jon-nyc said in Puzzle time - the Fibonacci numbers:
Interesting observation:
Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?
bump for Klaus and his little 4 line program.
Can you explain? You mean that the cycle length of Fib mod (2^n) is the same as Fib mod (3*2^(n-1))? That doesn't seem to be true.
I uploaded the first 10,000 cycle lengths here, if you want to check this yourself.
https://www.heypasteit.com/clip/0IV18W -
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
-
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
-
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