A384239 The number of primes p <= n such that p^p == p (mod n).

0, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 4, 2, 2, 3, 3, 2, 3, 2, 5, 3, 1, 1, 8, 1, 2, 1, 3, 2, 6, 1, 2, 3, 2, 4, 5, 1, 4, 3, 8, 2, 7, 3, 5, 5, 1, 1, 10, 4, 3, 2, 4, 1, 3, 3, 8, 4, 3, 1, 11, 3, 3, 7, 3, 5, 6, 2, 3, 3, 7, 1, 11, 2, 2, 5, 5, 6, 7, 1, 12, 3, 4, 1, 14, 2, 4, 5, 8, 2, 11

Offset

1,6

Links

Table of n, a(n) for n=1..90.

Example

a(4) = 1 because not 2^2 = 2 (mod 4) and 3^3 = 27 == 3 (mod 4), where 2 and 3 are primes p <= 4.

Prog

(Magma) [(IsPrime(n) select 1 else 0) + #[p: p in PrimesUpTo(n) | Modexp(p, p, n) eq p]: n in [1..90]];
(PARI) a(n) = #select(x->(Mod(x, n)^x == x), primes([1, n])); \\ Michel Marcus, May 23 2025
(Python)
from sympy import sieve
def a(n): return int(n in sieve) + sum(1 for p in sieve.primerange(1, n+1) if pow(p, p, n) == p)
print([a(n) for n in range(1, 91)]) # Michael S. Branicky, May 23 2025

Crossrefs

Cf. A010051, A000720.

Sequence in context: A353278 A328917 A265917 * A057021 A152443 A373368

Adjacent sequences: A384236 A384237 A384238 * A384240 A384241 A384242

Keyword

nonn

Author

Juri-Stepan Gerasimov, May 22 2025

Status

approved