A018804 -id:A018804 - cp's OEIS frontend

A344372 a(n) = Sum_{k = 1..n} gcd(2*k, n).

1, 4, 5, 12, 9, 20, 13, 32, 21, 36, 21, 60, 25, 52, 45, 80, 33, 84, 37, 108, 65, 84, 45, 160, 65, 100, 81, 156, 57, 180, 61, 192, 105, 132, 117, 252, 73, 148, 125, 288, 81, 260, 85, 252, 189, 180, 93, 400, 133, 260, 165, 300, 105, 324, 189, 416, 185, 228, 117, 540, 121, 244, 273

Offset: 1

Max Alekseyev, May 16 2021

For all n, a(n) >= 2*n - 1, where the equality holds if n is 1 or an odd prime.

a(n) equals the number of solutions to the congruence 2*x*y == 0 (mod n) for 1 <= x, y <= n. - Peter Bala, Jan 11 2024

			a(6) = 20: the 20 solutions to the congruence 2*x*y == 0 (mod 6) for 1 <= x, y <= 6 are the pairs (x, y) = (k, 6) for 1 <= k <= 6, the pairs (6, k) for 1 <= k <= 5, the pairs (3, k) for 1 <= k <= 5 and the pairs (1, 3), (2, 3), (4, 3) and (5, 3). - _Peter Bala_, Jan 11 2024

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

Cf. A106475, A344371, A344373.
Negated bisection of A199084.
Cf. A018804, A332794, A368736 - A368741.

seq(add((-1)^k*gcd(k, 2*n), k = 1..2*n), n = 1..70);
# alternative faster program for large n
with(numtheory): seq(add(gcd(2,d)*phi(d)*n/d, d in divisors(n)), n = 1..70); # Peter Bala, Jan 08 2024

f[p_, e_] := (e + 1)*p^e - e*p^(e - 1); f[2, e_] := (e + 1)*2^e; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 20 2022 *)
Table[Sum[GCD[2*k, n], {k, 1, n}], {n, 1, 60}] (* or *)
Table[Sum[(-1)^k * GCD[k, 2*n], {k, 1, 2*n}], {n, 1, 60}] (* Vaclav Kotesovec, Jan 13 2024 *)

