A018804 -id:A018804 - cp's OEIS frontend

A342370 a(n) = Sum_{k=1..n} gcd(k,n)^(k-1).

1, 3, 11, 68, 629, 7797, 117655, 2097254, 43046979, 1000000799, 25937424611, 743008402000, 23298085122493, 793714773374529, 29192926027528343, 1152921504613147242, 48661191875666868497, 2185911559739107208115, 104127350297911241532859, 5242880000000008181608132

Offset: 1

Seiichi Manyama, Mar 13 2021

nonn

Martin Ehrenstein, Table of n, a(n) for n = 1..400

Cf. A000010, A018804, A056665, A173235, A341036, A342394, A342433, A342436, A342449.

a[n_] := Sum[GCD[k, n]^(k - 1), {k, 1, n}]; Array[a, 20] (* Amiram Eldar, Mar 13 2021 *)

PARI
```
a(n) = sum(k=1, n, gcd(k, n)^(k-1));
```

If p is prime, a(p) = p-1 + p^(p-1) = A173235(p).

a(19) and beyond from Martin Ehrenstein, Mar 13 2021

A349570 Dirichlet convolution of A011782 [2^(n-1)] with A055615 (Dirichlet inverse of n).

Original entry on oeis.org

1, 0, 1, 4, 11, 24, 57, 112, 244, 480, 1013, 1972, 4083, 8064, 16331, 32512, 65519, 130488, 262125, 523244, 1048377, 2095104, 4194281, 8384176, 16777136, 33546240, 67108096, 134201316, 268435427, 536836584, 1073741793, 2147418112, 4294964213, 8589803520, 17179868787, 34359470272, 68719476699, 137438429184, 274877894643

Offset: 1

Antti Karttunen, Nov 22 2021

nonn

Dirichlet convolution of this sequence with phi (A000010) is A000740, with sigma (A000203) it is A034729, and with A018804 it is A034738.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A055615, A349569 (Dirichlet inverse).

Cf. also A000010, A000740, A000203, A018804, A034729, A034738, A349564, A349566, A349568.

