Puzzle time - the Fibonacci numbers
-
Show that every positive integer has a multiple that is a Fibonacci number.
-
Hm, interesting.
I was browsing the Wikipedia article on Fibonacci numbers to look up some of the identities given there, and I believe I regrettatably already stumbled upon a major part of the solution.
||
The snippet above illustrates the situation for prime numbers, but any number is a product of prime numbers, so presumably it can be made to work for non-prime numbers (but the details are not yet clear to me).
||But the Wikipedia article leaves out the derivation/proof. Slackers.
-
Haha. Let’s agree to go for the non-trivial solution.
-
I know a very elegant solution that requires no advanced math.
Hint?
-
Explore the Fibonacci numbers mod n for a few n
-
Well, the "mod n" sequences seem to loop. In particular, they always seem to come back to 0. Which means that those "0" points can be divided by n.
So if "zero(n)" is the index of the first fibonacci number (different from 0) where Fib(zero(n)) mod n = 0, then n divides the zero(n)-th Fibonacci number.
However, it's not so clear why the "mod n" sequences have that looping structure.
-
You’re on track, and one small insight from a solution.
-
I think the proof of looping can be seen from the congruence property of modular arithmetic. In particular, "modulo" is a congruence with respect to Fibonacci numbers:
Fib(n) mod m = (Fib(n-1) mod m) + (Fib(n-2) mod m) (for n >= 2)
Since there are only about m^2 possible pairs of numbers in the "mod n" ring, and Fib(n) mod m only depends on the pair of previous numbers (mod m), it follows that the sequence must necessarily loop.
-
That’s right. The process is totally reversible so the 0,1,1 must eventually repeat.
-
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]
-
What language is that?
-
Interesting observation:
Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?
-
-
I use 8086 assembler for such tasks.
-
Are you two about to have a 'my dick is smaller' contest?
-
@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>
-
@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.