A371883 a(n) is the number of divisors d of n such that d^n mod n = d.

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 2, 1, 4, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 3, 4, 1, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 3, 1, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 3, 2, 1, 2, 2, 2, 1, 1, 2, 1, 2

Offset

1,6

Comments

1 <= a(n) < A000005(n) for n >= 2.

Links

Antti Karttunen, Table of n, a(n) for n = 1..16384

Example

a(1) = 0: 1 divides 1, but 1^1 mod 1 = 0 (not 1).
a(2) = 1: 1 divides 2, and 1^2 mod 2 = 1;
          2 divides 2, but 2^2 mod 2 = 0 (not 2).
a(6) = 2: 1 divides 6, and 1^6 mod 6 = 1;
          2 divides 6, but 2^6 mod 6 = 4 (not 2);
          3 divides 6, and 3^6 mod 6 = 3;
          6 divides 6, but 6^6 mod 6 = 0 (not 6).

Mathematica

a[n_] := DivisorSum[n, 1 &, PowerMod[#, n, n] == # &]; Array[a, 100] (* Amiram Eldar, Apr 11 2024 *)

Prog

(Magma) [#[d: d in Divisors(n) | d^n mod n eq d]: n in [1..100]];
(Python)
from sympy import divisors
def a(n): return sum(1 for d in divisors(n)[:-1] if pow(d, n, n) == d)
print([a(n) for n in range(1, 101)]) # Michael S. Branicky, Apr 10 2024
(PARI) a(n) = sumdiv(n, d, d^n % n == d); \\ Michel Marcus, Apr 20 2024

Crossrefs

Cf. A000005, A182816, A279024, A371513, A371884.

Sequence in context: A328512 A302041 A302031 * A237353 A293460 A231813

Adjacent sequences: A371880 A371881 A371882 * A371884 A371885 A371886

Keyword

nonn

Author

Juri-Stepan Gerasimov, Apr 10 2024

Status

approved