A286510 Number of primitive roots g mod prime(n) for which there is no solution to g^x == x (mod p) with 2 <= x <= prime(n)-2.

1, 1, 1, 1, 2, 1, 1, 3, 4, 2, 1, 6, 5, 2, 9, 11, 12, 5, 7, 9, 8, 8, 17, 12, 11, 16, 12, 23, 20, 16, 17, 17, 23, 17, 26, 18, 19, 25, 26, 32, 38, 21, 21, 18, 27, 25, 24, 27, 52, 30, 44, 33, 19, 44, 54, 45, 57, 14, 29, 27, 39, 58, 28, 41, 39, 62, 26, 25, 69, 48, 51, 61, 44, 47, 37, 63, 77, 55, 55, 41

Offset: 1

Author

Robert Israel, May 10 2017

Keywords

• nonn

Links

• Robert Israel, Table of n, a(n) for n = 1..1000
• M. Levin, C. Pomerance, K. Soundararajan, Fixed Points for Discrete Logarithms. In: Hanrot G., Morain F., Thomé E. (eds) Algorithmic Number Theory. ANTS 2010. Lecture Notes in Computer Science, vol 6197. Springer, Berlin, Heidelberg (2010).
• Math Overflow, Fixed points of g^x (modulo a prime)

Crossrefs

Cf. A008330, A174407.

Programs

Maple

f:= proc(n) local p, r, S, R,x;
   p:= ithprime(n);
   r:= numtheory:-primroot(p);
   S:= select(t -> igcd(t,p-1) = 1, {$1..p-1});
   R:= map(s -> r &^ s mod p, S);
   for x from 2 to p-2 do
     R:= remove(t -> (t &^ x - x mod p = 0), R);
   od;
   nops(R);
end proc;
map(f, [$1..100]);

Mathematica

Join[{1}, Table[p = Prime[n]; EulerPhi[EulerPhi[p]] - Length[Select[ PrimitiveRootList[p], MemberQ[PowerMod[#, Range[p-1], p] - Range[p-1], 0] &]], {n, 2, 100}]] (* Jean-François Alcover, Oct 11 2020, after T. D. Noe in A174407 *)

Formula

a(n) = A008330(n) - A174407(n) for n >= 2.