A062732 -id:A062732 - cp's OEIS frontend

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

Olivier Gérard

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

			phi(34) = 16 = 4*4.

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

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

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.

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

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

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

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

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

A280988 Least k such that phi(k*n) is a perfect square, or 0 if no such k exists.

Original entry on oeis.org

1, 1, 4, 2, 1, 2, 9, 1, 7, 1, 41, 1, 21, 9, 4, 2, 1, 6, 3, 2, 3, 41, 89, 2, 5, 14, 4, 13, 113, 2, 143, 1, 25, 1, 9, 3, 1, 2, 7, 1, 11, 3, 49, 25, 7, 89, 1151, 1, 43, 5, 4, 7, 553, 2, 15, 9, 1, 113, 233, 1, 77, 122, 1, 2, 21, 25, 299, 2, 356, 9, 281, 6, 3, 1, 11, 1, 61, 6, 313

Offset: 1

Altug Alkan, Jan 12 2017

nonn

Pollack and Pomerance proved that if phi(a) = b^m, then m = 2 occurs only on a set of density 0.

			a(11) = 41 because phi(k*11) is not a perfect square for 0 < k < 41 and phi(41*11) = 20^2.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Pollack and Carl Pomerance, Square values of Euler's function, Bulletin of the London Mathematical Society, Vol. 46, No. 2 (2014), pp. 403-414, alternative link.

Cf. A000010, A039770, A062732, A280986.

f:= proc(n) local k;
    for k from 1 do
      if issqr(numtheory:-phi(k*n)) then return k fi
   od
end proc:
map(f, [$1..100]); # Robert Israel, Jan 12 2017

a[n_] := Module[{k = 1}, While[!IntegerQ[Sqrt[EulerPhi[k*n]]], k++]; k]; Array[a, 80] (* Amiram Eldar, Jul 13 2019 *)

a(n) = {my(k = 1); while (!issquare(eulerphi(k*n)), k++); k; }

A324745 Numbers k with exactly two distinct prime factors and such that phi(k) is a square.

Original entry on oeis.org

10, 12, 34, 40, 48, 57, 63, 74, 76, 85, 108, 136, 160, 185, 192, 202, 219, 250, 292, 296, 304, 394, 432, 451, 489, 505, 513, 514, 544, 567, 629, 640, 652, 679, 768, 802, 808, 873, 972, 985, 1000, 1057, 1154, 1168, 1184, 1216, 1285, 1354

Offset: 1

Bernard Schott, Mar 12 2019

nonn

This sequence is the intersection of A007774 and A039770.
The sequences A324746 and A324747 form a partition of this sequence.
See the file "Subfamilies and subsequences" (& II) in A039770 for more details, proofs with data, comments, formulas and examples.
The integers with only one prime factor and whose totient is a square are in A054755.

			1st family: 136 = 2^3 * 37 and phi(136) = 8^2.
2nd family: 652 = 2^2 * 163 and phi(652) = 18^2.

Intersection of A007774 and A039770.

Cf. A054755, A062732, A221285, A324746, A324747.

filter:= n -> issqr(numtheory:-phi(n)) and nops(numtheory:-factorset(n))=2:
select(filter, [$1..2000]); # Robert Israel, Mar 18 2019

