cp's OEIS Frontend

A307640 Least number k such that n divides gcd(sigma(k), phi(k), tau(k)).

%I A307640 #29 Feb 20 2022 20:25:39
%S A307640 1,3,18,15,3344,45,24128,30,882,3344,1012736,126,1953792,24128,16200,
%T A307640 168,452263936,2016,1852571648,3344,40768,1012736,27007123456,420,
%U A307640 1490000,1953792,103968,24128,2739920699392,30096,8348342681600,840,9114624,452263936,6163776,2016
%N A307640 Least number k such that n divides gcd(sigma(k), phi(k), tau(k)).
%C A307640 For each n >= 1 there are infinitely many numbers s such that n divides sigma(s), phi(s) and tau(s).
%C A307640 From Dirichlet's theorem there are infinitely many numbers m for which the numbers p = n*m + 1 are prime. Then sigma(p^(n-1)), phi(p^(n-1)) and tau(p^(n-1)) numbers are divisible by n.
%D A307640 Laurențiu Panaitopol, Alexandru Gica, Arithmetic problems and number theory. Ideas and methods of solving, Ed. Gil, Zalău, 2006, ch. 13, p. 79, pr. 18. (in Romanian).
%e A307640 For n = 2, sigma(3) = 4, phi(3) = 2, tau(3) = 4 are divisible by 2.
%e A307640 For n = 5, sigma(3344) = 7440, phi (3344) = 1440, tau (3344) = 20 are divisible by 5 and by 10.
%e A307640 For n = 11, sigma(1012736) = 2161632 = 11 * 196512, phi(1012736) = 11 * 43008, tau(1012736) = 11 * 4 are divisible by 11.
%t A307640 Array[Block[{i = 1}, While[Mod[GCD[DivisorSigma[1, i], EulerPhi@ i,DivisorSigma[0, i]], #] != 0, i++]; i] &, 16] (*Adaptation after A222713*)
%o A307640 (Magma) for m in [1..16] do
%o A307640       for n in [1..2000000] do
%o A307640               if IsIntegral(SumOfDivisors(n)/m) and IsIntegral(EulerPhi(n)/m) and IsIntegral(NumberOfDivisors(n)/m) then
%o A307640              m,n;
%o A307640              break;
%o A307640             end if;
%o A307640       end for;
%o A307640 end for;
%o A307640 (PARI) isok(n,k) = ! frac(gcd(sigma(k), gcd(eulerphi(k), numdiv(k)))/n);
%o A307640 a(n) = my(k=1); while(!isok(n,k), k++); k; \\ _Michel Marcus_, Apr 20 2019
%o A307640 (PARI) a(n) = {if(n==1,return(1)); my(res = oo, f = factor(n), hpf = f[#f~, 1]); forprime(p = 2, oo, if(p ^ (hpf - 1) > res, return(res)); forstep(i = p ^ (hpf - 1), res, p ^ (hpf - 1), if(isok(n, i), res = min(res, i);  next(2) ) ) ) } \\ uses isok from above \\ _David A. Corneth_, Apr 22 2019
%Y A307640 Cf. A000005, A000010, A000203, A009223, A222713.
%K A307640 nonn
%O A307640 1,2
%A A307640 _Marius A. Burtea_, Apr 19 2019
%E A307640 More terms from _David A. Corneth_, Apr 21 2019