login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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, 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,5
LINKS
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).
FORMULA
a(n) = A008330(n) - A174407(n) for n >= 2.
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 *)
CROSSREFS
Sequence in context: A056863 A120019 A145034 * A336842 A159933 A305431
KEYWORD
nonn
AUTHOR
Robert Israel, May 10 2017
STATUS
approved