A018804 -id:A018804

A101035

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

+20
12

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

G. P. Michon, Multiplicative Functions.

FORMULA

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

EXAMPLE

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

MATHEMATICA

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 *)

PROG

(Haskell)

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

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

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

CROSSREFS

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

Cf. A008683.

KEYWORD

easy,nice,sign,mult

AUTHOR

Gerard P. Michon, Nov 27 2004

STATUS

approved

A272718

Partial sums of gcd-sum sequence A018804.

+20
10

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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.

FORMULA

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)

EXAMPLE

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

MATHEMATICA

b[n_] := GCD[n, #]& /@ Range[n] // Total;

Array[b, 100] // Accumulate (* Jean-François Alcover, Jun 05 2021 *)

PROG

(PARI) 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

CROSSREFS

Partial sums of A018804.

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

KEYWORD

nonn,easy

AUTHOR

Gareth McCaughan, May 05 2016

STATUS

approved

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

+20
7

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..58.

EXAMPLE

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

CROSSREFS

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.

KEYWORD

nonn

AUTHOR

Matthew Vandermast, Mar 02 2003

STATUS

approved

A348494

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

+20
7

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

LINKS

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

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

FORMULA

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

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

MATHEMATICA

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 *)

PROG

(PARI)

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));

CROSSREFS

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

Cf. also A348496.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 21 2021

STATUS

approved

A348492

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

+20
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

LINKS

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

FORMULA

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

For n > 1, a(n) = A003415(n) / A348493(n).

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

MATHEMATICA

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

PROG

(PARI)

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));

CROSSREFS

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

Cf. also A342413, A342458, A348495.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 21 2021

STATUS

approved

A348496

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

+20
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

LINKS

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

FORMULA

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

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

MATHEMATICA

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 *)

PROG

(PARI)

\\ Needs also code from A348495:

A003557(n) = (n/factorback(factorint(n)[, 1]));

A348496(n) = (A348495(n)/A003557(n));

CROSSREFS

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

Cf. also A348494, A348498.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 21 2021

STATUS

approved

A347128

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

+20
5

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

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

FORMULA

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

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

MATHEMATICA

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 *)

PROG

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

CROSSREFS

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

Cf. also A173557, A347127.

KEYWORD

nonn,mult,look

AUTHOR

Antti Karttunen, Aug 23 2021

STATUS

approved

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.

+20
5

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

LINKS

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

FORMULA

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

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

MATHEMATICA

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 *)

PROG

(PARI)

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));

CROSSREFS

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

Cf. also A348492, A348497.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 21 2021

STATUS

approved

A066862

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

+20
4

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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.

FORMULA

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

MAPLE

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

MATHEMATICA

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 *)

PROG

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

(PARI) 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

CROSSREFS

Cf. A018804.

KEYWORD

nonn

AUTHOR

Benoit Cloitre, Jan 25 2002

EXTENSIONS

More terms from Michel Marcus, Nov 20 2013

STATUS

approved

A318443

Numerators of the sequence whose Dirichlet convolution with itself yields A018804, Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

+20
3

1, 3, 5, 23, 9, 15, 13, 91, 59, 27, 21, 115, 25, 39, 45, 1451, 33, 177, 37, 207, 65, 63, 45, 455, 179, 75, 353, 299, 57, 135, 61, 5797, 105, 99, 117, 1357, 73, 111, 125, 819, 81, 195, 85, 483, 531, 135, 93, 7255, 363, 537, 165, 575, 105, 1059, 189, 1183, 185, 171, 117, 1035, 121, 183, 767, 46355, 225, 315, 133, 759, 225, 351, 141, 5369

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Because A018804 gets only odd values on primes, A046644 gives the sequence of denominators. Because both of those sequences are multiplicative, this is also.

LINKS

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

FORMULA

a(n) = numerator of f(n), where f(1) = 1, f(n) = (1/2) * (A018804(n) - Sum_{d|n, d>1, d<n} f(d) * f(n/d)) for n > 1.

MATHEMATICA

a18804[n_] := Sum[n EulerPhi[d]/d, {d, Divisors[n]}];

f[1] = 1; f[n_] := f[n] = 1/2 (a18804[n] - Sum[f[d] f[n/d], {d, Divisors[ n][[2 ;; -2]]}]);

a[n_] := f[n] // Numerator;

Array[a, 72] (* Jean-François Alcover, Sep 13 2018 *)

PROG

(PARI)

up_to = 16384;

A018804(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ From A018804

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&&d<n, u[d]*u[n/d], 0)))/2); u}; \\ From A317937.

v318443aux = DirSqrt(vector(up_to, n, A018804(n)));

A318443(n) = numerator(v318443aux[n]);

CROSSREFS

Cf. A018804, A046644 (denominators).

Cf. also A318444.

KEYWORD

nonn,frac,mult

AUTHOR

Antti Karttunen and Andrew Howroyd, Aug 29 2018

STATUS

approved