A039770 -id:A039770 - cp's OEIS frontend

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.

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.

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

Original entry on oeis.org

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

Amiram Eldar, Apr 09 2020

nonn

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

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.

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

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

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

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).

A236386 Numbers m such that phi(m) is an oblong number.

Original entry on oeis.org

3, 4, 6, 7, 9, 13, 14, 18, 21, 25, 26, 28, 31, 33, 36, 42, 43, 44, 49, 50, 62, 66, 73, 86, 87, 91, 95, 98, 111, 116, 117, 121, 135, 146, 148, 152, 157, 161, 169, 174, 182, 190, 201, 207, 211, 216, 222, 228, 234, 237, 241, 242, 252, 268, 270, 287, 289, 305

Offset: 1

Joseph L. Pe, Jan 24 2014

An oblong number (A002378) is of the form k*(k+1) where k is a natural number.
From Bernard Schott, Feb 27 2023: (Start)
Subsequence of primes is A002383 because in this case phi(k^2+k+1) = k*(k+1).
Subsequence of oblong numbers is A359847 where k and phi(k) are both oblong numbers. (End)

			phi(13) = 12 = 3*4, an oblong number; so 13 is a term of the sequence.

Giovanni Resta, Table of n, a(n) for n = 1..10000

Cf. A000010, A002378, A002383, A359847.

Similar, but where phi(m) is: A039770 (square), A039771 (cube), A078164 (biquadrate), A096503 (repdigit), A117296 (palindrome), A360944 (triangular).

filter := m -> issqr(1 + 4*phi(m)) : select(filter, [$(1 .. 700)]); # Bernard Schott, Feb 26 2023

