A336664 Number of distinct divisors d of n with the property that d = (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) for some nonnegative k.

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

Offset: 1

Author

Juri-Stepan Gerasimov, Jul 29 2020

Keywords

• nonn

Comments

For any k >= 0, the value of (the number of nonnegative bases m < n such that m^k == m (mod n))/(the number of nonnegative bases m < n such that -m^k == m (mod n)) is the value of some part of n, and is equal or unequal to the value of some divisor of n. Starting with k = 2, these infinite sequences of the parts of n are periodic with a period equal to A002322(n) (or A000010(n)). Also these sequences are different, but among n there are pairs of numbers (1 and 2, 3 and 6, ...) for which they are the same.

For n >= 1, minimal d is equal to 1 and maximal d is equal to A026741(n).

If n: 1, 2, 3, 5, 6, 10, 15, 17, 30, 34, 51, 85, 102, ..., then d = (the number of nonnegative bases m < n such that m^k = m)/(the number of nonnegative bases m < n such that -m^k = m) for all nonnegative k.

Examples

			For n = 1 the a(1) = 1 solution d is 1 (k = 0),
n = 2 the a(2) = 1 solution d is 1 (k = 0),
n = 3 the a(3) = 2 solutions d are 1 (k = 0) and 3 (k = 1),
n = 4 the a(4) = 2 solutions d are 1 (k = 0) and 2 (k = 1),
n = 5 the a(5) = 2 solutions d are 1 (k = 0) and 5 (k = 1),
n = 6 the a(6) = 2 solutions d are 1 (k = 0) and 3 (k = 1),
n = 7 the a(7) = 2 solutions d are 1 (k = 0) and 7 (k = 1),
n = 8 the a(8) = 2 solutions d are 1 (k = 0) and 4 (k = 1),
n = 9 the a(9) = 3 solutions d are 1 (k = 0), 3 (k = 3) and 9 (k = 1).
		

Links

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

Crossrefs

Cf. A000010, A002322, A026741, A334006.

Programs

PARI

T(n, k) = sum(m=0, n-1, Mod(m, n)^k == m)/sum(m=0, n-1, Mod(-m, n)^k == m); \\ A334006
vec(n) = vecsort(vector(n, k, T(n,k-1)),,8);
a(n) = { my(v=vec(n)); sumdiv(n, d, vecsearch(v, d) != 0); }; \\ Michel Marcus, Aug 27 2020, edited for speed by Antti Karttunen, Dec 13 2021