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!)
A214876 Prime numbers for which there is a primitive root g for which the iteration x -> g^x (mod p) generates all nonzero residues (mod p). 1
3, 5, 23, 41, 59, 61, 107, 139, 149, 173, 181, 233, 239, 251, 269, 281, 311, 331, 349, 359, 389, 397, 439, 457, 461, 463, 467, 487, 509, 547, 577, 587, 647, 653, 719, 751, 769, 809, 811, 829, 877, 883, 907, 919, 941, 967, 1039, 1069, 1097, 1103, 1109, 1213 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Recent works by Holden, Pomerance et al. have established that for every prime p>2 there is a primitive root g modulo p which has a fixed point: g^x = x (mod p). This sequence shows in fact not every prime has a primitive root which generates all nonzero residues by iterated exponentiation. This sequence may have applications to random number generation, where long periods are usually required.

LINKS

Alasdair McAndrew, Table of n, a(n) for n = 1..1884

M. Levin, C Pomerance, and K. Soundararajan, Fixed points for discrete logarithms, Lecture Notes in Computer Science, 2010, Volume 6197, Algorithmic Number Theory, pages 6-15.

MATHEMATICA

testcyclic[p_] := (g = 1; out = False; While[out == False && g < p-2, g += 1; If[ MultiplicativeOrder[g, p] == p-1, x = g; c = 1; While[x != 1, x = PowerMod[g, x, p]; c += 1]; If[c == p-1, out = True]]]; Return[out]);

testcyclic[3] = True;

Reap[ Do[ If[ testcyclic[p], Print[p]; Sow[p]], {p, Prime /@ Range[200]}]][[2, 1]]

(* Jean-François Alcover, Sep 17 2012, translated from Sage *)

PROG

(Sage)

def testcyclic(p):

if p == 3: return True

g = 1

out = False

while not out and g<p-2:

g += 1

if mod(g, p).multiplicative_order()==p-1:

x = g

c = 1

while (x != 1):

x = power_mod(g, x, p)

c += 1

if c==p-1:

out = True

return out

for p in primes(400):

if testcyclic(p): print(p)

(PARI) has(g)=my(x=g); for(i=4, g.mod, x=g^lift(x); if(x==1, return(0))); 1

is(n)=if(!isprime(n), return(0)); my(r=znprimroot(n), g=1); for(k=1, n, g*=r; if(gcd(k, n-1)==1 && has(g), return(n>2))); 0 \\ Charles R Greathouse IV, Jul 31 2016

CROSSREFS

Sequence in context: A215132 A091157 A199336 * A280273 A036952 A065720

Adjacent sequences: A214873 A214874 A214875 * A214877 A214878 A214879

KEYWORD

nonn,nice

AUTHOR

Alasdair McAndrew, Jul 28 2012

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 February 5 20:57 EST 2023. Contains 360087 sequences. (Running on oeis4.)