Select[Range[500], IntegerQ@Sqrt[1 + 4*EulerPhi[#]] &] (* Giovanni Resta, Jan 24 2014 *)

isok(m) = my(t=eulerphi(m)); !(t%2) && ispolygonal(t/2, 3); \\ Michel Marcus, Feb 27 2023

from itertools import count, islice
from sympy.ntheory.primetest import is_square
from sympy import totient
def A236386_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:is_square((totient(n)<<2)+1), count(max(1,startvalue)))
A236386_list = list(islice(A236386_gen(),20)) # Chai Wah Wu, Feb 28 2023

a(16)-a(58) from Giovanni Resta, Jan 24 2014

A262406 Squarefree k such that phi(k) is a perfect square.

Original entry on oeis.org

1, 2, 5, 10, 17, 34, 37, 57, 74, 85, 101, 114, 170, 185, 197, 202, 219, 257, 273, 285, 370, 394, 401, 438, 451, 489, 505, 514, 546, 570, 577, 629, 677, 679, 802, 902, 969, 978, 985, 1010, 1057, 1095, 1154, 1258, 1285, 1297, 1354, 1358, 1365

Offset: 1

Charles R Greathouse IV, Oct 13 2015

nonn

The subsequence of primes is A002496 (primes of the form k^2+1). - Michel Marcus, Oct 14 2015

Charles R Greathouse IV, 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.

Intersection of A039770 and A005117.

Cf. A000010, A002496, A007614, A068560, A004171, A114063.

[n: n in [1..1400] | IsSquarefree(n) and IsSquare(EulerPhi(n))]; // Vincenzo Librandi, May 05 2016

Select[Range[1500], SquareFreeQ[#] && IntegerQ @ Sqrt @ EulerPhi[#] &] (* Amiram Eldar, Jul 16 2022 *)

is(n)=my(f=factor(n)); issquare(eulerphi(f)) && (n==1 || vecmax(f[,2])==1)

Banks, Friedlander, Pomerance, and Shparlinski show that a(n) = O(n^1.421).

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

A333912 Numbers k such that phi(k) is not the sum of 3 squares, where phi is the Euler totient function (A000010).

Original entry on oeis.org

29, 58, 61, 77, 93, 99, 113, 122, 124, 141, 145, 154, 157, 169, 186, 188, 198, 226, 232, 237, 241, 253, 282, 287, 290, 301, 305, 314, 316, 317, 325, 338, 348, 349, 363, 369, 381, 385, 387, 413, 429, 441, 449, 465, 474, 482, 484, 488, 493, 495, 496, 506, 508, 509

Offset: 1

Amiram Eldar, Apr 09 2020

nonn

Pollack (2011) proved that the complementary sequence has asymptotic density 7/8. Therefore the asymptotic density of this sequence is 1/8.

			1 is not a term since phi(1) = 1 = 0^2 + 0^2 + 1^2 is the sum of 3 squares.
29 is a term since phi(29) = 28 is not the sum of 3 squares.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Pollack, Values of the Euler and Carmichael functions which are sums of three squares, Integers, Vol. 11 (2011), pp. 145-161.

Cf. A000010, A004215, A039770, A272405, A333909, A333913.

Select[Range[500], SquaresR[3, EulerPhi[#]] == 0 &]

A067781 Numbers k such that phi(k) and sigma(k) are both perfect squares.

Original entry on oeis.org

1, 170, 364, 679, 5044, 5130, 5670, 5770, 8721, 8736, 9154, 9639, 9809, 14322, 16376, 22413, 27783, 30256, 32025, 37114, 38760, 51455, 71604, 78570, 82615, 88392, 92004, 100821, 101153, 104168, 115430, 121056, 133569, 139954, 148568, 171069, 177940, 198462, 217868

Offset: 1

Benoit Cloitre, Feb 07 2002

nonn

A subsequence of A011257. - M. F. Hasler, Sep 22 2009

Donovan Johnson, Table of n, a(n) for n = 1..5000

Cf. A000010 (phi), A000203 (sigma), A006532, A011257, A039770.

Select[Range[250000], And @@ (IntegerQ[Sqrt[#1]] & /@ {EulerPhi[#], DivisorSigma[1, #]} ) &] (* Amiram Eldar, May 08 2025 *)

isok(k) = {my(f = factor(k)); issquare(eulerphi(f)) && issquare(sigma(f));} \\ Amiram Eldar, May 08 2025

Equals A006532 intersect A039770. - M. F. Hasler, Sep 22 2009

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

A287473 Triangular numbers k such that phi(k) is a square number, where phi(k) is the Euler totient function (A000010).

Original entry on oeis.org

1, 10, 136, 630, 2016, 7875, 9180, 18915, 32896, 37128, 46056, 58311, 66430, 103740, 131841, 198135, 225456, 301476, 323610, 332520, 408156, 499500, 738720, 786885, 839160, 862641, 922761, 924120, 1065070, 1079715, 1183491, 1385280, 1851850, 1906128, 1925703

Offset: 1

Amiram Eldar, May 25 2017

nonn

The indices of these triangular numbers are: 1, 4, 16, 35, 63, 125, 135, 194, 256, 272, 303, 341, 364, 455, 513, 629, 671, 776, 804, 815, 903, 999, 1215, 1254, 1295, 1313, 1358, 1359, 1459, 1469, 1538, 1664, 1924, 1952, 1962, ... and their phi values are the squares of: 1, 2, 8, 12, 24, 60, 48, 96, 128, 96, 120, 180, 144, 144, 288, 288, 240, 288, 264, 288, 336, 360, 432, 600, 432, 720, 720, 480, 648, 672, 864, 576, 720, 720, 1080, ...

Similar to A115910, since A115910(n)^2 are squares whose phi is a triangular number.

			136=16*17/2 is triangular, phi(136)=64=8^2 is a square, thus 136 is in the sequence.

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

Cf. A000010, A000217, A000290, A039770, A115910, A256151.

Intersection of A000217 and A039770.

Select[Accumulate[Range[1000]],IntegerQ[Sqrt[EulerPhi[#]]]&]

isok(n) = ispolygonal(n, 3) && issquare(eulerphi(n)); \\ Michel Marcus, May 25 2017

A291549 Numbers n such that both phi(n) and psi(n) are perfect squares.

Original entry on oeis.org

1, 60, 170, 240, 315, 540, 679, 680, 960, 1500, 2142, 2160, 2720, 2835, 3840, 4250, 4365, 4860, 5770, 6000, 7875, 8568, 8640, 9154, 9809, 10880, 13500, 14322, 15360, 15435, 17000, 19278, 19440, 22413, 23080, 24000, 25515, 29682, 33271, 34272, 34560, 36616, 37114, 37500

Offset: 1

Amiram Eldar and Altug Alkan, Aug 26 2017

Intersection of A039770 and A291167.
Squarefree terms are 1, 170, 679, 5770, 9154, 9809, 14322, ...
From Robert Israel, May 16 2019: (Start)
If n is in the sequence and p is a prime factor of n then p^2*n is in the sequence.
If n and m are coprime members of the sequence, then n*m is in the sequence. (End)

			60 is a term because phi(60) = 16 and psi(60) = 144 are both perfect squares.

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

Cf. A000010, A000290, A001615, A039770, A291167.

filter:= proc(n) local F,psi,phi,p;
   F:= numtheory:-factorset(n);
   issqr( n*mul(1-1/p, p=F)) and issqr(n*mul(1+1/p,p=F))
end proc:
select(filter, [$1..50000]); # Robert Israel, May 15 2019

Select[Range[10^5], AllTrue[{EulerPhi@ #, If[# < 1, 0, # Sum[MoebiusMu[d]^2/d, {d, Divisors@ #}]]}, IntegerQ@ Sqrt@ # &] &] (* Michael De Vlieger, Aug 26 2017, after Michael Somos at A001615 *)

a001615(n) = my(f=factor(n)); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1))
isok(n) = issquare(eulerphi(n)) && issquare(a001615(n)); \\ after Charles R Greathouse IV at A001615

cp's OEIS Frontend

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A236386 Numbers m such that phi(m) is an oblong number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

A262406 Squarefree k such that phi(k) is a perfect square.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

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

A333912 Numbers k such that phi(k) is not the sum of 3 squares, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A067781 Numbers k such that phi(k) and sigma(k) are both perfect squares.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs