A174407 The number of primitive roots g such that there exists an x with g^x == x (mod p), where p=prime(n).

1, 0, 1, 1, 2, 3, 7, 3, 6, 10, 7, 6, 11, 10, 13, 13, 16, 11, 13, 15, 16, 16, 23, 28, 21, 24, 20, 29, 16, 32, 19, 31, 41, 27, 46, 22, 29, 29, 56, 52, 50, 27, 51, 46, 57, 35, 24, 45, 60, 42, 68, 63, 45, 56, 74, 85, 75, 58, 59, 69, 53, 86, 68, 79, 57, 94, 54, 71, 103, 64, 109, 117, 76

Offset

1,5

Comments

a(n) is the number of primitive roots g of p=prime(n) for which an x with 0 < x < p exists such that g^x == x (mod p). - Robert Israel, May 12 2017 [Corrected by Tim Peters (following an observation made by José Hernández), Apr 16 2024]

The number x is called a fixed point of the discrete logarithm with base g.

Links

Robert Israel, Table of n, a(n) for n = 1..1000

M. Levin, C. Pomerance, and K. Soundararajan, Fixed Points for Discrete Logarithms. In: G. Hanrot, F. Morain, and E. Thomé (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).

Maple

g:= 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;
   numtheory:-phi(p-1)-nops(R);
end proc:
g(1):= 1:
map(g, [$1..100]); # Robert Israel, May 12 2017

Mathematica

Table[p = Prime[n]; Length[Select[PrimitiveRootList[p], MemberQ[PowerMod[#, Range[p-1], p] - Range[p-1], 0]&]], {n, 1, 100}] (* updated by Jean-François Alcover, Oct 11 2020 *)

Prog

(PARI) apply( {A174407(n, p=prime(n), s=0)=for(r=1, p-1, my(g=Mod(r, p)); if(znorder(g)==p-1, for(x=1, p-1, g^x==x && s++ && next(2)))); s}, [1..99]) \\ quite inefficient code, for illustration. - M. F. Hasler, Apr 15 2024

Crossrefs

Cf. A174329 and A174330 (least g and x for each p).

Sequence in context: A096389 A054144 A226985 * A160727 A187152 A086508

Adjacent sequences: A174404 A174405 A174406 * A174408 A174409 A174410

Keyword

nonn

Author

T. D. Noe, Mar 18 2010

Extensions

Definition edited, and a(1) and a(2) inserted, by Robert Israel, May 12 2017

Status

approved