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,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

Table of n, a(n) for n=1..48.

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

Cf. A000010, A002110, A244052.

Sequence in context: A181312 A330006 A288784 * A237823 A241547 A273542

Adjacent sequences: A322161 A322162 A322163 * A322165 A322166 A322167

Keyword

nonn

Author

Amiram Eldar, Nov 29 2018

Status

approved