A333909 Numbers k such that phi(k) is the sum of 2 squares, where phi is the Euler totient function (A000010).

1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 15, 16, 17, 19, 20, 22, 24, 25, 27, 30, 32, 33, 34, 37, 38, 40, 41, 44, 48, 50, 51, 53, 54, 55, 57, 59, 60, 63, 64, 66, 68, 73, 74, 75, 76, 80, 82, 83, 85, 88, 91, 95, 96, 100, 101, 102, 106, 107, 108, 110, 111, 114, 117, 118, 120

Offset: 1

Author

Amiram Eldar, Apr 09 2020

Keywords

• nonn

Examples

			1 is a term since phi(1) = 1 = 0^2 + 1^2.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• William D. Banks, Florian Luca, Filip Saidak, and Igor E. Shparlinski, Values of arithmetical functions equal to a sum of two squares, Quarterly Journal of Mathematics, Vol. 56, No. 2 (2005), pp. 123-139, alternative link.

Crossrefs

Cf. A000010, A001481, A039770, A079545, A333910, A333911, A333912.

Programs

Mathematica

Select[Range[120], SquaresR[2, EulerPhi[#]] > 0 &]

Python

from itertools import count, islice
from sympy import factorint, totient
def A333909_gen(): # generator of terms
    return filter(lambda n:all(p & 3 != 3 or e & 1 == 0 for p, e in factorint(totient(n)).items()),count(1))
A333909_list = list(islice(A333909_gen(),30)) # Chai Wah Wu, Jun 27 2022

Formula

c1 * x/log(x)^(3/2) < N(x) < c2 * x/log(x)^(3/2), where N(x) is the number of terms <= x, and c1 and c2 are two positive constants (Banks et al., 2005).