A029939 -id:A029939 - cp's OEIS frontend

A069063 Composite k such that A029939(k) > k*(k+1)/2 where A029939(k) = Sum_{d|k} phi(d)^2.

25, 49, 55, 65, 69, 77, 85, 87, 91, 93, 95, 111, 115, 119, 121, 123, 125, 129, 133, 141, 143, 145, 155, 159, 161, 169, 175, 177, 183, 185, 187, 201, 203, 205, 209, 213, 215, 217, 219, 221, 235, 237, 245, 247, 249, 253, 259, 265, 267, 275, 287, 289, 291, 295

Offset: 1

Benoit Cloitre, Apr 04 2002

Cf. A029939.

A127473 a(n) = phi(n)^2.

Original entry on oeis.org

1, 1, 4, 4, 16, 4, 36, 16, 36, 16, 100, 16, 144, 36, 64, 64, 256, 36, 324, 64, 144, 100, 484, 64, 400, 144, 324, 144, 784, 64, 900, 256, 400, 256, 576, 144, 1296, 324, 576, 256, 1600, 144, 1764, 400, 576, 484, 2116, 256, 1764, 400, 1024, 576, 2704, 324, 1600

Offset: 1

Gary W. Adamson, Jan 15 2007

Number of maps of the form j |--> m*j + d with gcd(m, n) = 1 and gcd(d, n) = 1 from [1, 2, ..., n] to itself. - Joerg Arndt, Aug 29 2014
Right border of A127474.
Equals the Mobius transform (A054525) of A029939. - Gary W. Adamson, Aug 20 2008
From Jianing Song, Apr 14 2019: (Start)
a(n) is the number of solutions to gcd(xy, n) = 1 with x, y in [0, n-1].
Let Z_n be the ring of integers modulo n, then a(n) is the number of invertible elements in the ring Z_n[x]/(x^2 - x) (or equivalently, Z_n[x]/(x^2 + x)) with discriminant d = 1 (that is, a(n) is the size of the group G(n) = (Z_n[x]/(x^2 - x))*). Actually, G(n) is isomorphic to (Z_n)* X (Z_n)*. (End)

			a(5) = 16 since phi(5) = 4.

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).

Cf. A000010, A057434, A065464, A109695, A127474, A358714, A361148, A008683.

Similar sequences: A082953 (size of (Z_n[x]/(x^2 - 1))*, d = 4), A002618 ((Z_n[x]/(x^2))*, d = 0), A079458 ((Z_n[x]/(x^2 + 1))*, d = -4), A319445 ((Z_n[x]/(x^2 - x + 1))* or (Z_n[x]/(x^2 + x + 1))*, d = -3).

[(EulerPhi(n))^2: n in [1..180]]; // Vincenzo Librandi, Apr 04 2011

A127473 := proc(n) numtheory[phi](n)^2 ; end proc:
seq(A127473(n),n=1..40) ; # R. J. Mathar, Apr 04 2011

Table[EulerPhi[n]^2,{n,100}] (* Vladimir Joseph Stephan Orlovsky, Feb 02 2012 *)

a(n) = eulerphi(n)^2; \\ Michel Marcus, Oct 16 2018

a(n) = A000010(n)^2.
Multiplicative with a(p^e) = (p-1)^2*p^(2e-2), e >= 1. Dirichlet g.f. zeta(s-2)*Product_{primes p} (1 - 2/p^(s-1) + 1/p^s). - R. J. Mathar, Apr 04 2011
Sum_{k>=1} 1/a(k) = A109695. - Vaclav Kotesovec, Sep 20 2020
Sum_{k>=1} (-1)^k/a(k) = (1/7) * A109695. - Amiram Eldar, Nov 11 2020
Sum_{k=1..n} a(k) ~ c * n^3, where c = (1/3) * Product_{p prime}(1 - (2*p-1)/p^3) = A065464 / 3 = 0.142749... . - Amiram Eldar, Oct 25 2022
a(n) = Sum_{d|n} mu(n/d)*phi(n*d). - Ridouane Oudra, Jul 23 2025

A062952 Multiplicative with a(p^e) = (p^(2*e+2)-p^(e+1)-p^e+p)/(p^2-1).

Original entry on oeis.org

1, 4, 9, 18, 25, 36, 49, 78, 87, 100, 121, 162, 169, 196, 225, 326, 289, 348, 361, 450, 441, 484, 529, 702, 645, 676, 807, 882, 841, 900, 961, 1334, 1089, 1156, 1225, 1566, 1369, 1444, 1521, 1950, 1681, 1764, 1849, 2178, 2175, 2116, 2209, 2934, 2443, 2580

Offset: 1

Vladeta Jovovic, Jul 21 2001

