[seqfan] Re: Property of Fibonacci sequence modulo M

Jack Brennen jfb at brennen.net
Wed Dec 2 20:48:04 CET 2009

Yeah, thanks for pointing that OEIS sequence out.
So my question is whether the second column in your
triangular array contains every integer >= 2?  Seems
plausible, but also seems beyond the realm of proof
unless somebody can find a constructive method to
generate examples for a particular target value.

Using just some ad hoc guessing, I was able to find, for instance,
that a(396883212) == 65.  It seems "easy" in some way to find
examples where the target is an odd number of the form 2^n+1.
For instance, multiply that number by 59, and you get:
a(23416109508) == 129.

The same ad hoc method gave me a(3571948908) == 35, which is a
relatively large odd target not of the form 2^N+1.  (This number
is just the original number above multiplied by 9.)

(Note that the Pisano periods for all of these examples fall into
the 6-digit to 7-digit range.  The brute force method that I'm using
of calculating one entire Pisano period and counting the times that
1 occurs can probably be improved by orders of magnitude by applying
a little more ingenuity.)

But I still don't see an obvious constructive method; for instance,
if a(X*Y) is equal to 13, what values of X and Y should we choose
to make the search most productive?  How do a(X) and a(Y) relate
to a(X*Y) for X,Y relatively prime?  The function isn't multiplicative
in the rigorous sense, but it does have some multiplicative properties
in that a(X*Y) is related to a(X) and a(Y) in some sense.

Richard Mathar wrote:
> jb> Date: Wed, 02 Dec 2009 07:57:06 -0800
> jb> From: Jack Brennen <jfb at brennen.net>
> jb> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> jb> Subject: [seqfan]  Property of Fibonacci sequence modulo M
> jb> 
> jb> Consider that v(M) consists of one period of the infinite repeating
> jb> sequence of Fibonacci numbers taken modulo M -- the shortest sequence
> jb> of numbers of length L such that v[1] == 1, v[2] == 1, v[L-1] == 1,
> jb> and v[L] == 0, with v[n] == (v[n-2]+v[n-1])%M.
> jb> 
> jb> So v(5) would be:
> jb>    1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0
> jb> 
> jb> Now, consider a(M) to be the number of times that the integer 1
> jb> occurs in v(M).  So, for instance a(5) == 4.
> In OEIS speak: the smallest row k for which A128924(k,1) = n.
> I see that the k-Fibonacci sequences a(n+1)=k*a(n)+a(n-1) are in the OEIS
> for k=1 (*the* Fibonacci sequence),
> k=2 (A000129)
> k=3 (A006190)
> k=4 (A001076)
> k=5 (0 followed by A052918)
> k=6 (A005668)
> k=7 (0 followed by A054413)
> k=8 (0 followed by A041025)
> k=9 (A099371) 
> k=10 (0 followed by A041041)
> k=11 (0 followed by A049666)
> k=12 (0 followed by A041061)
> Are the associated Pisano period lengths in the OEIS, generalizing A001176?
> These are discussed by
> S. Falcon and A. Plaza in "k-Fibonacci sequences modulo m", Chaos, Solitons & Fractals 41 (10) (2009) 497-504
> http://dx.doi.org/10.1016/j.chaos.2008.02.014
> Richard
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list