A018804 -id:A018804 - cp's OEIS frontend

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

1, 5, 29, 262, 3129, 46705, 823549, 16777544, 387421251, 10000003469, 285311670621, 8916100581446, 302875106592265, 11112006826387025, 437893890391180013, 18446744073743123788, 827240261886336764193, 39346408075299116257065

Offset: 1

Seiichi Manyama, Mar 13 2021

nonn

Cf. A000010, A001923, A018804, A050873, A231712, A332517, A341036, A342370, A342389, A342423.

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

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

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

A347104 Dirichlet g.f.: primezeta(s-1) * zeta(s-1) / zeta(s).

Original entry on oeis.org

0, 2, 3, 2, 5, 7, 7, 4, 6, 13, 11, 10, 13, 19, 22, 8, 17, 18, 19, 18, 32, 31, 23, 20, 20, 37, 18, 26, 29, 38, 31, 16, 52, 49, 58, 24, 37, 55, 62, 36, 41, 56, 43, 42, 54, 67, 47, 40, 42, 60, 82, 50, 53, 54, 94, 52, 92, 85, 59, 60, 61, 91, 78, 32, 112, 92, 67, 66, 112, 106, 71, 48, 73, 109, 100

Offset: 1

Ilya Gutkovskiy, Aug 18 2021

nonn

a(n) is the sum of the prime terms in row n of A050873.

Moebius transform of A328260.

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

Cf. A000010, A001221, A008472, A010051, A018804, A050873, A061397, A078439, A117494, A122411, A255655, A328260, A329354.

