A372772 a(n) is the number of divisors d of n such that d^n mod n = k, where k is also a divisor of n.

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

Offset: 1

Author

Juri-Stepan Gerasimov, May 12 2024

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A371883.

Programs

Magma

[&+[#[d: d in Divisors(n) | d^n mod n eq k and n mod k eq 0]: k in [1..n]]: n in [1..100]];

Mathematica

a[n_] := DivisorSum[n, 1 &, (m = PowerMod[#, n, n]) > 0 && Divisible[n, m] &]; Array[a, 100] (* Amiram Eldar, May 13 2024 *)

PARI

A372772(n) = { my(k); sumdiv(n, d, k=lift(Mod(d^n,n)); k > 0 && 0==(n%k)); }; \\ Antti Karttunen, May 13 2024

Python

from sympy import divisors
def a(n):
    divs = set(divisors(n)[:-1])
    return sum(1 for d in divs if pow(d, n, n) in divs)
print([a(n) for n in range(1, 101)]) # Michael S. Branicky, May 13 2024