A003147 - OEIS

%I M3811 #95 Oct 29 2023 01:43:25

%S 5,11,19,31,41,59,61,71,79,109,131,149,179,191,239,241,251,269,271,

%T 311,359,379,389,409,419,431,439,449,479,491,499,569,571,599,601,631,

%U 641,659,701,719,739,751,821,839,929,971,1019,1039,1051,1091,1129,1171,1181,1201,1259,1301

%N Primes p with a Fibonacci primitive root g, i.e., such that g^2 = g + 1 (mod p).

%C Primes p with a primitive root g such that g^2 = g + 1 (mod p).

%C Not the same as primes with a Fibonacci number as primitive root; cf. A083701. - _Jonathan Sondow_, Feb 17 2013

%C For all except the initial term 5, these are numbers such that the Pisano period equals 1 less than the Pisano number, i.e., where A001175(n) = n-1. - _Matthew Goers_, Sep 20 2013

%C As shown in the paper by Brison, these are also the primes p such that there is a Fibonacci-type sequence (mod p) that begins with (1,b) and encounters all numbers less than p in the first p-1 iterations (for some b). - _T. D. Noe_, Feb 26 2014

%C Shanks (1972) conjectured that the relative asymptotic density of this sequence in the sequence of primes is 27*c/38 = 0.2657054465..., where c is Artin's constant (A005596). The conjecture was proved on the assumption of a generalized Riemann hypothesis by Lenstra (1977) and Sander (1990). - _Amiram Eldar_, Jan 22 2022

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

%H Charles R Greathouse IV, <a href="/A003147/b003147.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Noe)

%H Bob Bastasz, <a href="https://www.fq.math.ca/Papers1/58-5/bastasz.pdf">Lyndon words of a second-order recurrence</a>, Fibonacci Quarterly, Vol. 58, No. 5 (2020), pp. 25-29.

%H Owen J. Brison, <a href="http://www.fq.math.ca/Scanned/30-4/brison.pdf">Complete Fibonacci sequences in finite fields</a>, Fibonacci Quarterly, Vol. 30, No. 4 (1992), pp. 295-304.

%H Alexandru Gica, <a href="http://www.fq.math.ca/Papers1/46_47-1/Gica_11-08.pdf">Quadratic Residues in Fibonacci Sequences</a>, Fibonacci Quart., Vol. 46/47, No. 1 (2008/2009), pp. 68-72. See Theorem 5.1.

%H Liang-Chung Hsia, Hua-Chieh Li, and Wei-Liang Sun, <a href="https://arxiv.org/abs/2302.00920">Certain Diagonal Equations and Conflict-Avoiding Codes of Prime Lengths</a>, arXiv:2302.00920 [math.NT], 2023.

%H H. W. Lenstra, Jr., <a href="https://doi.org/10.1007/BF01389788">On Artin's conjecture and Euclid's algorithm in global fields</a>, Invent. Math., Vol. 42 (1977), pp. 202-224; <a href="https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1977d/art.pdf">alternative link</a>.

%H J. W. Sander, <a href="https://www.fq.math.ca/Scanned/28-1/sander.pdf">On Fibonacci primitive roots</a>, Fibonacci Quarterly, Vol. 28, No. 1 (1990), pp. 79-80.

%H Daniel Shanks, <a href="http://www.fq.math.ca/Scanned/10-2/shanks-a.pdf">Fibonacci primitive roots</a>, <a href="http://www.fq.math.ca/Scanned/10-2/shanks-b.pdf">end of article</a>, Fibonacci Quarterly, Vol. 10, No. 2 (1972), pp. 163-168, 181.

%H Daniel Shanks and Larry Taylor, <a href="https://www.fq.math.ca/Scanned/11-2/shanks.pdf">An Observation of Fibonacci Primitive Roots</a>, Fibonacci Quarterly, Vol. 11, No. 2 (1973), pp. 159-160.

%H <a href="/index/Pri#primes_root">Index entries for primes by primitive root</a>.

%e 3 is a primitive root mod 5, and 3^2 = 3 + 1 mod 5, so 5 is a member. - _Jonathan Sondow_, Feb 17 2013

%p filter:=proc(n) local g,r;

%p if not isprime(n) then return false fi;

%p r:= [msolve(g^2 -g - 1, n)][1];

%p numtheory:-order(rhs(op(r)),n) = n-1

%p end proc:

%p select(filter, [5,seq(seq(10*i+j,j=[1,9]),i=1..1000)]); # _Robert Israel_, May 22 2015

%t okQ[p_] := AnyTrue[PrimitiveRootList[p], Mod[#^2, p] == Mod[#+1, p]&]; Select[Prime[Range[300]], okQ] (* _Jean-François Alcover_, Jan 04 2016 *)

%o (PARI) is(n)=if(kronecker(5,n)<1||!isprime(n), return(n==5)); my(s=sqrt(Mod(5,n))); znorder((1+s)/2)==n-1 || znorder((1-s)/2)==n-1 \\ _Charles R Greathouse IV_, May 22 2015

%Y Subsequence of A038872.

%Y Cf. A001175, A005596, A083701.

%Y See also A106535.

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_

%E Cross-reference from _Charles R Greathouse IV_, Nov 05 2009

%E Definition clarified by _M. F. Hasler_, Jun 05 2018