A018804 -id:A018804 - cp's OEIS frontend

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

1, 3, 7, 11, 21, 21, 43, 43, 61, 63, 111, 77, 157, 129, 147, 171, 273, 183, 343, 231, 301, 333, 507, 301, 521, 471, 547, 473, 813, 441, 931, 683, 777, 819, 903, 671, 1333, 1029, 1099, 903, 1641, 903, 1807, 1221, 1281, 1521, 2163, 1197, 2101, 1563, 1911, 1727

Offset: 1

Henry Gould, Oct 15 2000

Also sum of the orders of the elements in a cyclic group with n elements, i.e., row sums of A054531. - Avi Peretz (njk(AT)netvision.net.il), Mar 31 2001
Also inverse Moebius transform of EulerPhi(n^2), A002618.
Sequence is multiplicative with a(p^e) = (p^(2*e+1)+1)/(p+1). Example: a(10) = a(2)*a(5) = 3*21 = 63.
a(n) is the number of pairs (a, b) such that the equation ax = b is solvable in the ring (Zn, +, x). See the Mathematical Reflections link. - Michel Marcus, Jan 07 2017
From Jake Duzyk, Jun 06 2023: (Start)
These are the "contraharmonic means" of the improper divisors of square integers (inclusive of 1 and the square integer itself).
Permitting "Contraharmonic Divisor Numbers" to be defined analogously to Øystein Ore's Harmonic Divisor Numbers, the only numbers for which there exists an integer contraharmonic mean of the divisors are the square numbers, and a(n) is the n-th integer contraharmonic mean, expressible also as the sum of squares of divisors of n^2 divided by the sum of divisors of n^2. That is, a(n) = sigma_2(n^2)/sigma(n^2).
(a(n) = A001157(k)/A000203(k) where k is the n-th number such that A001157(k)/A000203(k) is an integer, i.e., k = n^2.)
This sequence is an analog of A001600 (Harmonic means of divisors of harmonic numbers) and A102187 (Arithmetic means of divisors of arithmetic numbers). (End)

David M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston MA, 1976, p. 152.
H. W. Gould and Temba Shonhiwa, Functions of GCD's and LCM's, Indian J. Math. (Allahabad), Vol. 39, No. 1 (1997), pp. 11-35.
H. W. Gould and Temba Shonhiwa, A generalization of Cesaro's function and other results, Indian J. Math. (Allahabad), Vol. 39, No. 2 (1997), pp. 183-194.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Habib Amiri and S. M. Jafarian Amiri, Sum of element orders on finite groups of the same order, J. Algebra Appl. 10 (2011), no. 2, 187--190. MR2795731 (2012d:20050)
Habib Amiri, S. M. Jafarian Amiri, and I. M. Isaacs, Sums of element orders in finite groups Comm. Algebra 37 (2009), no. 9, 2978--2980. MR2554185 (2010i:20022)
Miriam Mahannah El-Farrah, Expectation Numbers of Cyclic Groups, MS Thesis, Western Kentucky University, August 2015.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 154-5.
Walther Janous, Problem 10829, Amer. Math. Monthly, 107 (2000), p. 753.
Yadollah Marefat, Ali Iranmanesh, and Abolfazl Tehranian, On the sum of element orders of finite simple groups, J. Algebra Applications, 12 (2013), #1350026.
Mathematical Reflections, Solution to Problem U338, Issue 4, 2015, p 17.
Joachim von zur Gathen, Arnold Knopfmacher, Florian Luca, Lutz G. Lucht, and Igor E. Shparlinski, Average order of cyclic groups, J. Théorie Nombres Bordeaux 16 (1) (2004) 107-123.

Cf. A000010, A000203, A000290, A001157, A018804, A050873, A051193, A054522, A057661, A061255, A065764, A078747, A174405 (partial sums), A176797, A226512.

Cf. A308471.

a057660 n = sum $ map (div n) $ a050873_row n
-- Reinhard Zumkeller, Nov 25 2013

Table[ DivisorSigma[ 2, n^2 ] / DivisorSigma[ 1, n^2 ], {n, 1, 128} ]
Table[Total[Denominator[Range[n]/n]], {n, 55}] (* Alonso del Arte, Oct 07 2011 *)
f[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Nov 21 2020 *)

a(n)=if(n<1,0,sumdiv(n,d,d*eulerphi(d)))

a(n)=sumdivmult(n,d, eulerphi(d)*d) \\ Charles R Greathouse IV, Sep 09 2014

