A328919 Smallest index m such that from the m-th term on, the sequence {sigma_k(n) mod n: k >= 0} enters into a cycle.

0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 0, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 2, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 3, 4, 1, 1, 1, 1, 1, 1

Offset: 1

Author

Jianing Song, Oct 31 2019

Keywords

• nonn

Comments

sigma_k(n) = Sum_{d|n} d^k.

It is easy to see that {sigma_k(n) mod n: k >= A051903(n)} is purely periodic, and the period divides psi(n) = A002322(n) (the Carmichael lambda). So we have a(n) <= A051903(n). The equality seems to hold for most n: it holds for 7125 n's in the range [1, 10000] and 70287 n's in the range [1, 100000]. The numbers n such that a(n) < A051903(n) are listed in A328930.

Conjecture: a(n) = 0 only for n = 1, 12. If {sigma_k(n) mod n: k >= 0} is purely periodic, then sigma_0(n) == sigma_psi(n)(n) (mod n). Let p be any prime divisor of n, write n = p^e*s, then sigma_0(n) = d(n) = (e+1)*d(s), sigma_psi(n)(n) == Sum_{d|n, gcd(d,p)=1} 1 = d(s) (mod p^e), d = A000005. So sigma_0(n) == sigma_psi(n)(n) (mod n) means that p^e divides e*d(s) for every p dividing n, which seems highly impossible for n > 12. Of course, this shows that a(n) cannot be 0 if n is squarefree, so a(n) = 1 for squarefree n.

Note that sigma_m(n) == sigma_(m+psi(n))(n) (mod n) does NOT mean the sequence {sigma_k(n) mod n: k >= 0} enters into a cycle from the m-th term on: for n = 112, psi(112) = 12, sigma_1(112) == sigma_13(n) (mod 112) == 24 (mod 112), but sigma_2(112) == 26 (mod 112) while sigma_14(112) == 82 (mod 112). Actually, a(112) = 3.

Every number occurs in this sequence, because a(p^e) = e for primes p. Conjecture: a(2^e) is always the earliest occurrence of e.

Examples

			{sigma_k(8) mod 8: k >= 0}: 4, 7, 5, (1). {sigma_k(8) mod 8: k >= 0} enters into the cycle (1) from the 3rd term on, so a(8) = 3.
{sigma_k(12) mod 12: k >= 0}: (6, 4). {sigma_k(12) mod 12: k >= 0} enters into the cycle (6, 4) from the very beginning, so a(12) = 0.
{sigma_k(24) mod 24: k >= 0}: 8, (12, 10). {sigma_k(24) mod 24: k >= 0} enters into the cycle (12, 10) from the 1st term on, so a(24) = 1.
{sigma_k(90) mod 90: k >= 0}: 12, (54, 40, 18, 76). {sigma_k(90) mod 90: k >= 0} enters into the cycle (54, 40, 18, 76) from the 1st term on, so a(90) = 1.
		

Crossrefs

Cf. A051903, A328930, A002322, A000005.

Cf. A000203 (sigma), A013960 (sigma_12).

Programs

PARI

sigmamod(k,n) = my(d=divisors(n)); lift((sum(i=1, #d, Mod(d[i],n)^k))%n)
a(n) = forstep(k=A051903(n)-1, 0, -1, if(sigmamod(k,n)!=sigmamod(k+A002322(n),n), return(k+1))); return(0) \\ See A002322 and A051903 for their programs