{ A344372(n) = my(f=factor(n)); prod(i=1,#f~, (f[i,2]+1)*f[i,1]^f[i,2] - if(f[i,1]>2,f[i,2]*f[i, 1]^(f[i,2]-1)) ); }

a(n) = sum(k=1, 2*n, (-1)^k*gcd(k,2*n)); \\ Michel Marcus, May 17 2021

a(n) = Sum_{k = 1..2*n} (-1)^k * gcd(k,2*n).
a(n) is multiplicative with a(2^d) = (d+1)*2^d, and a(p^d) = (d+1)*p^d - d*p^(d-1) for an odd prime p, d >= 1.
a(n) = A344371(2*n) = -A199084(2*n) = 2*n - A106475(n-1).
a(n) = A018804(n) if n is odd, 4*A018804(n/2) if n is even. - Sebastian Karlsson, Aug 31 2021
From Peter Bala, Jan 11 2023: (Start)
a(n) = Sum_{d divides n} phi(2*d)*n/d, where phi(n) = A000010(n).
a(n) = - A332794(2*n); a(2*n+1) = A368736(2*n+1).
Dirichlet g.f.: 1/(1 - 1/2^s) * zeta(s-1)^2/zeta(s).
Define D(n) = Sum_{d divides n} a(d). Then
D(2*n+1) = (2*n + 1)*tau(2*n+1), where tau(n) = A000005(n), the number of divisors of n.
The sequence {(1/4)*( D(2*n) - D(n) ) : n >= 1} begins {1, 3, 6, 8, 10, 18, 14, 20, 27, 30, 22, 48, 26, 42, 60, 48, 34, 81, 38, 80, 84, 66, ...} and appears to be multiplicative. (End)
Sum_{k=1..n} a(k) ~ 4*n^2 * (log(n) - 1/2 + 2*gamma - log(2)/3 - 6*zeta'(2)/Pi^2) / Pi^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 12 2024

New name according to the formula by Peter Bala from Vaclav Kotesovec, Jan 13 2024

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

Original entry on oeis.org

0, 1, 2, 4, 4, 9, 6, 12, 12, 17, 10, 28, 12, 25, 30, 32, 16, 45, 18, 52, 44, 41, 22, 76, 40, 49, 54, 76, 28, 105, 30, 80, 72, 65, 82, 132, 36, 73, 86, 140, 40, 153, 42, 124, 144, 89, 46, 192, 84, 145, 114, 148, 52, 189, 134, 204, 128, 113, 58, 300, 60, 121, 210, 192

Offset: 1

Marc LeBrun

nonn

This sequence for a(n) also arises in the following context. If f(x) is a monic univariate polynomial of degree d>1 over Zn (= Z/nZ, the ring of integers modulo n), and we let X be the number of distinct roots of f(x) in Zn taken over all n^d choices for f(x), then the variance Var[X] = a(n)/n and the expected value E[X] = 1. - Michael Monagan, Sep 11 2015

Conjecture: a(n) != -1 (mod n) for a composite n. - Thomas Ordowski, Jun 11 2025

			a(12) = gcd(12,1) + gcd(12,2) + ... + gcd(12,11) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 = 28.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..2000 from T. D. Noe)
Marc Le Brun, Email to N. J. A. Sloane, Jul 1991.
Michael Monagan and Baris Tuncer, Some results on counting roots of polynomials and the Sylvester resultant, arXiv:1609.08712 [math.CO], 2016.

Antidiagonal sums of array A003989.

Cf. A018804.

a:= n-> add(igcd(n, k), k=1..n-1):
seq(a(n), n=1..64);

f[n_] := Sum[ GCD[n, k], {k, 1, n - 1}]; Table[ f[n], {n, 1, 60}]
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ f @@@ FactorInteger[n] - n; Array[a, 100] (* Amiram Eldar, Apr 26 2023 *)

A006579(n) = sum(k=1,n-1,gcd(n,k)) \\ Michael B. Porter, Feb 23 2010

from math import prod
from sympy import factorint
def A006579(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) - n # Chai Wah Wu, May 15 2022

a(p) = p-1 for a prime p.
a(n) = A018804(n)-n = Sum_{ d divides n } (d-1)*phi(n/d). - Vladeta Jovovic, May 04 2002
a(n+2) = Sum_{k=0..n} gcd(n-k+1, k+1) = -Sum_{k=0..4n+2} gcd(4n-k+3, k+1)*(-1)^k/4. - Paul Barry, May 03 2005
G.f.: Sum_{k>=1} phi(k) * x^(2*k) / (1 - x^k)^2. - Ilya Gutkovskiy, Feb 06 2020
a(p^k) = k(p-1)p^(k-1) for prime p. - Chai Wah Wu, May 15 2022

More terms from Robert G. Wilson v, May 04 2002

Corrected by Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 24 2002

A343497 a(n) = Sum_{k=1..n} gcd(k, n)^3.

Original entry on oeis.org

1, 9, 29, 74, 129, 261, 349, 596, 789, 1161, 1341, 2146, 2209, 3141, 3741, 4776, 4929, 7101, 6877, 9546, 10121, 12069, 12189, 17284, 16145, 19881, 21321, 25826, 24417, 33669, 29821, 38224, 38889, 44361, 45021, 58386, 50689, 61893, 64061, 76884, 68961, 91089, 79549, 99234, 101781

Offset: 1

Seiichi Manyama, Apr 17 2021

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

Column 3 of A343510.

Cf. A000010, A001157 (sigma_2(n)), A018804, A054610, A069097, A309323, A332517, A342423, A342433, A343498, A343499, A343513.

A343497:= func< n | (&+[d^3*EulerPhi(Floor(n/d)): d in Divisors(n)]) >;
[A343497(n): n in [1..50]]; // G. C. Greubel, Jun 24 2024

with(numtheory):
seq(add(phi(n/d) * d^3, d in divisors(n)), n = 1..50); # Peter Bala, Jan 20 2024

a[n_] := Sum[GCD[k, n]^3, {k, 1, n}]; Array[a, 50] (* Amiram Eldar, Apr 18 2021 *)
f[p_, e_] := p^(e - 1)*((p^2 + p + 1)*p^(2*e) - 1)/(p + 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* Amiram Eldar, Nov 22 2022 *)
A343497[n_]:= DivisorSum[n, #^3*EulerPhi[n/#] &]; Table[A343497[n], {n, 50}] (* G. C. Greubel, Jun 24 2024 *)

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

a(n) = sumdiv(n, d, eulerphi(n/d)*d^3);

a(n) = sumdiv(n, d, moebius(n/d)*d*sigma(d, 2));

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

def A343497(n): return sum(k^3*euler_phi(n/k) for k in (1..n) if (k).divides(n))
[A343497(n) for n in range(1,51)] # G. C. Greubel, Jun 24 2024

a(n) = Sum_{d|n} phi(n/d) * d^3.
a(n) = Sum_{d|n} mu(n/d) * d * sigma_2(d).
G.f.: Sum_{k >= 1} phi(k) * x^k * (1 + 4*x^k + x^(2*k))/(1 - x^k)^4.
Dirichlet g.f.: zeta(s-1) * zeta(s-3) / zeta(s). - Ilya Gutkovskiy, Apr 18 2021
Sum_{k=1..n} a(k) ~ 45*zeta(3)*n^4 / (2*Pi^4). - Vaclav Kotesovec, May 20 2021
Multiplicative with a(p^e) = p^(e-1)*((p^2+p+1)*p^(2*e) - 1)/(p+1). - Amiram Eldar, Nov 22 2022
a(n) = Sum_{1 <= i, j, k <= n} gcd(i, j, k, n) = Sum_{d divides n} d * J_3(n/d), where the Jordan totient function J_3(n) = A059376(n). - Peter Bala, Jan 20 2024

A343498 a(n) = Sum_{k=1..n} gcd(k, n)^4.

Original entry on oeis.org

1, 17, 83, 274, 629, 1411, 2407, 4388, 6729, 10693, 14651, 22742, 28573, 40919, 52207, 70216, 83537, 114393, 130339, 172346, 199781, 249067, 279863, 364204, 393145, 485741, 545067, 659518, 707309, 887519, 923551, 1123472, 1216033, 1420129, 1514003, 1843746, 1874197

Offset: 1

Seiichi Manyama, Apr 17 2021

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

Column 4 of A343510.

Cf. A000010, A001158 (sigma_3(n)), A018804, A054611, A069097, A332517, A342423, A342433, A343497, A343499, A343514.

A343498:= func< n | (&+[d^4*EulerPhi(Floor(n/d)): d in Divisors(n)]) >;
[A343498(n): n in [1..50]]; // G. C. Greubel, Jun 24 2024

a[n_] := Sum[GCD[k, n]^4, {k, 1, n}]; Array[a, 50] (* Amiram Eldar, Apr 18 2021 *)
f[p_, e_] := p^(e-1)*(p^(3*e+4) - p^(3*e) - p + 1)/(p^3-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* Amiram Eldar, Nov 22 2022 *)

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

a(n) = sumdiv(n, d, eulerphi(n/d)*d^4);

a(n) = sumdiv(n, d, moebius(n/d)*d*sigma(d, 3));

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

def A343498(n): return sum(k^4*euler_phi(n/k) for k in (1..n) if (k).divides(n))
[A343498(n) for n in range(1,51)] # G. C. Greubel, Jun 24 2024

a(n) = Sum_{d|n} phi(n/d) * d^4.
a(n) = Sum_{d|n} mu(n/d) * d * sigma_3(d).
G.f.: Sum_{k >= 1} phi(k) * x^k * (1 + 11*x^k + 11*x^(2*k) + x^(3*k))/(1 - x^k)^5.
Dirichlet g.f.: zeta(s-1) * zeta(s-4) / zeta(s). - Ilya Gutkovskiy, Apr 18 2021
Sum_{k=1..n} a(k) ~ Pi^4 * n^5 / (450*zeta(5)). - Vaclav Kotesovec, May 20 2021
Multiplicative with a(p^e) = p^(e-1)*(p^(3*e+4) - p^(3*e) - p + 1)/(p^3-1). - Amiram Eldar, Nov 22 2022
a(n) = Sum_{1 <= i, j, k, l <= n} gcd(i, j, k, l, n) = Sum_{d divides n} d * J_4(n/d), where the Jordan totient function J_4(n) = A059377(n). - Peter Bala, Jan 18 2024

A343510 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{j=1..n} gcd(j, n)^k.

Original entry on oeis.org

1, 1, 3, 1, 5, 5, 1, 9, 11, 8, 1, 17, 29, 22, 9, 1, 33, 83, 74, 29, 15, 1, 65, 245, 274, 129, 55, 13, 1, 129, 731, 1058, 629, 261, 55, 20, 1, 257, 2189, 4162, 3129, 1411, 349, 92, 21, 1, 513, 6563, 16514, 15629, 8085, 2407, 596, 105, 27, 1, 1025, 19685, 65794, 78129, 47515, 16813, 4388, 789, 145, 21

Offset: 1

Seiichi Manyama, Apr 17 2021

			G.f. of column 3: Sum_{i>=1} phi(i) * (x^i + 4*x^(2*i) + x^(3*i))/(1 - x^i)^4.
Square array begins:
   1,  1,   1,    1,     1,      1,      1, ...
   3,  5,   9,   17,    33,     65,    129, ...
   5, 11,  29,   83,   245,    731,   2189, ...
   8, 22,  74,  274,  1058,   4162,  16514, ...
   9, 29, 129,  629,  3129,  15629,  78129, ...
  15, 55, 261, 1411,  8085,  47515, 282381, ...
  13, 55, 349, 2407, 16813, 117655, 823549, ...

Seiichi Manyama, Antidiagonals n = 1..140, flattened
Peter Bala, GCD sum theorems. Two Multivariable Cesaro Type Identities.
Eric Weisstein's World of Mathematics, Eulerian Number and Euler's Number Triangle

Columns k=1..7 give A018804, A069097, A343497, A343498, A343499, A343508, A343509.
T(n-2,n) gives A342432.
T(n-1,n) gives A342433.
T(n,n) gives A332517.
T(n,n+1) gives A321294.
Cf. A008292, A343516.

T[n_, k_] := DivisorSum[n, EulerPhi[n/#] * #^k &]; Table[T[k, n - k + 1], {n, 1, 11}, {k, 1, n}] // Flatten (* Amiram Eldar, Apr 18 2021 *)

PARI
```
T(n, k) = sum(j=1, n, gcd(j, n)^k);
```

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

T(n, k) = sumdiv(n, d, moebius(n/d)*d*sigma(d, k-1));

G.f. of column k: Sum_{i>=1} phi(i) * ( Sum_{j=1..k} A008292(k, j) * x^(i*j) )/(1 - x^i)^(k+1).
T(n,k) = Sum_{d|n} phi(n/d) * d^k.
T(n,k) = Sum_{d|n} mu(n/d) * d * sigma_{k-1}(d).
Dirichlet g.f. of column k: zeta(s-1) * zeta(s-k) / zeta(s). - Ilya Gutkovskiy, Apr 18 2021
T(n,k) = Sum_{j=1..n} (n/gcd(n,j))^k*phi(gcd(n,j))/phi(n/gcd(n,j)). - Richard L. Ollerton, May 10 2021
T(n,k) = Sum_{1 <= j_1, j_2, ..., j_k <= n} gcd(j_1, j_2, ..., j_k)^2 = Sum_{d divides n} d * J_k(n/d), where J_k(n) denotes the k-th Jordan totient function. - Peter Bala, Jan 29 2024

A299149 Numerators of the positive solution to n = Sum_{d|n} a(d) * a(n/d).

Original entry on oeis.org

1, 1, 3, 3, 5, 3, 7, 5, 27, 5, 11, 9, 13, 7, 15, 35, 17, 27, 19, 15, 21, 11, 23, 15, 75, 13, 135, 21, 29, 15, 31, 63, 33, 17, 35, 81, 37, 19, 39, 25, 41, 21, 43, 33, 135, 23, 47, 105, 147, 75, 51, 39, 53, 135, 55, 35, 57, 29, 59, 45, 61, 31, 189, 231, 65, 33

Offset: 1

Gus Wiseman, Feb 03 2018

Dirichlet convolution of a(n)/A046644(n) with itself yields A000265. - Antti Karttunen, Aug 30 2018

			Sequence begins: 1, 1, 3/2, 3/2, 5/2, 3/2, 7/2, 5/2, 27/8, 5/2, 11/2, 9/4, 13/2, 7/2.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms Andrew Howroyd)
Vaclav Kotesovec, Graph - the asymptotic ratio (65537 terms)
Wikipedia, Dirichlet convolution.

Cf. A000010, A000265, A003958, A007431, A018804, A023900, A029935, A046643, A046644, A165825, A257098, A298971, A299119, A299150 (denominators), A299151, A317848, A318319, A318321, A318649.

nn=50;
sys=Table[n==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Numerator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]
odd[n_] := n/2^IntegerExponent[n, 2]; f[p_, e_] := odd[p^e*Binomial[2*e, e]]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 30 2023 *)

a(n)={my(v=factor(n)[,2]); numerator(n*prod(i=1, #v, my(e=v[i]); binomial(2*e, e)/4^e))} \\ Andrew Howroyd, Aug 09 2018

\\ DirSqrt(v) finds u such that v = v[1]*dirmul(u, u).
DirSqrt(v)={my(n=#v, u=vector(n)); u[1]=1; for(n=2, n, u[n]=(v[n]/v[1] - sumdiv(n, d, if(d>1&&dAndrew Howroyd, Aug 09 2018

for(n=1, 100, print1(numerator(direuler(p=2, n, 1/(1-p*X)^(1/2))[n]), ", ")) \\ Vaclav Kotesovec, May 09 2025

a(n) = numerator(n*A317848(n)/A165825(n)) = A000265(n*A317848(n)). - Andrew Howroyd, Aug 09 2018

Sum_{k=1..n} A299149(k)/A299150(k) ~ n^2 / (2*sqrt(Pi*log(n))) * (1 + (1-gamma) / (4*log(n))), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, May 09 2025

Keyword:mult added by Andrew Howroyd, Aug 09 2018

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

Original entry on oeis.org

1, 1, 3, 1, 4, 5, 1, 5, 8, 8, 1, 6, 12, 15, 9, 1, 7, 17, 26, 19, 15, 1, 8, 23, 42, 39, 35, 13, 1, 9, 30, 64, 74, 76, 34, 20, 1, 10, 38, 93, 130, 153, 90, 56, 21, 1, 11, 47, 130, 214, 287, 216, 152, 63, 27, 1, 12, 57, 176, 334, 506, 468, 379, 191, 86, 21

Offset: 1

Seiichi Manyama, Apr 17 2021

			T(4,2) = gcd(1,1,4) + gcd(1,2,4) + gcd(2,2,4) + gcd(1,3,4) + gcd(2,3,4) + gcd(3,3,4) + gcd(1,4,4) + gcd(2,4,4) + gcd(3,4,4) + gcd(4,4,4) = 1 + 1 + 2 + 1 + 1 + 1 + 1 + 2 + 1 + 4 = 15.
Square array begins:
   1,  1,  1,   1,   1,   1,    1, ...
   3,  4,  5,   6,   7,   8,    9, ...
   5,  8, 12,  17,  23,  30,   38, ...
   8, 15, 26,  42,  64,  93,  130, ...
   9, 19, 39,  74, 130, 214,  334, ...
  15, 35, 76, 153, 287, 506,  846, ...
  13, 34, 90, 216, 468, 930, 1722, ...

Seiichi Manyama, Antidiagonals n = 1..140, flattened

Columns k=1..7 give A018804, A309322, A309323, A343518, A343519, A343520, A343521.
Main diagonal gives A343517.
T(n,n-1) gives A343553.
Cf. A343510.

T[n_, k_] := DivisorSum[n, EulerPhi[n/#] * Binomial[k + # - 1, k] &]; Table[T[k, n - k + 1], {n, 1, 11}, {k, 1, n}] // Flatten (* Amiram Eldar, Apr 18 2021 *)

T(n, k) = sumdiv(n, d, eulerphi(n/d)*binomial(d+k-1, k));

G.f. of column k: Sum_{j>=1} phi(j) * x^j/(1 - x^j)^(k+1).

T(n,k) = Sum_{d|n} phi(n/d) * binomial(d+k-1, k).

A051193 a(n) = Sum_{k=1..n} lcm(n,k).

Original entry on oeis.org

1, 4, 12, 24, 55, 66, 154, 176, 279, 320, 616, 468, 1027, 910, 1110, 1376, 2329, 1656, 3268, 2320, 3171, 3674, 5842, 3624, 6525, 6136, 7398, 6636, 11803, 6630, 14446, 10944, 12837, 13940, 15820, 12096, 24679, 19570, 21450, 18080, 33661, 18984, 38872, 26884

Offset: 1

Clark Kimberling

nonn

Akshay Bansal, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Akshay Bansal, C Program.
Soichi Ikeda and Kaneaki Matsuoka, On the Lcm-Sum Function, Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.7.
László Tóth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.
Index entries for sequences related to lcm's.

Cf. A000010, A018804, A051173 (triangle whose n-th row sum is a(n)), A057660, A057661.

a051193 = sum . a051173_row  -- Reinhard Zumkeller, Feb 11 2014

a:=n->add(ilcm( n, j ), j=1..n): seq(a(n), n=1..50); # Zerinvary Lajos, Nov 07 2006

Table[Sum[LCM[k, n], {k, 1, n}], {n, 1, 39}] (* Geoffrey Critzer, Feb 16 2015 *)
f[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); a[n_] := n * (1 + Times @@ f @@@ FactorInteger[n])/2; Array[a, 100] (* Amiram Eldar, Apr 26 2023 *)

a(n) = sum(k=1, n, lcm(n,k)); \\ Michel Marcus, Feb 06 2015

from math import prod
from sympy import factorint
def A051193(n): return n*(1+prod((p**((e<<1)+1)+1)//(p+1) for p,e in factorint(n).items())>>1) # Chai Wah Wu, Aug 05 2024

a(n) = n*(1+Sum_{d|n} d*phi(d))/2 = n*(1+A057660(n))/2 = n*A057661(n). - Vladeta Jovovic, Jun 21 2002
G.f.: x*f'(x), where f(x) = x/(2*(1 - x)) + (1/2)*Sum_{k>=1} k*phi(k)*x^k/(1 - x^k) and phi() is the Euler totient function (A000010). - Ilya Gutkovskiy, Aug 31 2017
Sum_{k=1..n} a(k) ~ 3 * zeta(3) * n^4 / (4*Pi^2). - Vaclav Kotesovec, May 29 2021

A196443 a(n) = the sum of GCQ_A(n, k) for 1 <= k <= n (see definition in comments).

Original entry on oeis.org

0, 0, 2, 3, 9, 9, 20, 24, 32, 41, 54, 55, 77, 87, 100, 115, 135, 145, 170, 180, 205, 227, 252, 263, 298, 321, 346, 372, 405, 424, 464, 490, 523, 557, 592, 616, 665, 699, 736, 768, 819, 850, 902, 940, 983, 1031, 1080, 1113, 1174, 1219

Offset: 1

Jaroslav Krizek, Nov 26 2011

nonn

Definition of GCQ_A: The greatest common non-divisor of type A (GCQ_A) of two positive integers a and b (a<=b) is the largest positive non-divisor q of numbers a and b such that 1<=q<=a common to a and b; GCQ_A(a, b) = 0 if no such c exists.

GCQ_A(1, b) = GCQ_A(2, b) = 0 for b >=1. GCQ_A(a, b) = 0 or >= 2.

			 For n = 6, a(6) = 9 because GCQ_A(6, 1) = 0, GCQ_A(6, 2) = 0, GCQ_A(6, 3) = 0, GCQ_A(6, 4) = 0, GCQ_A(6, 5) = 4, GCQ_A(6, 6) = 5. Sum of results is 9.

Cf. A196437, A196438, A196439, A196440, A196441, A196442, A196444, A018804.
Cf. A199972 (the sum of GCQ_B(n, k) for 1<= k <= n).
Cf. A199973 (the sum of LCQ_B(n, k) for 1 <= k <= n).

A372792 Number of divisors of 12n; a(n) = tau(12n) = A000005(12n).

Original entry on oeis.org

6, 8, 9, 10, 12, 12, 12, 12, 12, 16, 12, 15, 12, 16, 18, 14, 12, 16, 12, 20, 18, 16, 12, 18, 18, 16, 15, 20, 12, 24, 12, 16, 18, 16, 24, 20, 12, 16, 18, 24, 12, 24, 12, 20, 24, 16, 12, 21, 18, 24, 18, 20, 12, 20, 24, 24, 18, 16, 12, 30, 12, 16, 24, 18, 24, 24

Offset: 1

Vaclav Kotesovec, May 13 2024

nonn

In general, 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.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Vaclav Kotesovec, Graph - the asymptotic ratio (100000 terms)

Cf. A000005, A099777, A372713, A372784, A372785, A372786, A372787, A372788, A372789, A372790, A372791.

Table[DivisorSigma[0, 12*n], {n, 1, 150}]

A372792(n) = numdiv(12*n); \\ Antti Karttunen, Jul 19 2024

Sum_{k=1..n} a(k) ~ (40*n*(log(n) + 2*gamma - 1) + n*(20*log(2) + 8*log(3))) / 12, where gamma is the Euler-Mascheroni constant A001620.

cp's OEIS Frontend

A344372 a(n) = Sum_{k = 1..n} gcd(2*k, n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A343497 a(n) = Sum_{k=1..n} gcd(k, n)^3.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

SageMath

Formula

A343498 a(n) = Sum_{k=1..n} gcd(k, n)^4.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

PARI

SageMath

Formula

A343510 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{j=1..n} gcd(j, n)^k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A299149 Numerators of the positive solution to n = Sum_{d|n} a(d) * a(n/d).

Views

Author

Keywords

A372792 Number of divisors of 12n; a(n) = tau(12n) = A000005(12n).