A000057 - OEIS

%I M0856 N0326 #96 Jun 18 2024 18:01:21

%S 2,3,7,23,43,67,83,103,127,163,167,223,227,283,367,383,443,463,467,

%T 487,503,523,547,587,607,643,647,683,727,787,823,827,863,883,887,907,

%U 947,983,1063,1123,1163,1187,1283,1303,1327,1367,1423,1447,1487,1543,1567,1583

%N Primes dividing all Fibonacci sequences.

%C Here a Fibonacci sequence is a sequence which begins with any two integers and continues using the rule s(n+2) = s(n+1) + s(n). These primes divide at least one number in each such sequence. - _Don Reble_, Dec 15 2006

%C Primes p such that the smallest positive m for which Fibonacci(m) == 0 (mod p) is m = p + 1. In other words, the n-th prime p is in this sequence iff A001602(n) = p + 1. - _Max Alekseyev_, Nov 23 2007

%C Cubre and Rouse comment that this sequence is not known to be infinite. - _Charles R Greathouse IV_, Jan 02 2013

%C Number of terms up to 10^n: 3, 7, 38, 249, 1894, 15456, 130824, 1134404, 10007875, 89562047, .... - _Charles R Greathouse IV_, Nov 19 2014

%C These are also the fixed points of sequence A213648 which gives the minimal number of 1's such that n*[n; 1,..., 1, n] = [x; ..., x], where [...] denotes simple continued fractions. - _M. F. Hasler_, Sep 15 2015

%C It appears that for n >= 2, all first differences are congruent to 0 (mod 4). - _Christopher Hohl_, Dec 28 2018

%C The comment above is equivalent to a(n) == 3 (mod 4) for n >= 2. This is indeed correct. Actually it can be proved that a(n) == 3, 7 (mod 20) for n >= 2. Let p != 2, 5 be a prime, then: A001175(p) divides (p - 1)/2 if p == 1, 9 (mod 20); p - 1 if p == 11, 19 (mod 20); (p + 1)/2 if p == 13, 17 (mod 20). So the remaining cases are p == 3, 7 (mod 20). - _Jianing Song_, Dec 29 2018

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Christian G. Bower and T. D. Noe, <a href="/A000057/b000057.txt">Table of n, a(n) for n = 1..1000</a>

%H U. Alfred, <a href="http://www.fq.math.ca/Scanned/2-1/alfred2.pdf">Primes which are factors of all Fibonacci sequences</a>, Fib. Quart., 2 (1964), 33-38.

%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 D. M. Bloom, <a href="http://www.jstor.org/stable/2315029">On periodicity in generalized Fibonacci sequences</a>, Am. Math. Monthly 72 (8) (1965) 856-861.

%H H. E. A. Campbell and David L. Wehlau, <a href="https://doi.org/10.1016/j.ffa.2023.102198">Zigzag polynomials, Artin's conjecture and trinomials</a>, Finite Fields and Their Applications (2023) Vol. 89, 102198.

%H Paul Cubre and Jeremy Rouse, <a href="http://arxiv.org/abs/1212.6221">Divisibility properties of the Fibonacci entry point</a>, arXiv:1212.6221 [math.NT], 2012.

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibGen.html">General Fibonacci Series</a>.

%H Rishi Kumar, <a href="https://arxiv.org/abs/2406.05890">Kepler Sets of Second-Order Linear Recurrence Sequences Over Q_p</a>, arXiv:2406.05890 [math.NT], 2024. See pp. 2, 7.

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence).

%t Select[Prime[Range[1000]], Function[p, a=0; b=1; n=1; While[b != 0, t=b; b = Mod[(a+b), p]; a=t; n++]; n>p]] (* _Jean-François Alcover_, Aug 05 2018, after _Charles R Greathouse IV_ *)

%o (PARI) select(p->my(a=0,b=1,n=1,t);while(b,t=b;b=(a+b)%p; a=t; n++); n>p, primes(1000)) \\ _Charles R Greathouse IV_, Jan 02 2013

%o (PARI) is(p)=fordiv(p-1,d,if(((Mod([1,1;1,0],p))^d)[1,2]==0,return(0)));fordiv(p+1,d,if(((Mod([1,1;1,0],p))^d)[1,2]==0,return(d==p+1 && isprime(p)))) \\ _Charles R Greathouse IV_, Jan 02 2013

%o (PARI) is(p)=if((p-2)%5>1, return(0)); my(f=factor(p+1)); for(i=1, #f~, if((Mod([1, 1; 1, 0], p)^((p+1)/f[i, 1]))[1, 2]==0, return(0))); isprime(p) \\ _Charles R Greathouse IV_, Nov 19 2014

%Y Subsequence of A064414.

%Y Cf. A001175, A001602, A079346, A106535, A213648.

%K nonn

%O 1,1

%A _N. J. A. Sloane_

%E More terms from _Don Reble_, Nov 14 2006