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

Links

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

Example

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

Mathematica

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

Prog

(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]];
(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

Crossrefs

Cf. A371883.

Sequence in context: A322373 A332288 A335450 * A324191 A373957 A238946

Adjacent sequences: A372769 A372770 A372771 * A372773 A372774 A372775

Keyword

nonn

Author

Juri-Stepan Gerasimov, May 12 2024

Status

approved