Select[Range[1400], And[PrimeNu[#] == 2, IntegerQ@ Sqrt@ EulerPhi@ #] &] (* Michael De Vlieger, Mar 21 2019 *)

isok(n) = (omega(n)==2) && issquare(eulerphi(n)); \\ Michel Marcus, Mar 17 2019

1st family (A324746): The primitive terms are defined by p*q, p < q, with phi(p*q) = (p-1)*(q-1) = m^2. The general terms are defined by k = p^(2s+1) * q^(2t+1), s,t >= 0, with phi(k) = (p^s * q^t * m)^2.

2nd family (A324747): The primitive terms are defined by p^2 * q, p <> q, with phi(p^2 * q) = p*(p-1)*(q-1) = m^2. The general terms are defined by k = p^(2s ) * q^(2t+1), s >= 1, t >= 0, with phi(k) = (p^(s-1) * q^t * m)^2.

A324746 Numbers k with exactly two distinct prime factors and such that phi(k) is square, when k = p^(2s+1) * q^(2t+1) with p < q primes, s,t >= 0.

Original entry on oeis.org

10, 34, 40, 57, 74, 85, 136, 160, 185, 202, 219, 250, 296, 394, 451, 489, 505, 513, 514, 544, 629, 640, 679, 802, 808, 985, 1000, 1057, 1154, 1184, 1285, 1354, 1387, 1417, 1576, 1717, 1971, 2005, 2047, 2056, 2125, 2176, 2509, 2560, 2594, 2649, 2761, 2885, 3097

Offset: 1

Bernard Schott, Mar 12 2019

nonn

An integer belongs to this sequence iff (p-1)*(q-1) = m^2.
This is the first subsequence of A324745, the second one is A324747.
Some values of (k,p,q,m): (10,2,5,2), (34,2,17,4), (40,2,5,4), (57,3,19,4), (74,2,37,6), (85,5,17,8).
The primitive terms of this sequence are the products p * q, with p < q which satisfy (p-1)*(q-1) = m^2; the first few are 10, 34, 57, 74, 85, 185. These primitives form exactly the sequence A247129. Then the integers (p*q) * p^2 and (p*q) * q^2 are new terms of the general sequence.
The number of semiprimes p*q whose totient is a square equal to (2*n)^2 can be found in A306722.

			629 = 17 * 37 and phi(629) = 16 * 36 = 9^2.
808 = 2^3 * 101 and phi(808) = (2^1 * 101^0 * 10)^2 = 20^2.

Cf. A039770, A062732, A221285, A054755, A324745, A324747, A306908.

Cf. A306722, A247129 (subsequence of primitives).

N:= 10^4:
Res:= {}:
p:= 1:
do
  p:= nextprime(p);
  if p^2 >= N then break fi;
  F:= ifactors(p-1)[2];
  dm:= mul(t[1]^ceil(t[2]/2),t=F);
  for j from (p-1)/dm+1 do
    q:= (j*dm)^2/(p-1) + 1;
    if q > N then break fi;
    if isprime(q) then Res:= Res union {seq(seq(
      p^(2*s+1)*q^(2*t+1),t=0..floor((log[q](N/p^(2*s+1))-1)/2)),
      s=0..floor((log[p](N/q)-1)/2))} fi
  od
od:
sort(convert(Res,list)); # Robert Israel, Mar 22 2019

Select[Range[6, 3100], And[PrimeNu@ # == 2, IntegerQ@ Sqrt@ EulerPhi@ #, IntegerQ@ Sqrt[Times @@ (FactorInteger[#][[All, 1]] - 1 )]] &] (* Michael De Vlieger, Mar 24 2019 *)

isok(k) = {if (issquare(eulerphi(k)), my(expo = factor(k)[,2]); if ((#expo == 2)&& (expo[1]%2) == (expo[2]%2), return (1)););} \\ Michel Marcus, Mar 18 2019

phi(p*q) = (p-1)*(q-1) = m^2 for primitive terms.

phi(k) = (p^s * q^t * m)^2 with k as in the name of this sequence.

A306722 Number of pairs of primes (p,q), p < q, which are a solution of the Diophantine equation (p-1)*(q-1) = (2n)^2.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 1, 1, 1, 3, 0, 3, 1, 1, 1, 1, 0, 3, 0, 3, 1, 1, 0, 3, 1, 1, 4, 3, 0, 3, 0, 1, 4, 0, 1, 3, 1, 0, 0, 3, 0, 3, 0, 1, 4, 0, 1, 3, 0, 1, 0, 1, 0, 2, 1, 2, 0, 2, 0, 5, 0, 1, 4, 0, 1, 4, 1, 0, 0, 4, 0, 6, 1, 1, 4, 0, 0, 5, 0, 4, 1

Offset: 1

Bernard Schott, Mar 06 2019

nonn

a(n) is also the number of semiprimes p*q whose totient is a square (A247129) and equal to (2*n)^2.
From Robert G. Wilson v, Mar 30 2019, Mar 30 2019: (Start)
First occurrence of k=1,2,3,...: 1, 3, 10, 27, 60, 72, 120, 180, 270, 480, 252, 1155, 720, 792, 1260, 630, ..., . = A307245.
Start of table:
a(k_i) = n:
\i  1   2   3   4   5   6    7    8    9   10   11   12   13   14   15  ...
n\
0  11  17  19  23  29  31   34   38   39   41   43   46   49   51   53  ...
1   1   2   4   5   7   8    9   13   14   15   16   21   22   25   26  ...
2   3   6  54  56  58  87  100  115  116  123  138  148  160  170  176  ...
3  10  12  18  20  24  28   30   36   40   42   48   84   88   99  144  ...
4  27  33  45  63  66  70   75   80  112  126  135  153  156  162  165  ...
5  60  78  90 102 140 168  200  260  264  285  288  315  378  408  432  ...
6  72 105 108 130 150 306  348  357  450  495  528  560  672  696  708  ...
7 120 132 240 297 312 330  390  588  750  882  980 1140 1176 1190 1215  ...
8 180 198 210 280 396 468  540  612  648  700  810  910  945  960 1020  ...
9 270 420 660 858 918 990 1248 1620 1782 1920 2088 2184 2352 2376 2688  ...
... (End).
If n is a prime <> 3, then a(n) = 1 if n is in A052291 and 0 otherwise, and a(n^2) = 1 if 2*n+1 and 2*n^3+1 are primes and 0 otherwise. - Robert Israel, Apr 04 2019

			a(2) = 1 because (2*2)^2 = (2-1) * (17-1), also, phi(2*17) = 4^2.
a(3) = 2 because (2*3)^2 = (2-1) * (37-1) = (3-1) * (19-1), also, phi(2*37) = phi(3*19) = 6^2.
a(11) = 0  because (2*11)^2 can't be written as (p-1)*(q-1) with p < q.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A039770, A052291, A062732, A221284, A221285, A247129, A306440, A307245.

f:= proc(n) local w;
  w:= (2*n)^2;
  nops(select(t -> t < 2*n and isprime(t+1) and isprime(w/t + 1),  numtheory:-divisors(w)))
end proc:
map(f, [$1..100]); # Robert Israel, Apr 04 2019

f[n_] := Length@ Select[ Divisors[ 4n^2], # < 2n && PrimeQ[# + 1] && PrimeQ[ 4n^2/# + 1] &]; Array[f, 81] (* Robert G. Wilson v, Mar 30 2019 *)

a(n) = {my(nb = 0, nn = 4*n^2); fordiv(nn, d, if (d == 2*n, break); if (isprime(d+1) && isprime(nn/d+1), nb++);); nb;} \\ Michel Marcus, Mar 06 2019

A216412 The cubes arising in A039771.

Original entry on oeis.org

1, 1, 8, 8, 8, 8, 8, 64, 64, 64, 64, 64, 64, 64, 64, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 512, 216, 216, 512, 512, 512, 1000, 1000, 512, 512, 1000, 512, 512, 512, 1728, 1728, 1000, 512, 1000, 512, 1728, 1000, 1728, 1728, 1000, 1000, 1728, 1728, 1000, 1728, 1728, 1000, 1728

Offset: 1

V. Raman, Sep 07 2012

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A039770, A039771, A039772, A062732, A078164, A166955.

Select[EulerPhi @ Range[3000], IntegerQ[Surd[#, 3]] &] (* Amiram Eldar, Mar 06 2020 *)

a(n) = A000010(A039771(n)). - Amiram Eldar, Mar 06 2020

A306882 Even numbers k such that phi(m) = k^2 has no solution.

Original entry on oeis.org

22, 34, 38, 46, 58, 62, 76, 78, 82, 86, 92, 98, 102, 106, 118, 122, 138, 142, 152, 154, 158, 164, 166, 172, 178, 182, 190, 194, 202, 212, 214, 218, 226, 238, 244, 254, 258, 262, 266, 274, 278, 282, 298, 302, 304, 310, 316, 318, 322, 328, 332, 334, 338, 344, 346, 356, 358, 362

Offset: 1

Bernard Schott, Mar 15 2019

nonn

In the link, P. Pollack and C. Pomerance "show that almost all squares are missing from the range of Euler's phi-function".
Except for m=1 and m=2, phi(m) is always even, so, the odd numbers >= 3 are not included in the data for clarity.
Includes 2*p if p is a prime not in A052291. - Robert Israel, Apr 10 2019

			phi(489) = 18^2, phi(401) = 20^2, phi(577) = 24^2, phi(677) = 26^2, but there is no integer m such that phi(m) = 22^2 = 484.

Robert Israel, Table of n, a(n) for n = 1..10000
P. Pollack and C. Pomerance, Square values of Euler's function, preprint (2013); Bulletin of the London Mathematical Society, Volume 46, Issue 2, 1 April 2014, Pages 403-414.

Cf. A000010, A002202, A052291, A058277, A062732, A221284, A221285.

select(t -> numtheory:-invphi(t^2)=[], [seq(i,i=2..400,2)]);  # Robert Israel, Apr 10 2019

isok(n) = !(n%2) && !istotient(n^2); \\ Michel Marcus, Mar 15 2019

A280986 Least k > 0 such that (k*n)^2 is in A002202, or 0 if no such k exists.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 4, 1, 6, 1, 2, 2, 8, 1, 2, 1, 2, 1, 4, 1, 4, 1, 2, 2, 2, 1, 2, 3, 4, 1, 6, 1, 10, 1, 2, 4, 2, 1, 4, 1, 4, 1, 8, 1, 2, 1, 2, 2, 4, 1, 12, 2, 2, 1, 2, 1, 2, 1, 4, 1, 4, 1, 2, 1, 2, 3, 4, 2, 6, 1, 2, 3, 8, 1, 2, 5, 2, 1, 6, 1, 4, 2, 2, 1, 4, 1, 8, 2, 2, 1

Offset: 1

Altug Alkan, Jan 12 2017

nonn

Pollack and Pomerance showed that almost all squares are missing from the range of Euler's totient function.

			a(11) = 4 because (k*11)^2 is not in A002202 for 0 < k < 4 and (4*11)^2 is in A002202.
a(95911) = 56 because (k*95911)^2 is not in A002202 for 0 < k < 56 and (56*95911)^2 is in A002202.

P. Pollack and C. Pomerance, Square values of Euler's function

Cf. A000010, A002202, A039770, A062732, A280988.

a(n) = {my(k = 1); while (!istotient((k*n)^2), k++); k; }

A216452 The fourth roots of the fourth powers arising in A078164.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 8, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 10, 8, 8, 8, 10, 8, 10, 8, 8, 8, 10, 10, 10, 12, 12, 12, 12, 10, 12

Offset: 1

V. Raman, Sep 07 2012

nonn

Cf. A039770, A039771, A039772, A062732, A078164, A166955.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A280988 Least k such that phi(k*n) is a perfect square, or 0 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A324745 Numbers k with exactly two distinct prime factors and such that phi(k) is a square.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A324746 Numbers k with exactly two distinct prime factors and such that phi(k) is square, when k = p^(2s+1) * q^(2t+1) with p < q primes, s,t >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A306722 Number of pairs of primes (p,q), p < q, which are a solution of the Diophantine equation (p-1)*(q-1) = (2n)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A216412 The cubes arising in A039771.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A306882 Even numbers k such that phi(m) = k^2 has no solution.

Views

Author

Keywords

Comments

Examples

Links