login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A174407 The number of primitive roots g such that there exists an x with g^x (mod p) = x, where p=prime(n). 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

a(n) is the number of x with 0 < x < p and g^x == x (mod p). - Robert Israel, May 12 2017

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

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]; coprimes=Select[Range[p-1], GCD[ #, p-1] == 1 &]; primRoots = PowerMod[PrimitiveRoot[p], coprimes, p]; Length[Select[primRoots, MemberQ[PowerMod[ #, Range[p-1], p] - Range[p-1], 0] &]], {n, 3, 100}]

CROSSREFS

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

Sequence in context: A054144 A110057 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 22:34 EST 2019. Contains 329323 sequences. (Running on oeis4.)