A247129 -id:A247129 - 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

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

A307245 First occurrence of n in A306722.

Original entry on oeis.org

11, 1, 3, 10, 27, 60, 72, 120, 180, 270, 480, 252, 1155, 720, 792, 1260, 630, 1050, 4590, 1680, 1320, 7980, 3780, 4680, 5880, 5040, 5460, 4620, 9180, 10080, 10710, 6930, 9240, 7560, 21420, 20790, 27300, 52080, 15120, 13860, 48510, 23940, 62370, 46200, 16380, 30030

Offset: 0

Bernard Schott and Robert G. Wilson v, Mar 30 2019

nonn

Record values: 11, 27, 60, 72, 120, 180, 270, 480, 1155, 1260, 4590, 7980, 9180, 10080, 10710, 21420, 27300, 52080, 62370, 191520, 207480, 214200, 428400, ..., .

			a(0) = 11  because (2*11)^2 = 484 is the smaller integer that can't be written as (p-1)*(q-1) with p,q primes, p < q.
a(3) = 10 because (2*10)^2 = 400 is the smaller integer such that the Diophantine equation (p-1)*(q-1) = 400 has three solutions: (p,q) = (2,401) = (5,101) = (11,41); also, phi(2*401) = phi(5*101) = phi(11*41) = 20^2.

Robert G. Wilson v, Table of n, a(n) for n = 0..876

Cf. A039770, A247129, A306722.

f[n_] := Length@ Select[ Divisors[ 4n^2], # < 2n && PrimeQ[# +1] && PrimeQ[4n^2/# +1] &]; t[_] := 0; k = 1; While[k < 100000, a = f@k; If[t[a] == 0, t[a] = k]; k++]; t@# & /@ Range[0, 50]

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

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

A307245 First occurrence of n in A306722.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica