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

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.

The New Coffee Room

Puzzle time - the Fibonacci numbers