login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003147 Primes p with a Fibonacci primitive root g, i.e., such that g^2 = g + 1 (mod p).
(Formerly M3811)
17
5, 11, 19, 31, 41, 59, 61, 71, 79, 109, 131, 149, 179, 191, 239, 241, 251, 269, 271, 311, 359, 379, 389, 409, 419, 431, 439, 449, 479, 491, 499, 569, 571, 599, 601, 631, 641, 659, 701, 719, 739, 751, 821, 839, 929, 971, 1019, 1039, 1051, 1091, 1129, 1171, 1181, 1201, 1259, 1301 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
Primes p with a primitive root g such that g^2 = g + 1 (mod p).
Not the same as primes with a Fibonacci number as primitive root; cf. A083701. - Jonathan Sondow, Feb 17 2013
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
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
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
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from Noe)
Bob Bastasz, Lyndon words of a second-order recurrence, Fibonacci Quarterly, Vol. 58, No. 5 (2020), pp. 25-29.
Owen J. Brison, Complete Fibonacci sequences in finite fields, Fibonacci Quarterly, Vol. 30, No. 4 (1992), pp. 295-304.
Alexandru Gica, Quadratic Residues in Fibonacci Sequences, Fibonacci Quart., Vol. 46/47, No. 1 (2008/2009), pp. 68-72. See Theorem 5.1.
Liang-Chung Hsia, Hua-Chieh Li, and Wei-Liang Sun, Certain Diagonal Equations and Conflict-Avoiding Codes of Prime Lengths, arXiv:2302.00920 [math.NT], 2023.
H. W. Lenstra, Jr., On Artin's conjecture and Euclid's algorithm in global fields, Invent. Math., Vol. 42 (1977), pp. 202-224; alternative link.
J. W. Sander, On Fibonacci primitive roots, Fibonacci Quarterly, Vol. 28, No. 1 (1990), pp. 79-80.
Daniel Shanks, Fibonacci primitive roots, end of article, Fibonacci Quarterly, Vol. 10, No. 2 (1972), pp. 163-168, 181.
Daniel Shanks and Larry Taylor, An Observation of Fibonacci Primitive Roots, Fibonacci Quarterly, Vol. 11, No. 2 (1973), pp. 159-160.
EXAMPLE
3 is a primitive root mod 5, and 3^2 = 3 + 1 mod 5, so 5 is a member. - Jonathan Sondow, Feb 17 2013
MAPLE
filter:=proc(n) local g, r;
if not isprime(n) then return false fi;
r:= [msolve(g^2 -g - 1, n)][1];
numtheory:-order(rhs(op(r)), n) = n-1
end proc:
select(filter, [5, seq(seq(10*i+j, j=[1, 9]), i=1..1000)]); # Robert Israel, May 22 2015
MATHEMATICA
okQ[p_] := AnyTrue[PrimitiveRootList[p], Mod[#^2, p] == Mod[#+1, p]&]; Select[Prime[Range[300]], okQ] (* Jean-François Alcover, Jan 04 2016 *)
PROG
(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
CROSSREFS
Subsequence of A038872.
See also A106535.
Sequence in context: A274946 A253936 A191032 * A106068 A304875 A164566
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from David W. Wilson
Cross-reference from Charles R Greathouse IV, Nov 05 2009
Definition clarified by M. F. Hasler, Jun 05 2018
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:47 EDT 2024. Contains 370951 sequences. (Running on oeis4.)