a[n_] := DivisorSum[n, # * MoebiusMu[#] * 2^(n/# - 1) &]; Array[a, 40] (* Amiram Eldar, Nov 22 2021 *)

A055615(n) = (n*moebius(n));
A349570(n) = sumdiv(n,d,(2^(d-1)) * A055615(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A055615(n/d).

A368737 a(n) = Sum_{k = 1..n} gcd(3*k, n).

Original entry on oeis.org

1, 3, 9, 8, 9, 27, 13, 20, 45, 27, 21, 72, 25, 39, 81, 48, 33, 135, 37, 72, 117, 63, 45, 180, 65, 75, 189, 104, 57, 243, 61, 112, 189, 99, 117, 360, 73, 111, 225, 180, 81, 351, 85, 168, 405, 135, 93, 432, 133, 195, 297, 200, 105, 567, 189, 260, 333, 171, 117, 648, 121, 183, 585, 256, 225, 567, 133, 264, 405, 351

Offset: 1

Peter Bala, Jan 05 2024

a(n) equals the number of solutions to the congruence 3*x*y == 0 (mod n) for 1 <= x, y <= n.

			a(6) = 27: each of the 36 pairs (x, y), 1 <= x, y <= 6, is a solution to the congruence 3*x*y == 0 (mod 6) except for the 9 pairs (x, y) with both x and y odd.

Seiichi Manyama, Table of n, a(n) for n = 1..10000
Peter Bala, Notes on A368737

Cf. A000010, A018804, A344372, A368736 - A368742.

seq(add(gcd(3*k, n), k = 1..n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(gcd(3,d)*phi(d)*n/d, d in divisors(n)), n = 1..70);

Table[Sum[GCD[3*k, n], {k, 1, n}], {n, 1, 100}] (* Vaclav Kotesovec, Jan 11 2024 *)

a(n) = sum(k = 1, n, gcd(3*k, n)); \\ Michel Marcus, Jan 11 2024

a(3*n) = 9*A018804(n); a(3*n+1) = A018804(3*n+1); a(3*n+2) = A018804(3*n+2).
a(n) = Sum_{d divides n} gcd(3, d)*phi(d)*n/d, where phi(n) = A000010(n)
Multiplicative: a(3^k) = (2*k + 1)*3^k and for prime p not equal to 3, a(p^k) = (k + 1)*p^k - k*p^(k-1).
Define D(n) = Sum_{d divides n} a(d). Then
D(3*n+1) = (3*n + 1)*tau(3*n+1) and D(3*n+2) = (3*n + 2)*tau(3*n+2), where tau(n) = A000005(n), the number of divisors of n.
The sequence {(1/9)*( D(3*n) - D(n) ) : n >= 1} begins {1, 4, 5, 12, 10, 20, 14, 32, 21, 40, 22, 60, 26, 56, 50, 80, 34, 84, 38, 120, 70, 88, ...} and appears to be multiplicative.
Dirichlet g.f.: (1 + 3/3^s)/(1 - 1/3^s) * zeta(s-1)^2/zeta(s).
Sum_{k=1..n} a(k) ~ 9*n^2 * (log(n)/2 - 1/4 + gamma - 3*log(3)/16 - 3*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 11 2024

A368741 a(n) = Sum_{k = 1..n} gcd(5*k + 1, n).

Original entry on oeis.org

1, 3, 5, 8, 5, 15, 13, 20, 21, 15, 21, 40, 25, 39, 25, 48, 33, 63, 37, 40, 65, 63, 45, 100, 25, 75, 81, 104, 57, 75, 61, 112, 105, 99, 65, 168, 73, 111, 125, 100, 81, 195, 85, 168, 105, 135, 93, 240, 133, 75, 165, 200, 105, 243, 105, 260, 185, 171, 117, 200, 121, 183, 273, 256, 125, 315, 133, 264, 225, 195

Offset: 1

Peter Bala, Jan 08 2024

Cf. A000010, A011558, A018804, A368736 - A368742.

with(numtheory): seq(add(gcd(5*k+1, n), k = 1..n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(irem(d^4,5)*phi(d)*n/d, d in divisors(n)), n = 1..70);

Table[Sum[GCD[5*k+1, n], {k, 1, n}], {n, 1, 100}] (* Vaclav Kotesovec, Jan 12 2024 *)

a(n) = Sum_{k = 1..n} gcd(5*k + r, n) for 1 <= r <= 4.
a(5*n) = 5*a(n); a(5*n+r) = A018804(5*n+r) for 1 <= r <= 4.
a(n) = Sum_{d divides n} X(d)*phi(d)*n/d, where phi(n) = A000010(n) and X(n) = A011558(n) is the principal Dirichlet character of the reduced residue system mod 5.
Multiplicative: a(5^k) = 5^k and for prime p not equal to 5, a(p^k) = (k + 1)*p^k - k*p^(k-1).
Dirichlet g.f.: (1 - 5/5^s)/(1 - 1/5^s) * zeta(s-1)^2/zeta(s).
Sum_{k=1..n} a(k) ~ 5*n^2 * (log(n)/2 - 1/4 + gamma + 5*log(5)/48 - 3*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 12 2024

A372674 a(n) = Sum_{j=1..n} Sum_{k=1..n} tau(j*k).

Original entry on oeis.org

1, 8, 23, 54, 89, 162, 221, 326, 439, 596, 707, 964, 1107, 1352, 1645, 1976, 2179, 2630, 2865, 3390, 3859, 4316, 4615, 5406, 5883, 6444, 7059, 7892, 8299, 9430, 9877, 10794, 11635, 12424, 13361, 14852, 15415, 16324, 17349, 18952, 19587, 21342, 22017, 23486, 25177

Offset: 1

Vaclav Kotesovec, May 10 2024

nonn

For m>=1, Sum_{j=1..n} tau(m*j) = A018804(m) * n * log(n) + O(n).

If p is prime, then Sum_{j=1..n} tau(p*j) ~ (2*p - 1) * n * (log(n) - 1 + 2*gamma)/p + n*log(p)/p, where gamma is the Euler-Mascheroni constant A001620.

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000
Vaclav Kotesovec, Plot of a(n) / (n^2 * (log(n) + 2*gamma - 1/2)^2) for n = 1..100000

Cf. A372633, A372675.
Cf. A006218, A263086.
cf. A000005, A099777, A372713.

Table[Sum[DivisorSigma[0, j*k], {j, 1, n}, {k, 1, n}], {n, 1, 50}]
s = 1; Join[{1}, Table[s += DivisorSigma[0, n^2] + 2*Sum[DivisorSigma[0, j*n], {j, 1, n - 1}], {n, 2, 50}]]

A372938 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{1 <= x_1, x_2, ..., x_k <= n} gcd(x_1, x_2, ..., x_k, n)^k.

Original entry on oeis.org

1, 1, 3, 1, 7, 5, 1, 15, 17, 8, 1, 31, 53, 40, 9, 1, 63, 161, 176, 49, 15, 1, 127, 485, 736, 249, 119, 13, 1, 255, 1457, 3008, 1249, 795, 97, 20, 1, 511, 4373, 12160, 6249, 4991, 685, 208, 21, 1, 1023, 13121, 48896, 31249, 30555, 4801, 1856, 225, 27

Offset: 1

Seiichi Manyama, May 17 2024

			Square array begins:
   1,   1,   1,    1,     1,      1,       1, ...
   3,   7,  15,   31,    63,    127,     255, ...
   5,  17,  53,  161,   485,   1457,    4373, ...
   8,  40, 176,  736,  3008,  12160,   48896, ...
   9,  49, 249, 1249,  6249,  31249,  156249, ...
  15, 119, 795, 4991, 30555, 185039, 1115115, ...
  13,  97, 685, 4801, 33613, 235297, 1647085, ...

Columns k=1..4 give: A018804, A360428, A372928, A372931.
Main diagonal gives A372939.
Cf. A000005, A001620, A008683, A343510.

f[p_, e_, k_] := (e - e/p^k + 1)*p^(k*e); T[1, k_] := 1; T[n_, k_] := Times @@ (f[First[#], Last[#], k] & /@ FactorInteger[n]); Table[T[k, n - k + 1], {n, 1, 10}, {k, 1, n}] // Flatten (* Amiram Eldar, May 25 2024 *)

T(n,k) = sumdiv(n, d, moebius(n/d)*d^k*numdiv(d));

a(n) = Sum_{d|n} mu(n/d) * d^k * tau(d), where mu is the Moebius function A008683.
From Amiram Eldar, May 25 2024: (Start)
T(n,k) for a given k is multiplicative with T(p^e, k) = (e - e/p^k + 1) * p^(k*e).
Dirichlet g.f. of T(n, k) for a given k: zeta(s-k)^2/zeta(s).
Sum_{m=1..n} T(m, k) ~ (n^(k+1)/((k+1)*zeta(k+1))) * (log(n) + 2*gamma - 1/(k+1) - zeta'(k+1)/zeta(k+1)), where gamma is Euler's constant (A001620). (End)

A070999 Numbers n such that the denominator of Sum_{k=1..n} 1/gcd(n,k) is not equal to n.

Original entry on oeis.org

6, 15, 18, 21, 30, 33, 35, 42, 44, 45, 48, 51, 54, 60, 66, 69, 70, 78, 84, 87, 90, 99, 102, 105, 114, 119, 120, 123, 126, 132, 133, 135, 138, 140, 141, 144, 147, 150, 153, 159, 162, 165, 168, 174, 177, 180, 186, 195, 198, 204, 207, 210, 213, 217, 220, 221, 222

Offset: 1

Benoit Cloitre, May 18 2002

Does lim_{n->infinity} a(n)/n = 3?
Sum_{k=1..n} 1/gcd(n,k) = (1/n)*Sum_{d|n} phi(d)*d = (1/n)*Sum_{k=1..n} gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)), where phi = A000010. - Richard L. Ollerton, May 10 2021
Numbers k such that gcd(k, A057660(k)) > 1. - Amiram Eldar, Jun 29 2022

			Sum_{k=1..6} 1/gcd(6,k) = 7/2, hence 6 is in the sequence;
Sum_{k=1..12} 1/gcd(12,k) = 77/12 so 12 is not in the sequence.

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

Cf. A000010, A018804, A057660.

Select[Range[300],Denominator[Sum[1/GCD[#,k],{k,#}]]!=#&] (* Harvey P. Dale, May 07 2022 *)
f[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); s[n_] := Times @@ (f @@@ FactorInteger[n]); Select[Range[250], !CoprimeQ[#, s[#]] &] (* Amiram Eldar, Jun 29 2022 *)

for(n=1,300,if(denominator(sum(i=1,n,1/gcd(n,i)))

A071000 Numbers m such that the denominator of Sum_{k=1..m} 1/gcd(m,k) equals m.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 34, 36, 37, 38, 39, 40, 41, 43, 46, 47, 49, 50, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 67, 68, 71, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 85, 86, 88, 89, 91, 92, 93

Offset: 1

Benoit Cloitre, May 18 2002

Does lim_{n -> infinity} a(n)/n = 3/2?
Sum_{k=1..n} 1/gcd(n,k) = (1/n)*Sum_{d|n} phi(d)*d = (1/n)*Sum_{k=1..n} gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)), where phi = A000010. - Richard L. Ollerton, May 10 2021
The numbers of terms not exceeding 10^k, for k = 1, 2, ..., are 9, 78, 709, 6713, 65135, 637603, 6275585, 61972835, 613362869, 6080312594, ... . Apparently, the asymptotic density of this sequence is 0 and the limit in the question above is infinite. - Amiram Eldar, Jun 28 2022

			Sum_{k=1..12} 1/gcd(12,k) = 77/12 hence 12 is in the sequence.

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

Cf. A000010, A018804.

Select[Range[100],Denominator[Sum[1/GCD[#,k],{k,#}]]==#&] (* Harvey P. Dale, Dec 13 2011 *)

for(n=1,300,if(denominator(sum(i=1,n,1/gcd(n,i))) == n,print1(n,",")))

A072109 Numbers k such that Sum_{i=1..k} gcd(k,i) divides Sum_{i=1..k} lcm(k,i).

Original entry on oeis.org

1, 4, 36, 125, 469, 536, 882, 1156, 8532, 8775, 25012, 32000, 34749, 36324, 37179, 61952, 147456, 405224, 451584, 644304, 954084, 1185921, 1560546, 1562500, 1982464, 3080025, 5229378, 5784025, 6138868, 9231327, 12806144, 22108500, 25509168, 25562264, 29762208, 40894464, 45001899, 47397636, 49242375

Offset: 1

Benoit Cloitre, Jun 19 2002

nonn

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

Cf. A018804, A051193.

with(numtheory): for n from 1 to 10^6 do a := divisors(n): s1 := add(a[m]*phi(a[m]),m=1..nops(a)): s2 := add(phi(a[m])/a[m],m=1..nops(a)): if type((s1+1)/(2*s2),integer) then printf(`%d,`,n); fi: od:

f[n_] := (k = n; While[ !IntegerQ[ Sum[ LCM[k, i], {i, 1, k}] / Sum[ GCD[k, i], {i, 1, k}]], k++ ]; k); j = 1; Do[ m = f[j]; Print[m]; j = m + 1, {n, 1, 9}]
f1[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); f2[p_, e_] := e*(p - 1)/p + 1; q[n_] := IntegerQ[(1 + Times @@ f1 @@@ (fct = FactorInteger[n]))/(2 * Times @@ f2 @@@ fct)]; Select[Range[10^5], q] (* Amiram Eldar, May 02 2023 *)

for(n=1,1156,if(sum(i=1,n,lcm(n,i))%sum(i=1,n,gcd(n,i))==0,print1(n,",")))

is(n) = {my(f = factor(n)); (1 + prod(i = 1, #f~, (f[i,1]^(2*f[i,2] + 1) + 1)/(f[i,1] + 1))) % (2*prod(i = 1, #f~, (f[i,2]*(f[i,1] - 1)/f[i,1] + 1))) == 0;} \\ Amiram Eldar, May 02 2023

Numbers k such that A018804(k) divides A051193(k).

Edited by Robert G. Wilson v, Jun 22 2002
More terms from Vladeta Jovovic, Jun 22 2002
More terms from Sean A. Irvine, Feb 01 2011
Corrected definition - Richard L. Ollerton, May 06 2021

A080999 Centrality of A080997(n) = a(n)/(A080997(n))^2.

Original entry on oeis.org

1, 3, 5, 8, 15, 9, 20, 40, 27, 13, 21, 45, 39, 63, 48, 72, 100, 21, 135, 25, 65, 104, 63, 168, 33, 180, 81, 75, 195, 112, 240, 65, 37, 360, 105, 117, 189, 168, 99, 45, 243, 260, 125, 420, 195, 111, 200, 520, 315, 351, 567, 273, 57, 432, 135, 61, 165, 256, 900, 189, 375

Offset: 1

Matthew Vandermast, Mar 02 2003

nonn

A permutation of sequence A018804, which gives the sum of gcd (k,n) for 1 <= k <= n.

Cf. A080997, A080998 for centrality rankings of the positive integers.

The multiplicative formula for the numerator in a positive integer's centrality fraction is: for prime p, a(p^e)= p^(e-1)*((p-1)e+p) (cf. A018804). Dividing by the square of the integer gives the integer's centrality, which is defined to be the average fraction of the integer that it shares with the other integers as a gcd; see A080997 for other interpretations. This sequence gives the unreduced centrality numerators for A080997(n), where A080997 is the sequence of positive integers in nonincreasing order of their centrality.

cp's OEIS Frontend

A342370 a(n) = Sum_{k=1..n} gcd(k,n)^(k-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A349570 Dirichlet convolution of A011782 [2^(n-1)] with A055615 (Dirichlet inverse of n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A368737 a(n) = Sum_{k = 1..n} gcd(3*k, n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A368741 a(n) = Sum_{k = 1..n} gcd(5*k + 1, n).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

A372674 a(n) = Sum_{j=1..n} Sum_{k=1..n} tau(j*k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A372938 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{1 <= x_1, x_2, ..., x_k <= n} gcd(x_1, x_2, ..., x_k, n)^k.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A070999 Numbers n such that the denominator of Sum_{k=1..n} 1/gcd(n,k) is not equal to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A071000 Numbers m such that the denominator of Sum_{k=1..m} 1/gcd(m,k) equals m.

Views

Author

Keywords

Comments