login
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).
0
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,1
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.
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.
EXAMPLE
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.
MATHEMATICA
aQ[n_] := Module[{e=EulerPhi[n]}, LengthWhile[Range[1, n-1], EulerPhi[n-#] + EulerPhi[#] >= e &] == n-1]; Select[Range[2, 10000], aQ]
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Amiram Eldar, Nov 29 2018
STATUS
approved