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

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.

Links

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

Example

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

Prog

(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

Crossrefs

Cf. A000010, A002322, A026741, A334006.

Sequence in context: A351399 A024708 A096917 * A335108 A359238 A378309

Adjacent sequences: A336661 A336662 A336663 * A336665 A336666 A336667

Keyword

nonn

Author

Juri-Stepan Gerasimov, Jul 29 2020

Status

approved