If k is squarefree (cf. A005117) then A062952(k) = k^2. - Benoit Cloitre, Apr 16 2002

Inverse Möbius transform of A062354(n). - Wesley Ivan Hurt, Jul 26 2025

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

Cf. A005117, A029939, A057660, A062952.
Cf. A002117, A013661, A183699, A330523.
Cf. A062354.

f[p_, e_] := (p^(2*e+2)-p^(e+1)-p^e+p)/(p^2-1); a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 50] (* Amiram Eldar, Jul 31 2019 *)

a(n) = sumdiv(n, d, eulerphi(d)*sigma(d)) \\ Michel Marcus, Jun 17 2013

a(n) = Sum_{d|n} phi(d)*sigma(d).
a(n) = Sum_{k=1..n} sigma(n/gcd(n, k)).
Sum_{k=1..n} a(k) ~ c * n^3, where c = (zeta(2)*zeta(3)/3) * Product_{p prime} (1 - 1/p^2 - 1/p^3 + 1/p^4) = A183699 * A330523 / 3. - Amiram Eldar, Oct 30 2022

A062949 Multiplicative with a(p^e) = ((e+1)p^(e+1)-(e+2)p^e+1)/(p-1).

Original entry on oeis.org

1, 3, 5, 9, 9, 15, 13, 25, 23, 27, 21, 45, 25, 39, 45, 65, 33, 69, 37, 81, 65, 63, 45, 125, 69, 75, 95, 117, 57, 135, 61, 161, 105, 99, 117, 207, 73, 111, 125, 225, 81, 195, 85, 189, 207, 135, 93, 325, 139, 207, 165, 225, 105, 285, 189, 325, 185, 171, 117, 405

Offset: 1

Vladeta Jovovic, Jul 21 2001

Inverse Mobius transform of A062355.

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

Cf. A057660, A029939.

A062949 := proc(n) add(numtheory[phi](d)*numtheory[tau](d), d=numtheory[divisors](n)) ; end proc: # R. J. Mathar, Feb 09 2011

f[p_, e_] := ((e+1)*p^(e+1)-(e+2)*p^e+1)/(p-1); a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 60] (* Amiram Eldar, Jul 31 2019 *)

a(n) = Sum_{d|n} phi(d)*tau(d).
a(n) = Sum_{k=1..n} tau(n/gcd(n, k)).
a(n) = Sum_{d|n} d*uphi(n/d), where uphi() = A047994(). - Vladeta Jovovic, Mar 16 2004

A342471 a(n) = Sum_{d|n} phi(d)^n.

Original entry on oeis.org

1, 2, 9, 18, 1025, 130, 279937, 65794, 10078209, 2097154, 100000000001, 16789506, 106993205379073, 156728328194, 35185445863425, 281479271743490, 295147905179352825857, 203119913861122, 708235345355337676357633, 1152923703631151106

Offset: 1

Seiichi Manyama, Mar 13 2021

nonn

Cf. A000010, A029939, A110567, A309369, A338997, A342470.

a[n_] := DivisorSum[n, EulerPhi[#]^n &]; Array[a, 20] (* Amiram Eldar, Mar 13 2021 *)

PARI
```
a(n) = sumdiv(n, d, eulerphi(d)^n);
```

a(n) = sum(k=1, n, eulerphi(n/gcd(k, n))^(n-1));

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, (eulerphi(k)*x)^k/(1-(eulerphi(k)*x)^k)))

a(n) = Sum_{k=1..n} phi(n/gcd(k, n))^(n-1).
G.f.: Sum_{k>=1} (phi(k)*x)^k/(1 - (phi(k)*x)^k).
If p is prime, a(p) = 1 + (p-1)^p = A110567(p-1).
a(n) = Sum_{k=1..n} phi(gcd(n,k))^n/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021

A062367 Multiplicative with a(p^e) = (e+1)(e+2)(2*e+3)/6.

Original entry on oeis.org

1, 5, 5, 14, 5, 25, 5, 30, 14, 25, 5, 70, 5, 25, 25, 55, 5, 70, 5, 70, 25, 25, 5, 150, 14, 25, 30, 70, 5, 125, 5, 91, 25, 25, 25, 196, 5, 25, 25, 150, 5, 125, 5, 70, 70, 25, 5, 275, 14, 70, 25, 70, 5, 150, 25, 150, 25, 25, 5, 350, 5, 25, 70, 140, 25, 125, 5, 70, 25, 125, 5

Offset: 1

Vladeta Jovovic, Jul 07 2001

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000005, A000012, A000330, A029939, A035116, A048691, A060648, A062368.

A062367 := proc(n)
    add(numtheory[tau](d)^2,d=numtheory[divisors](n)) ;
end proc:
seq(A062367(n),n=1..40) ; # R. J. Mathar, May 15 2025

