Puzzle time - the Fibonacci numbers

[jon-nyc]

Show that every positive integer has a multiple that is a Fibonacci number.

[Klaus]

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.

[Klaus]

Actually, there's a trivial solution, too : The first Fibonacci number is 0. 0 is a multiple of any number.

[jon-nyc]

Haha. Let’s agree to go for the non-trivial solution.

[Klaus]

Do you (already) know the solution? Does it involve advanced math? Even the partial statement that your proposition holds for prime numbers isn't exactly trivial to show.

[jon-nyc]

I know a very elegant solution that requires no advanced math.

Hint?

[jon-nyc]

Explore the Fibonacci numbers mod n for a few n

[Klaus]

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.

[jon-nyc]

You’re on track, and one small insight from a solution.

[Klaus]

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.

[jon-nyc]

That’s right. The process is totally reversible so the 0,1,1 must eventually repeat.

[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]

[jon-nyc]

What language is that?

[Horace]

It's a computer language. Computer programmers use computer languages to "talk" to computers and tell them what to do!

[jon-nyc]

Interesting observation:

Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?

[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)

[jon-nyc]

I use 8086 assembler for such tasks.

[Doctor Phibes]

Are you two about to have a 'my dick is smaller' contest?

[Klaus]

@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]

@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.