|
%I #36 Mar 14 2020 16:52:51
%S 3,5,23,41,59,61,107,139,149,173,181,233,239,251,269,281,311,331,349,
%T 359,389,397,439,457,461,463,467,487,509,547,577,587,647,653,719,751,
%U 769,809,811,829,877,883,907,919,941,967,1039,1069,1097,1103,1109,1213
%N 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).
%C 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.
%H Alasdair McAndrew, <a href="/A214876/b214876.txt">Table of n, a(n) for n = 1..1884</a>
%H M. Levin, C Pomerance, and K. Soundararajan, <a href="http://www.math.dartmouth.edu/~carlp/brizolisants.pdf">Fixed points for discrete logarithms</a>, Lecture Notes in Computer Science, 2010, Volume 6197, Algorithmic Number Theory, pages 6-15.
%t 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]);
%t testcyclic[3] = True;
%t Reap[ Do[ If[ testcyclic[p], Print[p]; Sow[p]], {p, Prime /@ Range[200]}]][[2, 1]]
%t (* _Jean-François Alcover_, Sep 17 2012, translated from Sage *)
%o (Sage)
%o def testcyclic(p):
%o if p == 3: return True
%o g = 1
%o out = False
%o while not out and g<p-2:
%o g += 1
%o if mod(g,p).multiplicative_order()==p-1:
%o x = g
%o c = 1
%o while (x != 1):
%o x = power_mod(g,x,p)
%o c += 1
%o if c==p-1:
%o out = True
%o return out
%o for p in primes(400):
%o if testcyclic(p): print(p)
%o (PARI) has(g)=my(x=g); for(i=4,g.mod, x=g^lift(x); if(x==1, return(0))); 1
%o 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
%K nonn,nice
%O 1,1
%A _Alasdair McAndrew_, Jul 28 2012
|