{1}~Join~Array[Times @@ Map[((# + 1) (# + 2) (2 # + 3))/6 &, FactorInteger[#][[All, -1]] ] &, 70, 2] (* or *)
Array[DivisorSum[#, DivisorSigma[0, #]^2 &] &, 71] (* Michael De Vlieger, Mar 05 2021 *)

a(n) = sumdiv(n, d, numdiv(d)^2) \\ Michel Marcus, Jun 17 2013

a(n) = Sum_{i|n, j|n} tau(gcd(i, j)) = Sum_{d|n} tau(d)^2.
a(n) = Sum_{i|n, j|n} tau(i)*tau(j)/tau(lcm(i, j)), where tau(n) = number of divisors of n, cf. A000005.
Dirichlet convolution of A035116 and A000012 (i.e., inverse Mobius transform of A035116). Dirichlet g.f.: zeta^5(s)/zeta(2s). - R. J. Mathar, Feb 03 2011
G.f.: Sum_{n>=1} A000005(n)^2*x^n/(1-x^n). - Mircea Merca, Feb 26 2014
L.g.f.: -log(Product_{k>=1} (1 - x^k)^(tau(k)^2/k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 23 2018
Dirichlet convolution of A007426 and A008966. Dirichlet convolution of A007425 and A034444. - R. J. Mathar, Jun 05 2020
Let b(n), n > 0, be Dirichlet inverse of a(n). Then b(n) is multiplicative with b(p^e) = (-1)^e*(Sum_{i=0..e} binomial(4,i)) for prime p and e >= 0, where binomial(n,k)=0 if n < k; abs(b(n)) is multiplicative and has the Dirichlet g.f.: (zeta(s))^5/(zeta(2*s))^4. - Werner Schulte, Feb 07 2021
a(n) = Sum_{d divides n} tau(d^2)*tau(n/d), Dirichlet convolution of A048691 and A000005. - Peter Bala, Jan 26 2024

A065018 a(n) = Sum_{d|n} sigma(d)^2.

Original entry on oeis.org

1, 10, 17, 59, 37, 170, 65, 284, 186, 370, 145, 1003, 197, 650, 629, 1245, 325, 1860, 401, 2183, 1105, 1450, 577, 4828, 998, 1970, 1786, 3835, 901, 6290, 1025, 5214, 2465, 3250, 2405, 10974, 1445, 4010, 3349, 10508, 1765, 11050, 1937, 8555, 6882

Offset: 1

Vladeta Jovovic, Nov 19 2001

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A029939, A062367.

{ for (n=1, 1000, a=sumdiv(n, d, sigma(d)^2); write("b065018.txt", n, " ", a) ) } \\ Harry J. Smith, Oct 03 2009

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, sigma(k)^2*x^k/(1-x^k))) \\ Seiichi Manyama, May 08 2021

Dirichlet convolution of A072861 and A000012. Dirichlet g.f.: zeta^2(s)*zeta^2(s-1)*zeta(s-2)/zeta(2s-2). - R. J. Mathar, Feb 03 2011
Sum_{k=1..n} a(k) ~ 5 * Zeta(3)^2 * n^3 / 6. - Vaclav Kotesovec, Feb 01 2019
From Seiichi Manyama, May 08 2021: (Start)
G.f.: Sum_{k >= 1} sigma(k)^2 * x^k/(1 - x^k).
If p is prime, a(p) = 1 + (p+1)^2. (End)

A338997 Number of (i,j,k) in {1,2,...,n}^3 such that gcd(n,i) = gcd(n,j) = gcd(n,k).

Original entry on oeis.org

1, 2, 9, 10, 65, 18, 217, 74, 225, 130, 1001, 90, 1729, 434, 585, 586, 4097, 450, 5833, 650, 1953, 2002, 10649, 666, 8065, 3458, 6057, 2170, 21953, 1170, 27001, 4682, 9009, 8194, 14105, 2250, 46657, 11666, 15561, 4810, 64001, 3906, 74089, 10010, 14625, 21298, 97337, 5274, 74305, 16130

Offset: 1

Benoit Cloitre, Dec 31 2020

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

Cf. A000010, A029939.

a[n_] := DivisorSum[n, EulerPhi[#]^3 &]; Array[a, 100] (* Amiram Eldar, Dec 31 2020 *)

PARI
```
a(n)=sumdiv(n,d,eulerphi(d)^3)
```

a(n) = sum(k=1, n, eulerphi(n/gcd(k, n))^2); \\ Seiichi Manyama, Mar 13 2021

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)^3*x^k/(1-x^k))) \\ Seiichi Manyama, Mar 13 2021

a(n) = Sum_{d|n} phi(d)^3.
From Seiichi Manyama, Mar 13 2021: (Start)
a(n) = Sum_{k=1..n} phi(n/gcd(k, n))^2.
G.f.: Sum_{k>=1} phi(k)^3 * x^k/(1 - x^k). (End)
From Amiram Eldar, Nov 15 2022: (Start)
Multiplicative with a(p^e) = 1 + ((p-1)^2 (p^(3*e)-1))/(p^2 + p + 1).
Sum_{k=1..n} a(k) ~ c * n^4, where c = (Pi^4/360) * Product_{p prime} (1 - 3/p^2 + 3/p^3 - 1/p^4) = 0.09123656748... . (End)

A342473 a(n) = Sum_{d|n} phi(d)^d.

Original entry on oeis.org

1, 2, 9, 18, 1025, 74, 279937, 65554, 10077705, 1049602, 100000000001, 16777306, 106993205379073, 78364444034, 35184372089865, 281474976776210, 295147905179352825857, 101559966746186, 708235345355337676357633, 1152921504607896594, 46005119909369701746057, 10000000000100000000002

Offset: 1

Seiichi Manyama, Mar 13 2021

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..388

Cf. A000010, A029939, A110567, A309369, A338997, A342470, A342471, A342485.

a[n_] := DivisorSum[n, EulerPhi[#]^# &]; Array[a, 20] (* Amiram Eldar, Mar 14 2021 *)

PARI
```
a(n) = sumdiv(n, d, eulerphi(d)^d);
```

a(n) = sum(k=1, n, eulerphi(n/gcd(k, n))^(n/gcd(k, n)-1));

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, (eulerphi(k)*x)^k/(1-x^k)))

a(n) = Sum_{k=1..n} phi(n/gcd(k, n))^(n/gcd(k, n) - 1).
G.f.: Sum_{k>=1} (phi(k) * x)^k/(1 - x^k).
If p is prime, a(p) = 1 + (p-1)^p = A110567(p-1).
a(n) = Sum_{k=1..n} phi(gcd(n,k))^gcd(n,k)/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021

A342470 a(n) = Sum_{d|n} phi(d)^4.

Original entry on oeis.org

1, 2, 17, 18, 257, 34, 1297, 274, 1313, 514, 10001, 306, 20737, 2594, 4369, 4370, 65537, 2626, 104977, 4626, 22049, 20002, 234257, 4658, 160257, 41474, 106289, 23346, 614657, 8738, 810001, 69906, 170017, 131074, 333329, 23634, 1679617, 209954, 352529, 70418

Offset: 1

Seiichi Manyama, Mar 13 2021

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000010, A013663, A029939, A338997, A342471.

a[n_] := DivisorSum[n, EulerPhi[#]^4 &]; Array[a, 40] (* Amiram Eldar, Mar 13 2021 *)

PARI
```
a(n) = sumdiv(n, d, eulerphi(d)^4);
```

a(n) = sum(k=1, n, eulerphi(n/gcd(k, n))^3);

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)^4*x^k/(1-x^k)))

a(n) = Sum_{k=1..n} phi(n/gcd(k, n))^3.
G.f.: Sum_{k>=1} phi(k)^4 * x^k/(1 - x^k).
From Amiram Eldar, Nov 13 2022: (Start)
Multiplicative with a(p^e) = 1 + ((p-1)^3*(p^(4*e)-1))/(p^3 + p^2 + p + 1).
Sum_{k=1..n} a(k) ~ c * n^5, where c = (zeta(5)/5) * Product_{p prime} (1 - 4/p^2 + 6/p^3 - 4/p^4 + 1/p^5) = 0.05936545607... . (End)

cp's OEIS Frontend

A069063 Composite k such that A029939(k) > k*(k+1)/2 where A029939(k) = Sum_{d|k} phi(d)^2.

Views

Author

Keywords

Crossrefs

A127473 a(n) = phi(n)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A062952 Multiplicative with a(p^e) = (p^(2*e+2)-p^(e+1)-p^e+p)/(p^2-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A062949 Multiplicative with a(p^e) = ((e+1)*p^(e+1)-(e+2)*p^e+1)/(p-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A342471 a(n) = Sum_{d|n} phi(d)^n.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A062367 Multiplicative with a(p^e) = (e+1)*(e+2)*(2*e+3)/6.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A065018 a(n) = Sum_{d|n} sigma(d)^2.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A338997 Number of (i,j,k) in {1,2,...,n}^3 such that gcd(n,i) = gcd(n,j) = gcd(n,k).

Views

Author

Keywords

Links

Crossrefs

A062949 Multiplicative with a(p^e) = ((e+1)p^(e+1)-(e+2)p^e+1)/(p-1).

A062367 Multiplicative with a(p^e) = (e+1)(e+2)(2*e+3)/6.