|
%I #50 Oct 27 2023 19:42:56
%S 3,8,20,16,10,28,36,18,48,14,30,76,40,88,32,108,58,60,136,70,148,78,
%T 168,44,196,50,208,72,108,76,256,130,276,46,148,50,316,328,336,348,
%U 178,90,190,388,396,22,42,448,456,114,52,238,240,250,516,176,268,270,556
%N Pisano periods for primes: period of Fibonacci numbers mod prime(n).
%C Assuming Wall's conjecture (which is still open) allows one to calculate A001175(m) when m is a prime power since for any k >= 1: A001175(prime(n)^k) = a(n)*prime(n)^(k-1). For example: A001175(2^k) = 3*2^(k-1) = A007283(k-1).
%H Alois P. Heinz, <a href="/A060305/b060305.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H B. Avila and T. Khovanova, <a href="http://arxiv.org/abs/1403.4614">Free Fibonacci Sequences</a>, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Avila/avila4.html">J. Int. Seq. 17 (2014), # 14.8.5</a>.
%H A. Elsenhans and J. Jahnel, <a href="http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf">The Fibonacci sequence modulo p^2 -- An investigation by computer for p < 10^14</a>, (2004).
%H D. D. Wall, <a href="http://www.jstor.org/stable/2309169">Fibonacci series modulo m</a>, Amer. Math. Monthly, 67 (1960), 525-532.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Pisano_period">Pisano period</a>.
%F a(n) = A001175(prime(n)). - _Jonathan Sondow_, Dec 09 2017
%F a(n) = (3 - L(p))/2 * (p - L(p)) / A296240(n) for n >= 4, where p = prime(n) and L(p) = Legendre(p|5); so a(n) <= p-1 if p == +- 1 mod 5, and a(n) <= 2*p+2 if p == +- 2 mod 5. See Wall's Theorems 6 and 7. - _Jonathan Sondow_, Dec 10 2017
%p a:= proc(n) option remember; local F, k, p;
%p F:=[1,1]; p:=ithprime(n);
%p for k while F<>[0,1] do
%p F:=[F[2], irem(F[1]+F[2],p)]
%p od: k
%p end:
%p seq(a(n), n=1..70); # _Alois P. Heinz_, Oct 16 2015
%t Table[p=Prime[n]; a={1,0}; a0=a; k=0; While[k++; s=Mod[Plus@@a,p];a=RotateLeft[a]; a[[2]]=s; a!=a0]; k, {n,100}] (* _T. D. Noe_, Jun 12 2006 *)
%o (PARI) for(n=1,100,s=1; while(sum(i=n,n+s,abs(fibonacci(i)%prime(n)-fibonacci(i+s)%prime(n)))+sum(i=n+1,n+1+s,abs(fibonacci(i)%prime(n)-fibonacci(i+s)%prime(n)))>0,s++); print1(s,","))
%o (Python)
%o from itertools import count
%o from sympy import prime
%o def A060305(n):
%o x, p = (1,1), prime(n)
%o for k in count(1):
%o if x == (0,1):
%o return k
%o x = (x[1], (x[0]+x[1]) % p) # _Chai Wah Wu_, May 31 2022
%Y Cf. A001175, A000961, A071774, A003147, A296240.
%K nonn
%O 1,1
%A Louis Mello (mellols(AT)aol.com), Mar 26 2001
%E Corrected by _Benoit Cloitre_, Jun 04 2002
%E Name clarified by _Jonathan Sondow_, Dec 09 2017
|