from math import gcd
def A057660(n): return sum(n//gcd(n,k) for k in range(1,n+1)) # Chai Wah Wu, Aug 24 2023

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

a(n) = Sum_{d|n} d*A000010(d) = Sum_{d|n} d*A054522(n,d), sum of d times phi(d) for all divisors d of n, where phi is Euler's phi function.
a(n) = sigma_2(n^2)/sigma_1(n^2) = A001157(A000290(n))/A000203(A000290(n)) = A001157(A000290(n))/A065764(n). - Labos Elemer, Nov 21 2001
a(n) = Sum_{d|n} A000010(d^2). - Enrique Pérez Herrero, Jul 12 2010
a(n) <= (n-1)*n + 1, with equality if and only if n is noncomposite. - Daniel Forgues, Apr 30 2013
G.f.: Sum_{n >= 1} n*phi(n)*x^n/(1 - x^n) = x + 3*x^2 + 7*x^3 + 11*x^4 + .... Dirichlet g.f.: sum {n >= 1} a(n)/n^s = zeta(s)*zeta(s-2)/zeta(s-1) for Re s > 3.  Cf. A078747 and A176797. - Peter Bala, Dec 30 2013
a(n) = Sum_{i=1..n} numerator(n/i). - Wesley Ivan Hurt, Feb 26 2017
L.g.f.: -log(Product_{k>=1} (1 - x^k)^phi(k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 21 2018
From Richard L. Ollerton, May 10 2021: (Start)
a(n) = Sum_{k=1..n} lcm(n,k)/k.
a(n) = Sum_{k=1..n} gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
From Vaclav Kotesovec, Jun 13 2021: (Start)
Sum_{k=1..n} a(k)/k ~ 3*zeta(3)*n^2/Pi^2.
Sum_{k=1..n} k^2/a(k) ~ A345294 * n.
Sum_{k=1..n} k*A000010(k)/a(k) ~ A345295 * n. (End)
Sum_{k=1..n} a(k) ~ 2*zeta(3)*n^3/Pi^2. - Vaclav Kotesovec, Jun 10 2023

More terms from James Sellers, Oct 16 2000

A050873 Triangular array T read by rows: T(n,k) = gcd(n,k).

Original entry on oeis.org

1, 1, 2, 1, 1, 3, 1, 2, 1, 4, 1, 1, 1, 1, 5, 1, 2, 3, 2, 1, 6, 1, 1, 1, 1, 1, 1, 7, 1, 2, 1, 4, 1, 2, 1, 8, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Clark Kimberling

The function T(n,k) = T(k,n) is defined for all integer k,n but only the values for 1 <= k <= n as a triangular array are listed here.
For each divisor d of n, the number of d's in row n is phi(n/d). Furthermore, if {a_1, a_2, ..., a_phi(n/d)} is the set of positive integers <= n/d that are relatively prime to n/d then T(n,a_i * d) = d. - Geoffrey Critzer, Feb 22 2015
Starting with any row n and working downwards, consider the infinite rectangular array with k = 1..n. A repeating pattern occurs every A003418(n) rows. For example, n=3: A003418(3) = 6. The 6-row pattern starting with row 3 is {1,1,3}, {1,2,1}, {1,1,1}, {1,2,3}, {1,1,1}, {1,2,1}, and this pattern repeats every 6 rows, i.e., starting with rows {9,15,21,27,...}. - Bob Selcoe and Jamie Morken, Aug 02 2017

			Rows:
  1;
  1, 2;
  1, 1, 3;
  1, 2, 1, 4;
  1, 1, 1, 1, 5;
  1, 2, 3, 2, 1, 6; ...

T. D. Noe, Rows n=1..100, flattened
Marcelo Polezzi, A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor, The American Mathematical Monthly, Vol. 104, No. 5 (May, 1997), pp. 445-446.
Eric Weisstein's World of Mathematics, Greatest Common Divisor
Wikipedia, Greatest Common Divisor

Cf. A003989.
Cf. A002262, A054531, A226314.
Cf. A018804 (row sums), A245717.
Cf. A132442 (sums of divisors).
Cf. A003418.

a050873 = gcd
a050873_row n = a050873_tabl !! (n-1)
a050873_tabl = zipWith (map . gcd ) [1..] a002260_tabl
-- Reinhard Zumkeller, Dec 12 2015, Aug 13 2013, Jun 10 2013

ColumnForm[Table[GCD[n, k], {k, 12}, {n, k}], Center] (* Alonso del Arte, Jan 14 2011 *)

{T(n, k) = gcd(n, k)} /* Michael Somos, Jul 18 2011 */

a(n) = gcd(A002260(n), A002024(n)); A054521(n) = A000007(a(n)). - Reinhard Zumkeller, Dec 02 2009
T(n,k) = A075362(n,k)/A051173(n,k), 1 <= k <= n. - Reinhard Zumkeller, Apr 25 2011
T(n, k) = T(k, n) = T(-n, k) = T(n, -k) = T(n, n+k) = T(n+k, k). - Michael Somos, Jul 18 2011
T(n,k) = A051173(n,k) / A051537(n,k). - Reinhard Zumkeller, Jul 07 2013

A054523 Triangle read by rows: T(n,k) = phi(n/k) if k divides n, T(n,k)=0 otherwise (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 2, 1, 0, 1, 4, 0, 0, 0, 1, 2, 2, 1, 0, 0, 1, 6, 0, 0, 0, 0, 0, 1, 4, 2, 0, 1, 0, 0, 0, 1, 6, 0, 2, 0, 0, 0, 0, 0, 1, 4, 4, 0, 0, 1, 0, 0, 0, 0, 1, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 2, 2, 2, 0, 1, 0, 0, 0, 0, 0, 1, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 6

Offset: 1

N. J. A. Sloane, Apr 09 2000

From Gary W. Adamson, Jan 08 2007: (Start)
Let H be this lower triangular matrix. Then:
H * A051731 = A126988,
H * [1, 2, 3, ...] = 1, 3, 5, 8, 9, 15, ... = A018804,
H * sigma(n) = A038040 = d(n) * n = 1, 4, 6, 12, 10, ... where sigma(n) = A000203,
H * d(n) (A000005) = sigma(n) = A000203,
Row sums are A000027 (corrected by Werner Schulte, Sep 06 2020, see comment of Gary W. Adamson, Aug 03 2008),
H^2 * d(n) = d(n)*n, H^2 = A127192,
H * mu(n) (A008683) = A007431(n) (corrected by Werner Schulte, Sep 06 2020),
H^2 row sums = A018804. (End)
The Möbius inversion principle of Richard Dedekind and Joseph Liouville (1857), cf. "Concrete Mathematics", p. 136, is equivalent to the statement that row sums are the row index n. - Gary W. Adamson, Aug 03 2008
The multivariable row polynomials give n times the cycle index for the cyclic group C_n, called Z(C_n) (see the MathWorld link with the Harary reference): n*Z(C_n) = Sum_{k=1..n} T(n,k)*(y_{n/k})^k, n >= 1. E.g., 6*Z(C_6) = 2*(y_6)^1 + 2*(y_3)^2 + 1*(y_2)^3 + 1*(y_1)^6. - Wolfdieter Lang, May 22 2012
See A102190 (no 0's, rows reversed). - Wolfdieter Lang, May 29 2012
This is the number of permutations in the n-th cyclic group which are the product of k disjoint cycles. - Robert A. Beeler, Aug 09 2013

			Triangle begins
   1;
   1, 1;
   2, 0, 1;
   2, 1, 0, 1;
   4, 0, 0, 0, 1;
   2, 2, 1, 0, 0, 1;
   6, 0, 0, 0, 0, 0, 1;
   4, 2, 0, 1, 0, 0, 0, 1;
   6, 0, 2, 0, 0, 0, 0, 0, 1;
   4, 4, 0, 0, 1, 0, 0, 0, 0, 1;
  10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
   4, 2, 2, 2, 0, 1, 0, 0, 0, 0, 0, 1;

Ronald L. Graham, D. E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, p. 136.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
Eric Weisstein's World of Mathematics, Cycle Index.

Cf. A000005, A000007, A000010, A000012, A000203, A007431, A008683.
Cf. A038040, A051731, A054521, A054525, A102190, A126988.
Sums incliude: A029935, A069097, A092843 (diagonal), A209295.
Sums of the form Sum_{k} k^p * T(n, k): A000027 (p=0), A018804 (p=1), A069097 (p=2), A343497 (p=3), A343498 (p=4), A343499 (p=5).

a054523 n k = a054523_tabl !! (n-1) !! (k-1)
a054523_row n = a054523_tabl !! (n-1)
a054523_tabl = map (map (\x -> if x == 0 then 0 else a000010 x)) a126988_tabl
-- Reinhard Zumkeller, Jan 20 2014

A054523:= func< n,k | k eq n select 1 else (n mod k) eq 0 select EulerPhi(Floor(n/k)) else 0 >;
[A054523(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, Jun 24 2024

A054523 := proc(n,k) if n mod k = 0 then numtheory[phi](n/k) ; else 0; end if; end proc: # R. J. Mathar, Apr 11 2011

T[n_, k_]:= If[k==n,1,If[Divisible[n, k], EulerPhi[n/k], 0]];
Table[T[n,k], {n,15}, {k,n}]//Flatten (* G. C. Greubel, Dec 15 2017 *)

for(n=1, 10, for(k=1, n, print1(if(!(n % k), eulerphi(n/k), 0), ", "))) \\ G. C. Greubel, Dec 15 2017

def A054523(n,k):
    if (k==n): return 1
    elif (n%k)==0: return euler_phi(int(n//k))
    else: return 0
flatten([[A054523(n,k) for k in range(1,n+1)] for n in range(1,16)]) # G. C. Greubel, Jun 24 2024

Sum_{k=1..n} k * T(n, k) = A018804(n). - Gary W. Adamson, Jan 08 2007
Equals A054525 * A126988 as infinite lower triangular matrices. - Gary W. Adamson, Aug 03 2008
From Werner Schulte, Sep 06 2020: (Start)
Sum_{k=1..n} T(n,k) * A000010(k) = A029935(n) for n > 0.
Sum_{k=1..n} k^2 * T(n,k) = A069097(n) for n > 0. (End)
From G. C. Greubel, Jun 24 2024: (Start)
T(2*n-1, n) = A000007(n-1), n >= 1.
T(2*n, n) = A000012(n), n >= 1.
Sum_{k=1..n} (-1)^(k-1)*T(n, k) = (1 - (-1)^n)*n/2.
Sum_{k=1..floor(n+1)/2} T(n-k+1, k) = A092843(n+1).
Sum_{k=1..n} (k+1)*T(n, k) = A209295(n).
Sum_{k=1..n} k^3 * T(n, k) = A343497(n).
Sum_{k=1..n} k^4 * T(n, k) = A343498(n).
Sum_{k=1..n} k^5 * T(n, k) = A343499(n). (End)

A029935 a(n) = Sum_{d divides n} phi(d)*phi(n/d).

Original entry on oeis.org

1, 2, 4, 5, 8, 8, 12, 12, 16, 16, 20, 20, 24, 24, 32, 28, 32, 32, 36, 40, 48, 40, 44, 48, 56, 48, 60, 60, 56, 64, 60, 64, 80, 64, 96, 80, 72, 72, 96, 96, 80, 96, 84, 100, 128, 88, 92, 112, 120, 112, 128, 120, 104, 120

Offset: 1

N. J. A. Sloane

Dirichlet convolution of A000010 with itself. - R. J. Mathar, Aug 28 2015

Gheorghe Coserea, Table of n, a(n) for n = 1..20000

Cf. A000005, A000010, A001620, A005117, A018804, A029936, A143258.

Row sums of A159937.

with(numtheory): A029935 := proc(n) local i,j; j := 0; for i in divisors(n) do j := j+phi(i)*phi(n/i); od; j; end;

A029935[n_]:=DivisorSum[n,EulerPhi[#]*EulerPhi[n/#]&]; Array[A029935, 50]
f[p_, e_] := (e+1)*(p^e - p^(e-1)) - (e-1)*(p^(e-1) - p^(e-2)); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 26 2023 *)

a(n) = {
  my(f = factor(n), fsz = matsize(f)[1],
     g = prod(k=1, fsz, f[k,1]),
     h = prod(k=1, fsz, sqr(f[k,1]-1)*f[k,2] + sqr(f[k,1])-1));
  return(h*n\sqr(g));
};
vector(54, n, a(n))  \\ Gheorghe Coserea, Oct 23 2016

a(n) = sumdiv(n, d, eulerphi(d)*eulerphi(n/d)); \\ Michel Marcus, Oct 23 2016

From Vladeta Jovovic, Oct 30 2001: (Start)
Sum_{k=1..n} phi(gcd(n, k)).
Multiplicative with a(p^e) = (e+1)*(p^e - p^(e - 1)) - (e - 1)*(p^(e - 1) - p^(e - 2)). (End)
From Franklin T. Adams-Watters, Nov 19 2004: (Start)
Sum_{d|n} a(d) = A018804(n), Mobius transform of A018804.
Dirichlet g.f.: zeta(s-1)^2/zeta(s)^2. (End)
Equals row sums of triangle A143258. - Gary W. Adamson, Aug 02 2008
a(n) <= A000010(n) * A000005(n), with equality iff n = A005117(k) for some k. - Gheorghe Coserea, Oct 23 2016
Sum_{k=1..n} a(k) ~ 9*n^2 * ((2*log(n) + 4*gamma - 1)/Pi^4 - 24*Zeta'(2)/Pi^6), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Jan 31 2019

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

Original entry on oeis.org

1, 2, 4, 6, 11, 11, 22, 22, 31, 32, 56, 39, 79, 65, 74, 86, 137, 92, 172, 116, 151, 167, 254, 151, 261, 236, 274, 237, 407, 221, 466, 342, 389, 410, 452, 336, 667, 515, 550, 452, 821, 452, 904, 611, 641, 761, 1082, 599, 1051, 782, 956, 864, 1379, 821, 1166

Offset: 1

Henry Gould, Oct 15 2000

Sum of numerators of n-th order Farey series (cf. A006842). - Benoit Cloitre, Oct 28 2002
Equals row sums of triangle A143613. - Gary W. Adamson, Aug 27 2008
Equals row sums of triangle A159936. - Gary W. Adamson, Apr 26 2009
Also row sums of triangle A164306. - Reinhard Zumkeller, Aug 12 2009

H. W. Gould and Temba Shonhiwa, Functions of GCD's and LCM's, Indian J. Math. (Allahabad), 39 (1997), 11-35.
H. W. Gould and Temba Shonhiwa, A generalization of Cesaro's function and other results, Indian J. Math. (Allahabad), 39 (1997), 183-194.

T. D. Noe, Table of n, a(n) for n = 1..1000
Zachary Franco, Problem 12114, The American Mathematical Monthly, Vol. 126, No. 5 (2019), p. 469; A Dirichlet Series with Reduced Numerators, Solution to Problem 12114 by Tamas Wiandt, ibid., Vol. 128, No. 1 (2021), pp. 91-92.
Index entries for sequences related to lcm's.

Cf. A000010, A000217, A006842, A018804, A023896, A051193, A057660, A143613, A159936, A164306.

See A341316 for another version.

a057661 n = a051193 n `div` n  -- Reinhard Zumkeller, Jun 10 2015

[&+[&+[h: h in [1..d] | GCD(h,d) eq 1]: d in Divisors(n)]: n in [1..100]]; // Jaroslav Krizek, Dec 28 2016

Table[Total[Numerator[Range[n]/n]], {n, 55}] (* Alonso del Arte, Oct 07 2011 *)
f[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); a[n_] := (1 + Times @@ f @@@ FactorInteger[n])/2; Array[a, 100] (* Amiram Eldar, Apr 26 2023 *)

a(n)=sum(k=1,n,lcm(n,k))/n \\ Charles R Greathouse IV, Feb 07 2017

from math import lcm
def A057661(n): return sum(lcm(n,k)//n for k in range(1,n+1)) # Chai Wah Wu, Aug 24 2023

from math import prod
from sympy import factorint
def A057661(n): return 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) = (1+A057660(n))/2.
a(n) = A051193(n)/n.
a(n) = Sum_{d|n} psi(d), where psi(m) = is the sum of totatives of m (A023896). - Jaroslav Krizek, Dec 28 2016
a(n) = Sum_{i=1..n} denominator(n/i). - Wesley Ivan Hurt, Feb 26 2017
G.f.: x/(2*(1 - x)) + (1/2)*Sum_{k>=1} k*phi(k)*x^k/(1 - x^k), where phi() is the Euler totient function (A000010). - Ilya Gutkovskiy, Aug 31 2017
If p is prime, then a(p) = T(p-1) + 1 = p(p-1)/2 + 1, where T(n) = n(n+1)/2 is the n-th triangular number (A000217). - David Terr, Feb 10 2019
Sum_{k=1..n} a(k) ~ zeta(3) * n^3 / Pi^2. - Vaclav Kotesovec, May 29 2021
Dirichlet g.f.: zeta(s)*(1 + zeta(s-2)/zeta(s-1))/2 (Franco, 2019). - Amiram Eldar, Mar 26 2022

More terms from James Sellers, Oct 16 2000

A069097 Moebius transform of A064987, n*sigma(n).

Original entry on oeis.org

1, 5, 11, 22, 29, 55, 55, 92, 105, 145, 131, 242, 181, 275, 319, 376, 305, 525, 379, 638, 605, 655, 551, 1012, 745, 905, 963, 1210, 869, 1595, 991, 1520, 1441, 1525, 1595, 2310, 1405, 1895, 1991, 2668, 1721, 3025, 1891, 2882, 3045, 2755, 2255, 4136, 2737

Offset: 1

Benoit Cloitre, Apr 05 2002

Equals A127569 * [1, 2, 3, ...]. - Gary W. Adamson, Jan 19 2007
Equals row sums of triangle A143309 and of triangle A143312. - Gary W. Adamson, Aug 06 2008
Dirichlet convolution of A000290 and A000010 (see Jovovic formula). - R. J. Mathar, Feb 03 2011

Amiram Eldar, Table of n, a(n) for n = 1..10000
Wenchang Chu, Jordan's totient function and trigonometric sums, Studia Scientiarum Mathematicarum Hungarica 57 (1), 40-53 (2020).
Nikolai Osipov, Problem 12003, Amer. Math. Monthly, 124(8) (2017), p. 754.

Column 2 of A343510.
Cf. A018804, A033457, A068963, A064987, A127569, A143309, A143312, A360428.
For Sum_{k = 1..n} gcd(k,n)^m see A018804 (m = 1), A343497 (m = 3), A343498 (m = 4) and A343499 (m = 5).

A069097[n_]:=n^2*Plus @@((EulerPhi[#]/#^2)&/@ Divisors[n]); Array[A069097, 100] (* Enrique Pérez Herrero, Feb 25 2012 *)
f[p_, e_] := p^(e-1)*(p^e*(p+1)-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 18 2020 *)

for(n=1,100,print1((sumdiv(n,k,k*sigma(k)*moebius(n/k))),","))

a(n) = Sum_{d|n} d^2*phi(n/d). - Vladeta Jovovic, Jul 31 2002
a(n) = Sum_{k=1..n} gcd(n, k)^2. - Vladeta Jovovic, Aug 27 2003
Dirichlet g.f.: zeta(s-2)*zeta(s-1)/zeta(s). - R. J. Mathar, Feb 03 2011
a(n) = n*Sum_{d|n} J_2(d)/d, where J_2 is A007434. - Enrique Pérez Herrero, Feb 25 2012.
G.f.: Sum_{n >= 1} phi(n)*(x^n + x^(2*n))/(1 - x^n)^3 = x + 5*x^2 + 11*x^3 + 22*x^4  + .... - Peter Bala, Dec 30 2013
Multiplicative with a(p^e) = p^(e-1)*(p^e*(p+1)-1). - R. J. Mathar, Jun 23 2018
Sum_{k=1..n} a(k) ~ Pi^2 * n^3 / (18*zeta(3)). - Vaclav Kotesovec, Sep 18 2020
a(n) = Sum_{k=1..n} (n/gcd(n,k))^2*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021
From Peter Bala, Dec 26 2023: (Start)
For n odd, a(n) = Sum_{k = 1..n} gcd(k,n)/cos(k*Pi/n)^2 (see Osipov and also Chu, p. 51).
It appears that for n odd, Sum_{k = 1..n} (-1)^(k+1)*gcd(k,n)/cos(k*Pi/n)^2 = n. (End)
a(n) = Sum_{1 <= i, j <= n} gcd(i, j, n). Cf. A360428. - Peter Bala, Jan 16 2024
Sum_{k=1..n} a(k)/k ~ Pi^2 * n^2 / (12*zeta(3)). - Vaclav Kotesovec, May 11 2024

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

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 8, 2, 2, 4, 2, 2, 4, 8, 2, 8, 2, 4, 4, 2, 2, 4, 8, 2, 16, 4, 2, 4, 2, 8, 4, 2, 4, 16, 2, 2, 4, 4, 2, 4, 2, 4, 16, 2, 2, 16, 8, 8, 4, 4, 2, 16, 4, 4, 4, 2, 2, 8, 2, 2, 16, 16, 4, 4, 2, 4, 4, 4, 2, 16, 2, 2, 16, 4, 4, 4, 2, 16, 128, 2, 2

Offset: 1

Gus Wiseman, Feb 03 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 from Andrew Howroyd)

Cf. A000010, A003958, A005187, A006519, A007431, A011371, A018804, A023900, A029935, A037445, A046643, A046644, A165825, A257098, A298971, A299119, A299149 (numerators), A299151, A317848, A317929, A317932, A318314, A318512, A318653, A318681.

Cf. A318440 (the 2-adic valuation).

nn=50;
sys=Table[n==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Denominator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]
f[p_, e_] := 2^((1 + Mod[p, 2])*e - DigitCount[e, 2, 1]); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *)

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

A299150(n) = { my(f = factor(n), m=1); for(i=1, #f~, m *= 2^(((1+(f[i,1]%2))*f[i,2]) - hammingweight(f[i,2]))); (m); }; \\ Antti Karttunen, Sep 03 2018

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

a(n) = denominator(n*A317848(n)/A165825(n)) = A165825(n)/(A037445(n) * A006519(n)). - Andrew Howroyd, Aug 09 2018
a(n) = A046644(n)/A006519(n). - Andrew Howroyd and Antti Karttunen, Aug 30 2018
From Antti Karttunen, Sep 03 2018: (Start)
a(n) = 2^A318440(n).
Multiplicative with a(2^e) = 2^A011371(e), a(p^e) = 2^A005187(e) for odd primes p.
Multiplicative with a(p^e) = 2^(((1+A000035(p))*e)-A000120(e)) for all primes p.
(End)

Keyword:mult added by Andrew Howroyd, Aug 09 2018

A318557 Number A(n,k) of n-member subsets of [k*n] whose elements sum to a multiple of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 5, 10, 1, 0, 1, 1, 6, 30, 38, 1, 0, 1, 1, 9, 55, 165, 126, 1, 0, 1, 1, 10, 91, 460, 1001, 452, 1, 0, 1, 1, 13, 138, 969, 3876, 6198, 1716, 1, 0, 1, 1, 14, 190, 1782, 10630, 33594, 38760, 6470, 1, 0, 1, 1, 17, 253, 2925, 23751, 118755, 296010, 245157, 24310, 1, 0

Offset: 0

Alois P. Heinz, Aug 28 2018

The sequence of row n satisfies a linear recurrence with constant coefficients of order A018804(n) for n>0.

			A(3,2) = 10: {1,2,3}, {1,2,5}, {1,3,4}, {1,3,6}, {1,4,5}, {1,5,6}, {2,3,5}, {2,4,6}, {3,4,5}, {3,5,6}.
A(2,3) = 5: {1,2}, {1,5}, {2,4}, {3,6}, {4,5}.
Square array A(n,k) begins:
  1, 1,    1,     1,      1,       1,       1,        1, ...
  0, 1,    1,     1,      1,       1,       1,        1, ...
  0, 1,    2,     5,      6,       9,      10,       13, ...
  0, 1,   10,    30,     55,      91,     138,      190, ...
  0, 1,   38,   165,    460,     969,    1782,     2925, ...
  0, 1,  126,  1001,   3876,   10630,   23751,    46376, ...
  0, 1,  452,  6198,  33594,  118755,  324516,   749398, ...
  0, 1, 1716, 38760, 296010, 1344904, 4496388, 12271518, ...

Alois P. Heinz, Antidiagonals n = 0..85, flattened

Columns k=0-10 give: A000007, A000012, A119358, A318591, A318592, A318593, A318594, A318595, A318596, A318597, A318598.
Rows n=0-10 give: A000012, A057427, A042963 (for k>0), A318624, A318625, A318626, A318627, A318628, A318629, A318630, A318631.
Main diagonal gives A318477.
Cf. A018804, A304482.

nmax = 11; (* Program not suitable to compute a large number of terms. *)
A[n_, k_] := A[n, k] = Count[Subsets[Range[k n], {n}], s_ /; Divisible[Total[s], k]]; A[0, _] = 1;
Table[A[n - k, k], {n, 0, nmax}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Oct 04 2019 *)

A143127 a(n) = Sum_{k=1..n} k*d(k) where d(k) is the number of divisors of k.

Original entry on oeis.org

1, 5, 11, 23, 33, 57, 71, 103, 130, 170, 192, 264, 290, 346, 406, 486, 520, 628, 666, 786, 870, 958, 1004, 1196, 1271, 1375, 1483, 1651, 1709, 1949, 2011, 2203, 2335, 2471, 2611, 2935, 3009, 3161, 3317, 3637, 3719, 4055, 4141, 4405, 4675, 4859, 4953, 5433

Offset: 1

Gary W. Adamson, Jul 26 2008

a(n) is also the sum of all parts of all partitions of all positive integers <= n into equal parts. - Omar E. Pol, May 29 2017

a(n) is also the sum of the multiples of k, not exceeding n, for k = 1, 2, ..., n. See a formula and an example below. - Wolfdieter Lang, Oct 18 2021

			a(3) = 11 = (1 + 4 + 6), where n*d(n) = (1, 4, 6, 12, 10, 24, ...).
a(4) = 23 = (8 + 7 + 5 + 3), where (8, 7, 5, 3) = row 4 of triangle A110661.
a(4) = 23 is the sum of [1 2 3 4|2 4|3|4] (multiples of k=1..4, not exceeding n). - _Wolfdieter Lang_, Oct 18 2021
a(4) = [1] + [2 + 1 + 1] + [3 + 1 + 1 + 1] + [4 + 2 + 2 + 1 + 1 + 1 + 1] = 23. - _Omar E. Pol_, Oct 18 2021

Enrique Pérez Herrero, Table of n, a(n) for n = 1..1000
Jacob F. F. Bulmer, Javier Martínez-Cifuentes, Bryn A. Bell, and Nicolás Quesada, Simulating lossy and partially distinguishable quantum optical circuits: theory, algorithms and applications to experiment validation and state preparation, arXiv:2412.17742 [quant-ph], 2024. See p. 29.
Vaclav Kotesovec, Graph - The asymptotic ratio (1000000 terms)

Partial sums of A038040.
Cf. A000005, A083356.
Row sums of triangle A110661.
Row sums of triangle A143310. - Gary W. Adamson, Aug 06 2008
Cf. A018804.

a143127 n = a143127_list !! (n-1)
a143127_list = scanl1 (+) a038040_list
-- Reinhard Zumkeller, Jan 21 2014

Accumulate[DivisorSigma[0, Range[48]] Range[48]] (* Giovanni Resta, May 29 2018 *)

a(n) = sum(k=1, n, k*numdiv(k)); \\ Michel Marcus, May 29 2018

from math import isqrt
def A143127(n): return -((k:=isqrt(n))*(k+1)>>1)**2+sum(i*(m:=n//i)*(1+m) for i in range(1,k+1)) # Chai Wah Wu, Jul 11 2023

a(n) = Sum_{k=1..n} A038040(k).
a(n) = Sum_{m=1..floor(sqrt(n))} m*(m+floor(n/m))*(floor(n/m)+1-m) - A000330(floor(sqrt(n))) = 2*A083356(n) - A000330(floor(sqrt(n))). - Max Alekseyev, Jan 31 2012
G.f.: x*f'(x)/(1 - x), where f(x) = Sum_{k>=1} x^k/(1 - x^k). - Ilya Gutkovskiy, Apr 13 2017 [Sum_{k>=1} k*x^k/((1-x)*(1-x^k)^2), see A038040. - Wolfdieter Lang, Oct 18 2021]
a(n) = Sum_{k=1..n} k/2 * floor(n/k) * floor(1 + n/k). - Daniel Suteu, May 28 2018
a(n) ~ log(n) * n^2 / 2 + (gamma - 1/4)*n^2, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Sep 08 2018
From Daniel Hoying, May 21 2020: (Start)
a(n) = (Sum_{i=1..floor(sqrt(n))} i*floor(n/i)*(1+floor(n/i))) - (floor(sqrt(n))*(1+floor(sqrt(n)))/2)^2;
     = (Sum_{i=1..floor(sqrt(n))} i*floor(n/i)*(1+floor(n/i))) - A000537(floor(sqrt(n))).
a(n) = A000537(floor(sqrt(n))) ; n=1;
     = A000537(floor(sqrt(n))) + n*(n+1) - floor(n/2)*(floor(n/2)+1) ; 1     = A000537(floor(sqrt(n))) + n*(n+1) - floor(n/2)*(floor(n/2)+1) + Sum_{i=floor(sqrt(n))+1..floor(n/2)} i*floor(n/i)*(1+floor(n/i)) ; n>=6. (End)
a(n) = Sum_{i=1..n} A018804(i)*floor(n/i). - Ridouane Oudra, Mar 15 2021
a(n) = Sum_{k=1..n} b(n,k), with b(n, k) = Sum_{j=1..floor(n/k)} j*k = k * floor(n/k) * (floor(n/k) + 1)/2. See the formula by Daniel Suteu above. - Wolfdieter Lang, Oct 18 2021

More terms from Carl Najafi, Dec 24 2011

Edited by Max Alekseyev, Jan 31 2012

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

Original entry on oeis.org

1, 5, 29, 274, 3129, 47515, 823549, 16843268, 387459861, 10009769725, 285311670621, 8918311856102, 302875106592265, 11112685048729175, 437893951473411261, 18447025557276459016, 827240261886336764193, 39346558373052524325225, 1978419655660313589123997

Offset: 1

Ilya Gutkovskiy, Feb 14 2020

nonn

If n is prime, a(n) = n-1 + n^n. - Robert Israel, Feb 16 2020

Robert Israel, Table of n, a(n) for n = 1..386

Cf. A000010, A008683, A018804, A031971, A069097, A226561, A228640, A321294.

[&+[Gcd(n,k)^n:k in [1..n]]: n in [1..20]]; // Marius A. Burtea, Feb 15 2020

f:= n -> add(igcd(n,k)^n,k=1..n):
map(f, [$1..30]); # Robert Israel, Feb 16 2020

Table[Sum[GCD[n, k]^n, {k, 1, n}], {n, 1, 19}]
Table[Sum[EulerPhi[n/d] d^n, {d, Divisors[n]}], {n, 1, 19}]
Table[Sum[MoebiusMu[n/d] d DivisorSigma[n - 1, d], {d, Divisors[n]}], {n, 1, 19}]

a(n) = sum(k=1, n, gcd(n, k)^n); \\ Michel Marcus, Feb 14 2020

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

a(n) = Sum_{d|n} phi(n/d) * d^n.
a(n) = Sum_{d|n} mu(n/d) * d * sigma_(n-1)(d).
a(n) ~ n^n.
From Richard L. Ollerton, May 09 2021: (Start)
a(n) = Sum_{k=1..n} (n/gcd(n,k))^n*phi(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))*gcd(n,k)*sigma_(n-1)(gcd(n,k))/phi(n/gcd(n,k)). (End)

Previous Showing 41-50 of 165 results. Next

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A050873 Triangular array T read by rows: T(n,k) = gcd(n,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A054523 Triangle read by rows: T(n,k) = phi(n/k) if k divides n, T(n,k)=0 otherwise (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A029935 a(n) = Sum_{d divides n} phi(d)*phi(n/d).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Python

Python

Formula

Extensions

A069097 Moebius transform of A064987, n*sigma(n).

Views