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
KEYWORD
nonn,nice
AUTHOR
Alasdair McAndrew, Jul 28 2012
STATUS
approved