|
|
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).
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|