periods of fibonacci-like sequences mod p
quasi
Choose a,b in Z_p, not both 0.
Define a sequence x_1, x_2, x_3, ... of elements of Z_p by
x_1 = a
x_2 = b
x_n = x_(n-1) + x_(n-2) if n > 2
Let m(p), M(p) be the least and greatest possible periods for the
sequence (x_n), over all choices of initial values a,b
Conjectures:
(1) If p = 2 or 3 (mod 5) then m(p) = M(p) != p-1.
(2) If p = 1 or 4 (mod 5) then m(p) = M(p) iff M(p) = p-1.
quasi
achille
(2) is false for p = 11,
(a,b) = (1,8) -> 1,8,9,6,4,10,3,2,5,7,1,... has period 10.
(a,b) = (1,4) -> 1,4,5,9,3,1,4,5,9,3,1... has period 5.
ie. m(p) /= M(p) but M(p) = p-1.
aayushbabu
Regards,
Pubkeybreaker
> I'm completely new to this forum and maybe there's something to do with the variable naming conventions here or whatever the case, I didn't understand the Z_p thing. Please clarify.
> Regards,
Z_p is the same as Z/pZ; standard number-theoretic notation.
quasi
Thanks.
In fact, there are counterexamples both ways for Conjecture (2).
I'll revise the wording in my next reply.
quasi
quasi
Let p be a prime, p != 5.
Choose a,b in Z_p, not both 0.
Define a sequence x_1, x_2, x_3, ... of elements of Z_p by
x_1 = a
x_2 = b
x_n = x_(n-1) + x_(n-2) if n > 2
Let m(p), M(p) be the least and greatest possible periods for the
sequence (x_n), over all choices of initial values a,b.
Conjectures:
(1) If p = 2 or 3 (mod 5) then m(p) = M(p) != p-1
(2) If M(p) = p-1 then m(p) = p-1 or (p-1)/2.
I'm not really sure about either of the above claims, although I think
Conjecture (1) has a better chance.
quasi
quasi
wrote:
>I'm completely new to this forum and maybe there's something
>to do with the variable naming conventions here or whatever
>the case, I didn't understand the Z_p thing. Please clarify.
It just means the ring of integers, mod p.
In other words,
Z_p = {0,1,2, ..., p-1}
with addition and multiplication mod p.
quasi
geo
A nice little exercise.
Let T be the 2x2 matrix
T=
(0 1)
(1 1)
Then T has an inverse
T^(-1)=
(p-1 1)
( 1 0)
For in initial vector (a,b), not (0,0),
with elements in F, the field of residues mod p,
(a,b)T=(b,a+b).
The sequence
(a,b), (a,b)T, (a,b)T^2,....
is finite because F is finite and
is periodic because T has an inverse.
If 5 is a quadratic residue for p: 5=r^2 mod p,
then T has eigenvalues in F, (1 +/- r)/2,
and the order of T is the (common) order
for those eigenvalues.
If 5 is not a quadratic residue,
then the order of T will be (2p+2)/k,
with k=1 about 80% of the time.
George Marsaglia
quasi
wrote:
I'll have to go through it more carefully later, but it seems clear
that your analysis gets to the heart of the matter.
Thanks.
quasi
quasi
Actually, Conjecture (2) seems OK.
In fact, here's a generalized version ...
Let p be a prime, and let r,s in Z, with s not a multiple of p.
Choose a,b in Z_p, not both 0.
Define a sequence x_1, x_2, x_3, ... of elements of Z_p by
x_1 = a
x_2 = b
x_n = r*x_(n-1) + s*x_(n-2) if n > 2
Let m(p), M(p) be the least and greatest possible periods for the
sequence (x_n), over all choices of initial values a,b.
Conjecture (2) [generalized version]:
If M(p) = p-1 then m(p) = p-1 or (p-1)/2.
Remarks:
Most likely, the method George Marsaglia described will be the key to
resolving the above claim, but I don't have time right now to work out
the details.
quasi
quasi
>Let p be a prime, and let r,s in Z, with s not a multiple of p.
I meant:
Let p be a prime, and let r,s in Z_p with s != 0.
achille
The generalized version of (2) is false.
Counterexample:
(r,s) = (16,12) for p = 17
(a,b) = (1,3) -> 1,3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1,3... has
period 16 = p-1.
(a,b) = (1,13) -> 1,13,16,4,1,13,... has period 4 /= p-1 nor (p-1)/
2.
quasi
<achil...@yahoo.com.hk> wrote:
>On Feb 4, 6:48 am, quasi <qu...@null.set> wrote:
>> On Thu, 03 Feb 2011 17:06:18 -0500, quasi <qu...@null.set> wrote:
>> >Let p be a prime, and let r,s in Z, with s not a multiple of p.
>>
>> I meant:
>>
>> Let p be a prime, and let r,s in Z_p with s != 0.
>>
>> >Choose a,b in Z_p, not both 0.
>>
>> >Define a sequence x_1, x_2, x_3, ... of elements of Z_p by
>>
>> > x_1 = a
>> > x_2 = b
>> > x_n = r*x_(n-1) + s*x_(n-2) if n > 2
>>
>> >Let m(p), M(p) be the least and greatest possible periods for
>> >the sequence (x_n), over all choices of initial values a,b.
>>
>> >Conjecture (2) [generalized version]:
>>
>> >If M(p) = p-1 then m(p) = p-1 or (p-1)/2.
>>
>> >Remarks:
>>
>> >Most likely, the method George Marsaglia described will be
>> >the key to resolving the above claim, but I don't have time
>> >right now to work out the details.
>>
>The generalized version of (2) is false.
>Counterexample:
>
> (r,s) = (16,12) for p = 17
> (a,b) = (1,3) -> 1,3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1,3...
> has period 16 = p-1.
> (a,b) = (1,13) -> 1,13,16,4,1,13,...
> has period 4 /= p-1 nor (p-1)/2.
Yep.
I don't know what I was thinking -- for general r,s, Conjecture (2)
isn't even close to true. It does appear to hold for r = s = 1, but
even that may be an illusion.
quasi
achille
Assuming p > 2,
(2) is true when s = 1 and x^2 - rx - s has two
distinct roots in Z_p.
In that case, the two roots u,v of x^2 - rx - s
satisfies v = -u^-1. It is then easy to show:
order(u) = 0 mod 4 => order(v) = order(u).
order(u) = 2 mod 4 => order(v) = order(u)/2
order(u) = 1 mod 2 => order(v) = order(u)*2
On the other hand, if x^2 - rx - s has no root in
Z_p, then M(p) = m(p) != p - 1.
quasi
Looks very good.
Thanks.
quasi