A018804 -id:A018804 - cp's OEIS frontend

A272718 Partial sums of gcd-sum sequence A018804.

1, 4, 9, 17, 26, 41, 54, 74, 95, 122, 143, 183, 208, 247, 292, 340, 373, 436, 473, 545, 610, 673, 718, 818, 883, 958, 1039, 1143, 1200, 1335, 1396, 1508, 1613, 1712, 1829, 1997, 2070, 2181, 2306, 2486, 2567, 2762, 2847, 3015, 3204, 3339, 3432, 3672, 3805, 4000, 4165

Offset: 1

Gareth McCaughan, May 05 2016

a(n) is the sum of all pairs of greater common divisors for (i,j) where 1 <= i <= j <= n. - Jianing Song, Feb 07 2021

			The gcd-sum function takes values 1,3,5 for n = 1,2,3; therefore a(3) = 1+3+5 = 9.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Olivier Bordellès, A note on the average order of the gcd-sum function, Journal of Integer Sequences, Vol. 10 (2007), Article 07.3.3.

Partial sums of A018804.

Cf. A018806, A000010, A001620, A074962, A178881.

b[n_] := GCD[n, #]& /@ Range[n] // Total;
Array[b, 100] // Accumulate (* Jean-François Alcover, Jun 05 2021 *)
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; s[n_] := Times @@ f @@@ FactorInteger[n]; Accumulate[Array[s, 100]] (* Amiram Eldar, Dec 10 2024 *)

first(n)=my(v=vector(n),f); v[1]=1; for(i=2,n, f=factor(i); v[i] = v[i-1] + prod(j=1, #f~, (f[j, 2]*(f[j, 1]-1)/f[j, 1] + 1)*f[j, 1]^f[j, 2])); v \\ Charles R Greathouse IV, May 05 2016

According to Bordellès (2007), a(n) = (n^2 / (2*zeta(2)))*(log n + gamma - 1/2 + log(A^12/(2*Pi))) + O(n^(1+theta+epsilon)) where gamma = A001620, A ~= 1.282427129 is the Glaisher-Kinkelin constant A074962, theta is a certain constant defined in terms of the divisor function and known to lie between 1/4 and 131/416, and epsilon is any positive number.
G.f.: (1/(1 - x))*Sum_{k>=1} phi(k)*x^k/(1 - x^k)^2, where phi(k) is the Euler totient function. - Ilya Gutkovskiy, Jan 02 2017
a(n) = (1/2)*Sum_{k=1..n} phi(k) * floor(n/k) * floor(1+n/k), where phi(k) is the Euler totient function. - Daniel Suteu, May 28 2018
From Jianing Song, Feb 07 2021: (Start)
a(n) = Sum_{i=1..n, j=i..n} gcd(i,j).
a(n) = (A018806(n) + n*(n+1)/2) / 2 = (Sum_{k=1..n} phi(k)*(floor(n/k))^2 + n*(n+1)/2) / 2, phi = A000010.
a(n) = A178881(n) + n*(n+1)/2.
a(n) = A018806(n) - A178881(n). (End)

A101035 Dirichlet inverse of the gcd-sum function (A018804).

Original entry on oeis.org

1, -3, -5, 1, -9, 15, -13, 1, 4, 27, -21, -5, -25, 39, 45, 1, -33, -12, -37, -9, 65, 63, -45, -5, 16, 75, 4, -13, -57, -135, -61, 1, 105, 99, 117, 4, -73, 111, 125, -9, -81, -195, -85, -21, -36, 135, -93, -5, 36, -48, 165, -25, -105, -12, 189, -13, 185, 171, -117, 45, -121, 183, -52, 1, 225, -315, -133, -33, 225, -351, -141, 4

Offset: 1

Gerard P. Michon, Nov 27 2004

			a(4)=1, a(8)=1, a(16)=1, a(32)=1, etc. because of the multiplicative definition for powers of 2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
G. P. Michon, Multiplicative Functions.

Cf. A018804, A055615, A046692, A023900, A007427, A053822, A053825, A053826.

Cf. A008683.

a101035 n = product $ zipWith f (a027748_row n) (a124010_row n) where
   f p 1 = 1 - 2 * p
   f p e = (p - 1) ^ 2
-- Reinhard Zumkeller, Jul 16 2012

DirichletInverse[f_][1] = 1/f[1]; DirichletInverse[f_][n_] := DirichletInverse[f][n] = -1/f[1]*Sum[ f[n/d]*DirichletInverse[f][d], {d, Most[ Divisors[n]]}]; GCDSum[n_] := Sum[ GCD[n, k], {k, 1, n}]; Table[ DirichletInverse[ GCDSum][n], {n, 1, 72}](* Jean-François Alcover, Dec 12 2011 *)
f[p_, e_] := If[e == 1, 1 - 2*p, (p - 1)^2]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Dec 06 2022 *)

seq(n)={dirdiv(vector(n, n, n==1), vector(n, n, sumdiv(n, d, n*eulerphi(d)/d)))} \\ Andrew Howroyd, Aug 05 2018

for(n=1, 100, print1(direuler(p=2, n, (1 - p*X)^2/(1 - X))[n], ", ")) \\ Vaclav Kotesovec, Aug 22 2021

Multiplicative function with a(p)=1-2p and a(p^e)=(p-1)^2 when e>1 [p prime].
Dirichlet g.f.: zeta(s)/zeta^2(s-1). - R. J. Mathar, Apr 10 2011
a(n) = Sum{d|n} tau_{-2}(d)*d, where tau_{-2} is A007427. - Enrique Pérez Herrero, Jan 19 2013
Conjecture: Logarithmic g.f. Sum_{n>0,k>0} mu(n)*mu(k)*log(1/(1-x^(n*k))). - Benedict W. J. Irwin, Jul 26 2017

A080998 a(n) is n's rank among the positive integers in terms of centrality -the fraction of n represented by the average gcd of n and the positive integers, or A018804(n)/n^2 (cf. A080997).

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 10, 7, 11, 9, 18, 8, 20, 13, 12, 15, 25, 14, 33, 16, 21, 23, 40, 17, 32, 28, 27, 22, 53, 19, 56, 30, 35, 39, 36, 24, 69, 46, 43, 26, 79, 29, 89, 38, 37, 55, 95, 31, 67, 45, 57, 47, 108, 41, 60, 42, 65, 75

Offset: 1

Matthew Vandermast, Mar 02 2003

nonn

			a(5)=6 because the centrality of 5 is 9/25 (.36), which places it sixth among positive integers in centrality; it ranks behind 1 (whose centrality is 1), 2 (3/4, .75), 3 (5/9, .555...), 4 (1/2, .5) and 6 (5/12, .41666...).

A080997 gives fuller description of centrality, as well as finite portion of the arrangement of positive integers in order of their centrality. For more about where numbers occur in A080997, see also A081000, A081001, A081028, A081029.

A348494 a(n) = A348492(n) / A003557(n), where A348492 is the GCD of the arithmetic derivative (A003415) and Pillai's arithmetical function (A018804).

Original entry on oeis.org

1, 1, 1, 2, 1, 5, 1, 1, 1, 1, 1, 4, 1, 3, 1, 2, 1, 7, 1, 12, 5, 1, 1, 1, 1, 15, 3, 4, 1, 1, 1, 1, 7, 1, 3, 2, 1, 3, 1, 1, 1, 1, 1, 12, 1, 5, 1, 2, 1, 3, 5, 4, 1, 9, 1, 1, 1, 1, 1, 2, 1, 3, 1, 2, 9, 1, 1, 12, 1, 1, 1, 1, 1, 3, 1, 4, 3, 1, 1, 2, 1, 1, 1, 2, 11, 15, 1, 35, 1, 1, 5, 12, 1, 1, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1

Offset: 1

Antti Karttunen, Oct 21 2021

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A003415, A003557, A018804, A342001, A347128, A348492, A348500 [= a(A276086(n))].

Cf. also A348496.

Array[GCD[Total@ GCD[#1, Range[#1]], #1 Total[#2/#1 & @@@ #2]]/Apply[Times, Map[#1^(#2 - 1) & @@ # &, #2]] & @@ {#, FactorInteger[#]} &, 105] (* Michael De Vlieger, Oct 21 2021 *)

A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A003557(n) = (n/factorback(factorint(n)[, 1]));
A018804(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ From A018804
A348492(n) = gcd(A003415(n), A018804(n));
A348494(n) = (A348492(n)/A003557(n));

a(n) = gcd(A342001(n), A347128(n)).

a(n) = A348492(n) / A003557(n), where A348492(n) = gcd(A003415(n), A018804(n)).

A348492 Greatest common divisor of the arithmetic derivative (A003415) and Pillai's arithmetical function (A018804).

Original entry on oeis.org

1, 1, 1, 4, 1, 5, 1, 4, 3, 1, 1, 8, 1, 3, 1, 16, 1, 21, 1, 24, 5, 1, 1, 4, 5, 15, 27, 8, 1, 1, 1, 16, 7, 1, 3, 12, 1, 3, 1, 4, 1, 1, 1, 24, 3, 5, 1, 16, 7, 15, 5, 8, 1, 81, 1, 4, 1, 1, 1, 4, 1, 3, 3, 64, 9, 1, 1, 24, 1, 1, 1, 12, 1, 3, 5, 8, 3, 1, 1, 16, 27, 1, 1, 4, 11, 15, 1, 140, 1, 3, 5, 24, 1, 1, 3, 16, 1, 7

Offset: 1

Antti Karttunen, Oct 21 2021

nonn

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

Cf. A003415, A003557, A018804, A348493, A348494.

Cf. also A342413, A342458, A348495.

Array[GCD[Total@ GCD[#, Range[#]], # Total[#2/#1 & @@@ FactorInteger[#]]] &, 98] (* Michael De Vlieger, Oct 21 2021 *)

A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A018804(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ From A018804
A348492(n) = gcd(A003415(n), A018804(n));

a(n) = gcd(A003415(n), A018804(n)).
For n > 1, a(n) = A003415(n) / A348493(n).
a(n) = A003557(n) * A348494(n).

A348496 a(n) = gcd(A018804(n), A347130(n)) / A003557(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 4, 1, 3, 1, 2, 1, 21, 1, 36, 5, 1, 1, 1, 1, 15, 3, 4, 1, 1, 1, 1, 7, 1, 3, 1, 1, 3, 1, 1, 1, 1, 1, 12, 3, 5, 1, 10, 1, 3, 5, 4, 1, 9, 1, 1, 1, 1, 1, 12, 1, 3, 1, 1, 9, 1, 1, 12, 1, 1, 1, 1, 1, 3, 1, 4, 3, 1, 1, 2, 1, 1, 1, 4, 11, 15, 1, 35, 1, 3, 5, 36, 1, 1, 3, 1, 1, 3, 3, 1, 1

Offset: 1

Antti Karttunen, Oct 21 2021

nonn

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

Cf. A003557, A018804, A347128, A347129, A347130, A348495, A348501 [= a(A276086(n))].

Cf. also A348494, A348498.

Table[GCD[Total@ GCD[n, Range[n]], DivisorSum[n, #*(If[# < 2, 0, # Total[#2/#1 & @@@ FactorInteger[#]]] &[n/#]) &]]/Apply[Times, Map[#1^(#2 - 1) & @@ # &, FactorInteger[n]]], {n, 101}] (* Michael De Vlieger, Oct 21 2021 *)

\\ Needs also code from A348495:
A003557(n) = (n/factorback(factorint(n)[, 1]));
A348496(n) = (A348495(n)/A003557(n));

a(n) = A348495(n) / A003557(n).

a(n) = gcd(A347128(n), A347129(n)).

A370895 Partial alternating sums of Pillai's arithmetical function (A018804).

Original entry on oeis.org

1, -2, 3, -5, 4, -11, 2, -18, 3, -24, -3, -43, -18, -57, -12, -60, -27, -90, -53, -125, -60, -123, -78, -178, -113, -188, -107, -211, -154, -289, -228, -340, -235, -334, -217, -385, -312, -423, -298, -478, -397, -592, -507, -675, -486, -621, -528, -768, -635, -830

Offset: 1

Amiram Eldar, Mar 05 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
László Tóth, Alternating Sums Concerning Multiplicative Arithmetic Functions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.1.

Cf. A018804, A272718.
Cf. A001620, A306016.
Similar sequences: A068762, A068773, A307704, A357817, A362028.

f[p_, e_] := (e*(p - 1)/p + 1)*p^e; pil[n_] := Times @@ f @@@ FactorInteger[n]; Accumulate[Array[(-1)^(#+1) * pil[#] &, 100]]

pil(n) = {my(f=factor(n)); prod(i=1, #f~, (f[i, 2]*(f[i, 1]-1)/f[i, 1] + 1)*f[i, 1]^f[i, 2]);}
lista(kmax) = {my(s = 0); for(k = 1, kmax, s += (-1)^(k+1) * pil(k); print1(s, ", "))};

a(n) = Sum_{k=1..n} (-1)^(k+1) * A018804(k).

a(n) = -(1/Pi^2) * n^2 * (log(n) + 2*gamma - 1/2 - zeta'(2)/zeta(2) - 10*log(2)/3) + O(n^(547/416 + eps)), where gamma is Euler's constant (A001620) (Tóth, 2017).

A347128 a(n) = A018804(n) / A003557(n), where A018804 is Pillai's arithmetical function.

Original entry on oeis.org

1, 3, 5, 4, 9, 15, 13, 5, 7, 27, 21, 20, 25, 39, 45, 6, 33, 21, 37, 36, 65, 63, 45, 25, 13, 75, 9, 52, 57, 135, 61, 7, 105, 99, 117, 28, 73, 111, 125, 45, 81, 195, 85, 84, 63, 135, 93, 30, 19, 39, 165, 100, 105, 27, 189, 65, 185, 171, 117, 180, 121, 183, 91, 8, 225, 315, 133, 132, 225, 351, 141, 35, 145, 219, 65, 148

Offset: 1

Antti Karttunen, Aug 23 2021

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

Cf. A003557, A018804, A348494 [= gcd(a(n), A342001(n))], A348496 [= gcd(a(n), A347129(n))].

Cf. also A173557, A347127.

f[p_, e_] := (e*(p - 1)/p + 1)*p^e; A347128[n_] := (Times @@ (f @@@ FactorInteger[n]))/(n/Times @@ (First[Transpose[FactorInteger[n]]]));Table[A347128[n], {n, 1, 76}] (* Robert P. P. McKone, Aug 23 2021, after Amiram Eldar *)

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

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

a(n) = A018804(n) / A003557(n).

A348495 a(n) = gcd(A018804(n), A347130(n)), where A347130 is the Dirichlet convolution of the identity function with the arithmetic derivative of n (A003415), and A018804 is Pillai's arithmetical function.

Original entry on oeis.org

1, 1, 1, 2, 1, 5, 1, 4, 3, 1, 1, 8, 1, 3, 1, 16, 1, 63, 1, 72, 5, 1, 1, 4, 5, 15, 27, 8, 1, 1, 1, 16, 7, 1, 3, 6, 1, 3, 1, 4, 1, 1, 1, 24, 9, 5, 1, 80, 7, 15, 5, 8, 1, 81, 1, 4, 1, 1, 1, 24, 1, 3, 3, 32, 9, 1, 1, 24, 1, 1, 1, 12, 1, 3, 5, 8, 3, 1, 1, 16, 27, 1, 1, 8, 11, 15, 1, 140, 1, 9, 5, 72, 1, 1, 3, 16, 1

Offset: 1

Antti Karttunen, Oct 21 2021

nonn

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

Cf. A003415, A003557, A018804, A347130, A348496.

Cf. also A348492, A348497.

Table[GCD[Total@ GCD[n, Range[n]], DivisorSum[n, #*(If[# < 2, 0, # Total[#2/#1 & @@@ FactorInteger[#]]] &[n/#]) &]], {n, 97}] (* Michael De Vlieger, Oct 21 2021 *)

A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A018804(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ From A018804
A347130(n) = sumdiv(n,d,d*A003415(n/d));
A348495(n) = gcd(A018804(n), A347130(n));

a(n) = gcd(A018804(n), A347130(n)).

a(n) = A003557(n) * A348496(n).

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

Original entry on oeis.org

1, 4, 15, 16, 27, 48, 60, 64, 108, 144, 240, 256, 325, 432, 729, 891, 960, 1008, 1024, 1200, 1280, 1296, 1300, 1728, 1875, 2916, 3072, 3125, 3564, 3645, 3840, 3888, 4095, 4096, 5200, 6000, 6237, 6375, 6400, 6912, 7056, 7500, 8775, 9216, 11520, 11664, 12500

Offset: 1

Benoit Cloitre, Jan 25 2002

nonn

Also k such that Sum_{d|k} phi(d)/d is an integer. - Benoit Cloitre, Apr 14 2002
If two coprime numbers are terms then their product is as well, because Pillai's function A018804(n) is multiplicative. - Thomas Ordowski, Oct 28 2014
The first six squarefree terms are 1, 15=3*5, 1488251=19*29*37*73, 4464753=3*19*29*37*73, 7441255=5*19*29*37*73 and 22323765=3*5*19*29*37*73. Are there any others? - Michel Marcus and Thomas Ordowski, Nov 01 2014

Charles R Greathouse IV, Table of n, a(n) for n = 1..3287
László Tóth, A survey of gcd-sum functions, J. Int. Seq., Vol. 13 (2010), Article 10.8.1.

Cf. A018804.

A066862:=n->`if`(add(gcd(n,i), i=1..n) mod n = 0, n, NULL):
seq(A066862(n), n=1..500); # Wesley Ivan Hurt, Oct 28 2014

a066862[n_Integer] := Select[Range[n], Divisible[Sum[GCD[#, i], {i, 1, #}], #] &]; a066862[12500] (* Michael De Vlieger, Nov 23 2014 *)
f[p_, e_] := (e*(p - 1)/p + 1); r[n_] := Times @@ (f @@@ FactorInteger[n]); Select[Range[12500], IntegerQ[r[#]] &] (* Amiram Eldar, Apr 09 2022 *)

isok(n) = sum(i=1,n,gcd(n,i)) % n == 0; \\ Michel Marcus, Nov 20 2013

A018804(n)=my(f=factor(n)); prod(i=1, #f~, (f[i, 2]*(f[i, 1]-1)/f[i, 1] + 1)*f[i, 1]^f[i, 2])
is(n)=A018804(n)%n==0 \\ Charles R Greathouse IV, Oct 28 2014

If n = 4^k with k >= 0, n is in the sequence.

If p is prime and k >= 0 then n = p^(kp) is in the sequence. - Thomas Ordowski, Oct 28 2014

More terms from Michel Marcus, Nov 20 2013

cp's OEIS Frontend

A272718 Partial sums of gcd-sum sequence A018804.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A101035 Dirichlet inverse of the gcd-sum function (A018804).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

A080998 a(n) is n's rank among the positive integers in terms of centrality -the fraction of n represented by the average gcd of n and the positive integers, or A018804(n)/n^2 (cf. A080997).

Views

Author

Keywords

Examples

Crossrefs

A348494 a(n) = A348492(n) / A003557(n), where A348492 is the GCD of the arithmetic derivative (A003415) and Pillai's arithmetical function (A018804).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A348492 Greatest common divisor of the arithmetic derivative (A003415) and Pillai's arithmetical function (A018804).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A348496 a(n) = gcd(A018804(n), A347130(n)) / A003557(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A370895 Partial alternating sums of Pillai's arithmetical function (A018804).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A347128 a(n) = A018804(n) / A003557(n), where A018804 is Pillai's arithmetical function.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica