

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.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



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, n1, Mod(m, n)^k == m)/sum(m=0, n1, Mod(m, n)^k == m); \\ A334006
vec(n) = vecsort(vector(n, k, T(n, k1)), , 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



KEYWORD

nonn


AUTHOR



STATUS

approved



