A039770 Numbers k such that phi(k) is a perfect square.

1, 2, 5, 8, 10, 12, 17, 32, 34, 37, 40, 48, 57, 60, 63, 74, 76, 85, 101, 108, 114, 125, 126, 128, 136, 160, 170, 185, 192, 197, 202, 204, 219, 240, 250, 257, 273, 285, 292, 296, 304, 315, 364, 370, 380, 394, 401, 432, 438, 444, 451, 456, 468, 489, 504, 505

Offset: 1

Author

Olivier Gérard

Keywords

• nonn
• easy
• nice
• changed

Comments

A004171 is a subsequence because phi(2^(2k+1)) = (2^k)^2. - Enrique Pérez Herrero, Aug 25 2011

Subsequence of primes is A002496 since in this case phi(k^2+1) = k^2. - Bernard Schott, Mar 06 2023

Products of distinct terms of A002496 form a subsequence. - Chai Wah Wu, Aug 22 2025

Examples

			phi(34) = 16 = 4*4.
		

References

• D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston MA, 1976, p. 141.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• W. D. Banks, J. B. Friedlander, C. Pomerance and I. E. Shparlinski, Multiplicative structure of values of the Euler function, in High Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams (A. Van der Poorten, ed.), Fields Inst. Comm. 41 (2004), pp. 29-47.
• P. Pollack and C. Pomerance, Square values of Euler's function, submitted for publication.
• Bernard Schott, Subfamilies and subsequences

Crossrefs

Cf. A000010, A007614. A062732 gives the squares. A306882 (squares not totient).

Cf. A068560, A114063, A078164.

Subsequences: A054755, A002496, A004171, A262406, A324745, A324746, A247129, A324747, A306908.

Programs

Maple

with(numtheory); isA039770 := proc (n) return issqr(phi(n)) end proc; seq(`if`(isA039770(n), n, NULL), n = 1 .. 505); # Nathaniel Johnston, Oct 09 2013

Mathematica

Select[ Range[ 600 ], IntegerQ[ Sqrt[ EulerPhi[ # ] ] ]& ]

PARI

for(n=1, 120, if (issquare(eulerphi(n)), print1(n, ", ")))

Python

from math import isqrt
from sympy import totient as phi
def ok(n): return isqrt(p:=phi(n))**2 == p
print([k for k in range(1, 506) if ok(k)]) # Michael S. Branicky, Aug 17 2025

Formula

a(n) seems to be asymptotic to c*n^(3/2) with 1 < c < 1.3. - Benoit Cloitre, Sep 08 2002

Banks, Friedlander, Pomerance, and Shparlinski show that a(n) = O(n^1.421). - Charles R Greathouse IV, Aug 24 2009