%I #21 Dec 22 2021 07:03:16
%S 12,22,12,249,12,22,12,19689,12,22,12,249,12,22,12
%N Smallest k > 6 such that sigma_n(k)/phi(k) is an integer.
%C For n = 16, 48, 64, and 80 the solutions are hard to find, exceed 10^6 or even 10^7.
%C If a(16) exists, it is greater than 2^32. Terms a(17) to a(47) are 12, 22, 12, 249, 12, 22, 12, 9897, 12, 22, 12, 249, 12, 22, 12, 2566, 12, 22, 12, 249, 12, 22, 12, 19689, 12, 22, 12, 249, 12, 22, 12. - _T. D. Noe_, Dec 08 2013
%e These terms appear as 5th entries in A020492, A015759-A015774. k = {1, 2, 3, 6} are solutions to Min{k : Mod[sigma[n, k], phi[k]]=0}. First nontrivial solutions are larger: for odd n, k = 12 is solution; for even powers larger numbers arise like 22, 249, 9897, 19689, etc. Certain power-sums of divisors proved to be hard to find.
%t f[k_, x_] := DivisorSigma[k, x]/EulerPhi[x]; Table[fl=1; Do[s=f[k, n]; If[IntegerQ[s]&&Greater[n, 6], Print[{n, k}; fl=0], {n, 100000}, {k, 1, 100}]
%o (PARI) ok(n,k)=my(f=factor(n), r=sigma(f,k)/eulerphi(f)); r>=7 && denominator(r)==1
%o a(n)=my(k=7); while(!ok(k, n), k++); k \\ _Charles R Greathouse IV_, Nov 27 2013
%o (Python)
%o from sympy import divisors, totient as phi
%o def a(n):
%o k, pk = 7, phi(7)
%o while sum(pow(d, n, pk) for d in divisors(k, generator=True))%pk != 0:
%o k += 1
%o pk = phi(k)
%o return k
%o print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Dec 22 2021
%Y Cf. A000203, A001157, A001158, A000010, A015759-A015774, A020492.
%K hard,more,nonn
%O 1,1
%A _Labos Elemer_, Nov 29 2002