login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Numbers n > 1 such that phi(n) <= phi(k) + phi(n-k) for all 1 <= k <= n-1, where phi(n) is the Euler totient function (A000010).
0

%I #6 Dec 01 2018 08:30:08

%S 2,3,4,6,10,12,18,24,30,42,60,84,90,120,150,180,210,330,390,420,630,

%T 840,1050,1260,1470,1680,1890,2100,2310,2730,3570,3990,4620,5460,6930,

%U 8190,9240,10920,11550,13650,13860,16170,18480,20790,23100,25410,27720,30030

%N Numbers n > 1 such that phi(n) <= phi(k) + phi(n-k) for all 1 <= k <= n-1, where phi(n) is the Euler totient function (A000010).

%C C. A. Nicol called these numbers "phi-subadditive" and the numbers n>1 such that phi(k) + phi(n-k) <= phi(n) for all 1 <= k <= n-1 "phi-superadditive", and propose the problem of proving that both sequences are infinite. Foster proved that all the primes > 3 are phi-superadditive and that all the primorials (A002110, except 1) are phi-subadditive.

%C Apparently the same as A244052 if n > 2.

%D J. Sandor and B. Crstici, Handbook of Number Theory II, Springer Verlag, 2004, Chapter 3.3, p. 224.

%H C. A. Nicol, <a href="https://www.jstor.org/stable/2318228">Problem E2590</a>, The American Mathematical Monthly, Vol. 83, No. 4 (1976), p. 284, <a href="https://www.jstor.org/stable/2321026">solution</a> by Lorraine L. Foster, Vol. 84, No. 8 (1977), p. 654-655.

%e 6 is in the sequence since phi(k) + phi(6-k) = 5, 3, 4, 3, 5 for k = 1 to 5 are all larger than phi(6) = 2.

%t aQ[n_] := Module[{e=EulerPhi[n]}, LengthWhile[Range[1,n-1], EulerPhi[n-#] + EulerPhi[#] >= e &] == n-1]; Select[Range[2, 10000], aQ]

%o (PARI) isok(n) = {if (n == 1, return(0)); my(t = eulerphi(n)); for (k=1, n-1, if (t > eulerphi(k) + eulerphi(n-k), return(0));); return (1);} \\ _Michel Marcus_, Nov 29 2018

%Y Cf. A000010, A002110, A244052.

%K nonn

%O 1,1

%A _Amiram Eldar_, Nov 29 2018