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).

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

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