A322164 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).

2, 3, 4, 6, 10, 12, 18, 24, 30, 42, 60, 84, 90, 120, 150, 180, 210, 330, 390, 420, 630, 840, 1050, 1260, 1470, 1680, 1890, 2100, 2310, 2730, 3570, 3990, 4620, 5460, 6930, 8190, 9240, 10920, 11550, 13650, 13860, 16170, 18480, 20790, 23100, 25410, 27720, 30030

Offset: 1

Author

Amiram Eldar, Nov 29 2018

Keywords

• nonn

Comments

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.

Apparently the same as A244052 if n > 2.

Examples

			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.
		

References

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

Links

• C. A. Nicol, Problem E2590, The American Mathematical Monthly, Vol. 83, No. 4 (1976), p. 284, solution by Lorraine L. Foster, Vol. 84, No. 8 (1977), p. 654-655.

Crossrefs

Cf. A000010, A002110, A244052.

Programs

Mathematica

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

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