[seqfan] Property of Fibonacci sequence modulo M
Jack Brennen
jfb at brennen.net
Wed Dec 2 16:57:06 CET 2009
I was considering the periodicity of the Fibonacci sequence modulo M,
and came up with an interesting problem that I can't immediately
figure out...
Consider that v(M) consists of one period of the infinite repeating
sequence of Fibonacci numbers taken modulo M -- the shortest sequence
of numbers of length L such that v[1] == 1, v[2] == 1, v[L-1] == 1,
and v[L] == 0, with v[n] == (v[n-2]+v[n-1])%M.
So v(5) would be:
1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0
Now, consider a(M) to be the number of times that the integer 1
occurs in v(M). So, for instance a(5) == 4.
The question is, can a(M) take all integer values >= 2? Probably
not easy to prove either way...
Here's the list of the first occurrence of different values of a(M):
2 == a(2) (actually the only time a(M) is 2)
3 == a(3)
4 == a(5)
5 == a(9)
6 == a(6)
7 == a(99)
8 == a(10)
9 == a(132)
10 == a(66)
11 == a(2871)
12 == a(154)
14 == a(1107)
16 == a(12771)
17 == a(3828)
18 == a(1914)
19 == a(169389)
20 == a(4466)
22 == a(508167)
24 == a(1838078)
But no solutions found (yet) for 13, 15, 21, 23.
Clearly, it seems "easier" in general for a(M) to be even rather
than odd, but there are some interesting data points, like the
fact that a(M) == 17 has many more solutions than a(M) == 16.
Also, twice in this list, we see instances where a(2M) == a(M)-1,
for M=66, and for M=1914.
Can anybody find M such that a(M) is 13, 15, 21, or 23, or
give a plausible explanation why that might be difficult?
Or even come up with a better search methodology than brute
force computation of the v[] sequences?
More information about the SeqFan
mailing list