Table[DivisorSum[n, MoebiusMu[n/#] # PrimeNu[#] &], {n, 1, 75}]
Table[DivisorSum[n, # EulerPhi[n/#] &, PrimeQ[#] &], {n, 1, 75}]
Table[Sum[Boole[PrimeQ[GCD[n, k]]] GCD[n, k], {k, 1, n}], {n, 1, 75}]

a(n) = sumdiv(n, d, moebius(n/d)*d*omega(d)); \\ Michel Marcus, Aug 18 2021

a(n) = Sum_{d|n} mu(n/d) * d * omega(d).
a(n) = Sum_{p|n, p prime} p * phi(n/p).
a(n) = Sum_{k=1..n} A010051(gcd(n,k)) * gcd(n,k).

A347137 a(n) = Sum_{d|n} phi(d) * A003961(n/d), where A003961 shifts the prime factorization of its argument one step towards larger primes, and phi is Euler totient function.

Original entry on oeis.org

1, 4, 7, 14, 11, 28, 17, 46, 41, 44, 23, 98, 29, 68, 77, 146, 35, 164, 41, 154, 119, 92, 51, 322, 97, 116, 223, 238, 59, 308, 67, 454, 161, 140, 187, 574, 77, 164, 203, 506, 83, 476, 89, 322, 451, 204, 99, 1022, 229, 388, 245, 406, 111, 892, 253, 782, 287, 236, 119, 1078, 127, 268, 697, 1394, 319, 644, 137, 490

Offset: 1

Antti Karttunen, Aug 24 2021

Dirichlet convolution of Euler phi (A000010) with the prime shift function (A003961). Multiplicative because both A000010 and A003961 are.
Dirichlet convolution of the identity function (A000027) with the prime shifted phi (A003972).
Möbius transform of A347136.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Index entries for sequences computed from indices in prime factorization.

Cf. A000010, A000027, A000040, A001043, A003961, A003972, A008683, A151800, A347122, A347136 (inverse Möbius transform).

Cf. also A018804, A347237.

f[p_, e_] := (q = NextPrime[p])^e + (p - 1)*(q^e - p^e)/(q - p); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 16 2023 *)

A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A347137(n) = sumdiv(n,d,eulerphi(n/d)*A003961(d));

a(n) = Sum_{d|n} A000010(n/d) * A003961(d).
a(n) = Sum_{d|n} d * A003972(n/d).
a(n) = Sum_{d|n} A008683(n/d) * A347136(d).
a(n) = A347122(n) + 2*A000010(n).
a(A000040(n)) = A001043(n) - 1.
Multiplicative with a(p^e) = q(p)^e + (p-1)*(q(p)^e - p^e)/(q(p) - p), where q(p) = nextprime(p) = A151800(p). - Amiram Eldar, Sep 16 2023

A349123 a(n) = Sum_{d|n} A038040(n/d) * A003415(d), where A038040(n) = n*tau(n), and A003415 is the arithmetic derivative of n.

Original entry on oeis.org

0, 1, 1, 8, 1, 15, 1, 40, 12, 21, 1, 96, 1, 27, 24, 160, 1, 126, 1, 144, 30, 39, 1, 440, 20, 45, 90, 192, 1, 279, 1, 560, 42, 57, 36, 720, 1, 63, 48, 680, 1, 369, 1, 288, 234, 75, 1, 1680, 28, 270, 60, 336, 1, 810, 48, 920, 66, 93, 1, 1656, 1, 99, 306, 1792, 54, 549, 1, 432, 78, 531, 1, 3120, 1, 117, 330, 480, 54, 639

Offset: 1

Antti Karttunen, Nov 08 2021

nonn

This sequence is the Dirichlet convolution of at least the following pairs of sequences:
  - A003415 (the arithmetic derivative) with A038040,
  - A000027 (the identity function) with A347130,
  - A000203 (sigma) with A347131,
  - A018804 with A319684,
  - A060640 with A300251.

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

Cf. A000027, A000203, A003415, A003557, A018804, A060640, A300251, A319684, A347130, A349124.

Cf. also A348983, A349143.

d[1] = 0; d[n_] := n*Plus @@ ((Last[#]/First[#]) & /@ FactorInteger[n]); a[n_] := DivisorSum[n, d[#]*(n/#)*DivisorSigma[0, n/#] &]; Array[a, 100] (* Amiram Eldar, Nov 08 2021 *)

A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A038040(n) = (n*numdiv(n));
A349123(n) = sumdiv(n,d,A038040(d)*A003415(n/d));

a(n) = Sum_{d|n} A038040(d) * A003415(n/d).
a(n) = Sum_{d|n} d * A347130(n/d).
a(n) = Sum_{d|n} A000203(d) * A347131(n/d).
a(n) = Sum_{d|n} A018804(d) * A319684(n/d).
a(n) = Sum_{d|n} A060640(d) * A300251(n/d).
For all n >= 1, A348983(n) <= a(n) <= A349143(n).
a(n) = A003557(n) * A349124(n).

A384628 a(n) = Sum_{k = 1..n} gcd(n, floor(n / k)).

Original entry on oeis.org

1, 3, 5, 8, 9, 14, 13, 20, 19, 25, 21, 35, 25, 37, 37, 44, 33, 56, 37, 60, 51, 58, 45, 84, 53, 71, 69, 85, 57, 103, 61, 99, 83, 93, 83, 130, 73, 104, 101, 136, 81, 146, 85, 140, 129, 124, 93, 188, 103, 155, 131, 163, 105, 191, 127, 185, 145, 159, 117, 251, 121

Offset: 1

Ctibor O. Zizka, Jun 05 2025

nonn

a(p) = A018804(p) for p prime (A000040).

Empirical observation: A005408(n) <= a(n) < (2 + sqrt(2)/10)*A000203(n).

			n = 3: a(3) = Sum_{k = 1..3} gcd(3, floor(3 / k)) = 3 + 1 + 1 = 5.
n = 4: a(4) = Sum_{k = 1..4} gcd(4, floor(4 / k)) = 4 + 2 + 1 + 1 = 8.

Cf. A000040, A000203, A005408, A018804.

a[n_] := Sum[GCD[n, Floor[n/k]], {k, 1, n}]; Array[a, 100] (* Amiram Eldar, Jun 05 2025 *)

a(n) = sum(k=1, n, gcd(n, n\k)); \\ Michel Marcus, Jun 05 2025

from math import gcd
def A384628(n):
    c, j = (n<<1)+1, 2
    k1 = n//j
    while k1>1:
        j2 = n//k1+1
        c += (j2-j)*gcd(n,k1)
        j, k1 = j2, n//j2
    return c-j # Chai Wah Wu, Jun 17 2025

For p prime: a(p) = 2*p - 1.

A081001 n is in the sequence if and only if it does not rank among the top n positive integers in centrality (cf. A080997 for fuller explanation of this concept).

Original entry on oeis.org

5, 7, 9, 11, 13, 17, 19, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, 51, 53, 55, 57, 58, 59, 61, 62, 65, 67, 69, 71, 73, 74, 77, 79, 81, 82, 83, 85, 86, 87, 89, 91, 92, 93, 94, 95, 97, 101, 103, 106, 107, 109, 111, 113, 115, 116, 118, 119

Offset: 1

Matthew Vandermast, Mar 02 2003

nonn

Complement of A081000.

Cf. A080997, A080998, also A081028 for centrality ranks of primes (all of which are members of this sequence except 2 and 3).

Formula for the centrality of n: A018804(n)/n^2 (see also A080997).

A081028 Numbers n such that n-th term of A080997 is prime; a(n) is ranking of n-th prime number among the positive integers in terms of centrality (cf. A080997 for explanation of this concept).

Original entry on oeis.org

2, 3, 6, 10, 18, 20, 25, 33, 40, 53, 56, 69, 79, 89, 95, 108

Offset: 1

Matthew Vandermast, Mar 02 2003

nonn

Let p(n) be the n-th prime. In order for the centrality rankings of all numbers from 1 to p(n) to be known, it is necessary for the numbers that occupy all of the ranking positions from 1 to a(n) to be determined.

Cf. A080997, A080998.

Formula for centrality of n: A018804(n)/n^2 (see also A080997).

A081029 Highly central numbers: numbers having a centrality higher than that of any larger number.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 15, 18, 20, 24, 30, 36, 40, 42, 48, 60, 72, 84, 90, 120, 126, 144, 180, 210, 240

Offset: 1

Matthew Vandermast, Mar 02 2003

nonn

A subset of A081000.

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

Formula for centrality of n: A018804(n)/n^2 (cf. A080997 for fuller description of this concept).

A234307 a(n) = Sum_{i=1..n} gcd(2*n-i, i).

Original entry on oeis.org

1, 3, 6, 8, 11, 17, 16, 20, 27, 31, 26, 44, 31, 45, 60, 48, 41, 75, 46, 80, 87, 73, 56, 108, 85, 87, 108, 116, 71, 165, 76, 112, 141, 115, 158, 192, 91, 129, 168, 196, 101, 239, 106, 188, 261, 157, 116, 256, 175, 235, 222, 224, 131, 297, 256, 284, 249, 199

Offset: 1

Wesley Ivan Hurt, Dec 22 2013

Sum of the GCD's of the smallest and largest parts in the partitions of 2n into exactly two parts.

			a(6) = 17; the partitions of 2(6) = 12 into two parts are: (11,1),(10,2),(9,3),(8,4),(7,5),(6,6). Then a(6) = gcd(11,1) + gcd(10,2) + gcd(9,3) + gcd(8,4) + gcd(7,5) + gcd(6,6) = 1 + 2 + 3 + 4 + 1 + 6 = 17.

Seiichi Manyama, Table of n, a(n) for n = 1..10000
Index entries for sequences related to partitions.

Cf. A001105 (sum of parts), A002378 (differences of parts).

Cf. A001620, A018804, A306016.

A234307:=n->add( gcd(2*n-i, i), i=1..n); seq(A234307(n), n=1..100);

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

a(n) = sum(i=1, n, gcd(i, 2*n-i)); \\ Michel Marcus, Dec 23 2013

a(n) = {my(f = factor(2*n)); (prod(i = 1, #f~, p = f[i, 1]; e = f[i, 2]; p^(e-1)*(p+e*(p-1))) - n)/2;} \\ Amiram Eldar, Mar 30 2024

a(n) = Sum_{i=1..n} gcd(2*n-i, i).
a(n) = (A018804(2*n)-n)/2. - Sebastian Karlsson, Oct 03 2021
Conjecture: a(n) = (1/4)*Sum_{k = 1..4*n} (-1)^k *gcd(k, 8*n). - Peter Bala, Jan 01 2024
Sum_{k=1..n} a(k) ~ (Pi^2/4)*n^2 * (log(n) + 2*gamma - 1/2 + log(2)/6 - Pi^2/16 - zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). - Amiram Eldar, Mar 30 2024

A321294 a(n) = Sum_{d|n} mu(n/d)dsigma_n(d).

Original entry on oeis.org

1, 9, 83, 1058, 15629, 282381, 5764807, 134480900, 3486902505, 100048836321, 3138428376731, 107006403495850, 3937376385699301, 155572843119518781, 6568408661060858767, 295150157013526773768, 14063084452067724991025, 708236697425777157039381

Offset: 1

Ilya Gutkovskiy, Nov 02 2018

nonn

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

Cf. A018804, A069097, A320940, A332517, A342432, A342433.

Table[Sum[MoebiusMu[n/d] d DivisorSigma[n, d], {d, Divisors[n]}], {n, 18}]
Table[Sum[EulerPhi[n/d] d^(n + 1), {d, Divisors[n]}], {n, 18}]
Table[Sum[GCD[n, k]^(n + 1), {k, n}], {n, 18}]

a(n) = sumdiv(n, d, moebius(n/d)*d*sigma(d, n)); \\ Michel Marcus, Nov 03 2018

from sympy import totient, divisors
def A321294(n):
    return sum(totient(d)*(n//d)**(n+1) for d in divisors(n,generator=True)) # Chai Wah Wu, Feb 15 2020

a(n) = [x^n] Sum_{i>=1} Sum_{j>=1} mu(i)*j^(n+1)*x^(i*j)/(1 - x^(i*j))^2.
a(n) = Sum_{d|n} phi(n/d)*d^(n+1).
a(n) = Sum_{k=1..n} gcd(n,k)^(n+1).
a(n) ~ n^(n+1). - Vaclav Kotesovec, Nov 02 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A347104 Dirichlet g.f.: primezeta(s-1) * zeta(s-1) / zeta(s).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A347137 a(n) = Sum_{d|n} phi(d) * A003961(n/d), where A003961 shifts the prime factorization of its argument one step towards larger primes, and phi is Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349123 a(n) = Sum_{d|n} A038040(n/d) * A003415(d), where A038040(n) = n*tau(n), and A003415 is the arithmetic derivative of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384628 a(n) = Sum_{k = 1..n} gcd(n, floor(n / k)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A081001 n is in the sequence if and only if it does not rank among the top n positive integers in centrality (cf. A080997 for fuller explanation of this concept).

Views

Author

Keywords

Comments

Crossrefs

Formula

A081028 Numbers n such that n-th term of A080997 is prime; a(n) is ranking of n-th prime number among the positive integers in terms of centrality (cf. A080997 for explanation of this concept).

Views

Author

Keywords

Comments

Crossrefs

Formula

A081029 Highly central numbers: numbers having a centrality higher than that of any larger number.

Views

Author

Keywords

Comments

Crossrefs

Formula

A234307 a(n) = Sum_{i=1..n} gcd(2*n-i, i).

Views

Author

Keywords

A321294 a(n) = Sum_{d|n} mu(n/d)dsigma_n(d).