cp's OEIS Frontend

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.

%I A336664 #25 Dec 13 2021 16:12:56
%S A336664 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,
%T A336664 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,
%U A336664 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
%N 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.
%C A336664 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.
%C A336664 For n >= 1, minimal d is equal to 1 and maximal d is equal to A026741(n).
%C A336664 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.
%H A336664 Antti Karttunen, <a href="/A336664/b336664.txt">Table of n, a(n) for n = 1..3755</a>
%e A336664 For n = 1 the a(1) = 1 solution d is 1 (k = 0),
%e A336664 n = 2 the a(2) = 1 solution d is 1 (k = 0),
%e A336664 n = 3 the a(3) = 2 solutions d are 1 (k = 0) and 3 (k = 1),
%e A336664 n = 4 the a(4) = 2 solutions d are 1 (k = 0) and 2 (k = 1),
%e A336664 n = 5 the a(5) = 2 solutions d are 1 (k = 0) and 5 (k = 1),
%e A336664 n = 6 the a(6) = 2 solutions d are 1 (k = 0) and 3 (k = 1),
%e A336664 n = 7 the a(7) = 2 solutions d are 1 (k = 0) and 7 (k = 1),
%e A336664 n = 8 the a(8) = 2 solutions d are 1 (k = 0) and 4 (k = 1),
%e A336664 n = 9 the a(9) = 3 solutions d are 1 (k = 0), 3 (k = 3) and 9 (k = 1).
%o A336664 (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
%o A336664 vec(n) = vecsort(vector(n, k, T(n,k-1)),,8);
%o A336664 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
%Y A336664 Cf. A000010, A002322, A026741, A334006.
%K A336664 nonn
%O A336664 1,3
%A A336664 _Juri-Stepan Gerasimov_, Jul 29 2020