A057661 -id:A057661 - cp's OEIS frontend

A356472 Numerator of the average of gcd(i,n) for i = 1..n.

1, 3, 5, 2, 9, 5, 13, 5, 7, 27, 21, 10, 25, 39, 3, 3, 33, 7, 37, 18, 65, 63, 45, 25, 13, 75, 3, 26, 57, 9, 61, 7, 35, 99, 117, 14, 73, 111, 125, 9, 81, 65, 85, 42, 21, 135, 93, 5, 19, 39, 55, 50, 105, 9, 189, 65, 185, 171, 117, 6, 121, 183, 13, 4, 45, 105, 133, 66, 75, 351, 141, 35, 145, 219, 13, 74, 39, 125, 157

Offset: 1

Matthias Kaak, Aug 08 2022

			For n = 3, the average of the gcd's is (gcd(1,3) + gcd(2,3) + gcd(3,3))/3 = (1 + 1 + 3)/3 = 5/3 and its numerator is a(3)=5.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A356473 (denominators), A018804, A057661 (LCM).

Cf. A001620, A013661, A306016.

map numerator (map (\i -> sum (map (\j -> gcd i j) [1..i]) % i) [1..])

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

a(n) = numerator(sum(i=1, n, gcd(i, n))/n); \\ Michel Marcus, Aug 08 2022

a(n,f=factor(n))=my(k=prod(i=1, #f~, (f[i, 2]*(f[i, 1]-1)/f[i, 1] + 1)*f[i, 1]^f[i, 2])); k/gcd(k,n) \\ Charles R Greathouse IV, Sep 08 2022

from math import prod, gcd
from sympy import factorint
def A356472(n):
    f = factorint(n)
    return (m:=prod((p-1)*e+p for p, e in f.items()))//gcd(prod(f),m) # Chai Wah Wu, Sep 08 2022

a(n) = numerator(A018804(n)/n).
a(n) << n^(1+e) for any e > 0. a(n) > 1 for all n > 1. - Charles R Greathouse IV, Sep 08 2022
Sum_{k=1..n} a(k)/A356473(k) ~ (n/zeta(2)) * (log(n) + 2*gamma - 1 - zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). - Amiram Eldar, Dec 25 2024

A143613 Triangle read by rows: A051731 * A127368.

Original entry on oeis.org

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

Offset: 1

Gary W. Adamson, Aug 27 2008

A051731 = the inverse Moebius transform.
A127368 records the reduced residue system mod n, by rows.
Left border = d(n).
Row sums = A057661: (1, 2, 4, 6, 11, 11, 22, 22, 31, ...).

			First few rows of the triangle;
  1;
  2, 0;
  2, 2, 0;
  3, 0, 3, 0;
  2, 2, 3, 4, 0;
  4, 2, 0, 0, 5, 0;
  2, 2, 3, 4, 5, 6, 0;
  ...

Cf. A000005, A051731, A057661, A127368.

a(78) = 0 inserted by Georg Fischer, Jun 05 2023

A159936 Triangle read by rows, A051731 * A054533 * transpose(A101688), provided A101688 is read as a square array.

Original entry on oeis.org

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

Offset: 1

Gary W. Adamson, Apr 26 2009

Row sums = A057661: (1, 2, 4, 6, 11, 11, 22,...). Right border = A000010, phi(n).

			First few rows of the triangle are as follows:
  1;
  1, 1;
  1, 1, 2;
  1, 1, 2, 2;
  1, 1, 2, 3, 4;
  1, 1, 2, 2, 3, 2;
  1, 1, 2, 3, 4, 5, 6;
  1, 1, 2, 2, 4, 4, 4, 4;
  1, 1, 2, 3, 3, 3, 6, 6, 6;
  1, 1, 2, 2, 4, 4, 5, 4, 5, 4;
  1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;
  1, 1, 2, 2, 3, 2, 4, 4, 6, 6,  4,  4;
  1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12;
  1, 1, 2, 2, 4, 4, 6, 6, 7, 6,  7,  6,  7, 6;
  1, 1, 2, 3, 3, 3, 5, 4, 3, 5,  9,  8, 10, 9, 8;
  1, 1, 2, 2, 4, 4, 4, 4, 8, 8,  8,  8,  8, 8, 8, 8;
  ...

Cf. A000010, A051731, A054532, A054533, A054534, A054535, A057661, A101688.

Triangle read by rows, A051731 * A054533 * A000012. A051731 = the inverse Mobius transform. A054533 = the lower left half of the Ramanujan sum table. The operation (* transpose(A101688)) takes partial sums of (A051731 * A054533) starting from the right. [Edited by Petros Hadjicostas, Jul 30 2019]

Name edited by Petros Hadjicostas, Jul 30 2019

A308457 Expansion of e.g.f. (1/(1 - x)) * Product_{k>=2} 1/(1 - x^k)^(phi(k)/2), where phi() is the Euler totient function (A000010).

Original entry on oeis.org

1, 1, 3, 15, 93, 765, 6615, 73395, 855225, 11348505, 163593675, 2633729175, 44537325525, 829112008725, 16299062754975, 340762189642875, 7597436750528625, 178862527106888625, 4426363064514265875, 115222810432347993375, 3139125774622690978125

Offset: 0

Ilya Gutkovskiy, May 27 2019

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..435

Cf. A000010, A023022, A023896, A051193, A057661, A061255.

nmax = 20; CoefficientList[Series[1/(1 - x) Product[1/(1 - x^k)^(EulerPhi[k]/2), {k, 2, nmax}], {x, 0, nmax}], x] Range[0, nmax]!
nmax = 20; CoefficientList[Series[Exp[Sum[Sum[LCM[k, j], {j, 1, k}] x^k/k^2, {k, 1, nmax}]], {x, 0, nmax}], x] Range[0, nmax]!
a[n_] := a[n] = Sum[Total[Numerator[Range[k]/k]] k! Binomial[n - 1, k - 1] a[n - k]/k, {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 20}]

E.g.f.: exp(Sum_{k>=1} A057661(k)*x^k/k).
E.g.f.: exp(Sum_{k>=1} A051193(k)*x^k/k^2).
E.g.f.: d/dx ( exp(arctanh(x)) ) * Product_{k>=3} 1/(1 - x^k)^A023022(k).
a(n) ~ A * exp(3^(4/3) * Zeta(3)^(1/3) * n^(2/3) / (2*Pi)^(2/3) - n - 1/12) * n^(n + 1/36) / (2^(1/9) * 3^(19/36) * (Pi*Zeta(3))^(1/36)), where A is the Glaisher-Kinkelin constant A074962. - Vaclav Kotesovec, May 28 2019
E.g.f.: Product_{k>=1} 1/(1 - x^k)^(A023896(k)/k). - Ilya Gutkovskiy, May 28 2019

A331388 a(n) = Sum_{k=1..n} mu(gcd(n, k)) * k / gcd(n, k).

Original entry on oeis.org

1, 0, 2, 3, 9, 3, 20, 12, 24, 10, 54, 15, 77, 21, 48, 48, 135, 24, 170, 57, 103, 55, 252, 60, 240, 78, 216, 123, 405, 47, 464, 192, 273, 136, 390, 144, 665, 171, 388, 228, 819, 102, 902, 327, 456, 253, 1080, 240, 1008, 240, 678, 465, 1377, 216, 1036, 492, 853, 406, 1710

Offset: 1

Ilya Gutkovskiy, Feb 18 2020

nonn

Moebius transform of A023896.

Cf. A007427, A007431, A008683, A023896, A057661, A063445.

[&+[MoebiusMu(Gcd(n,k))*(k div Gcd(n,k)):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Feb 18 2020

Table[Sum[MoebiusMu[GCD[n, k]] k/GCD[n, k], {k, 1, n}], {n, 1, 65}]
A023896[n_] := Sum[If[GCD[n, k] == 1, k, 0], {k, 1, n}]; Table[Sum[MoebiusMu[n/d] A023896[d], {d, Divisors[n]}], {n, 1, 65}]

a(n) = (1/n) * Sum_{k=1..n} mu(gcd(n, k)) * lcm(n, k).
a(n) = Sum_{d|n} mu(n/d) * A023896(d).
a(n) = Sum_{d|n} A007427(n/d) * A057661(d).
Sum_{k=1..n} a(k) ~ n^3 / (Pi^2 * Zeta(3)). - Vaclav Kotesovec, Feb 19 2020

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

Original entry on oeis.org

0, 2, 12, 28, 100, 90, 392, 408, 792, 810, 2420, 1356, 4732, 3346, 4560, 6320, 13872, 7506, 21660, 12140, 18900, 21802, 46552, 22008, 53000, 43290, 61668, 49980, 117740, 48450, 153760, 100192, 123552, 129506, 169260, 111420, 312132, 203642, 245544, 195640

Offset: 1

Sebastian Karlsson, Jan 18 2021

nonn

Sebastian Karlsson, Table of n, a(n) for n = 1..10000
Index entries for sequences related to lcm's

Cf. A000010, A006580, A023900, A051193, A057661, A138421.

a[n_] := Sum[LCM[LCM[n, k], LCM[n, n - k]], {k, 1, n - 1}];
Table[a[n], {n, 1, 40}] (* Robert P. P. McKone, Jan 18 2021 *)

a(n) = sum(k=1, n-1, lcm(lcm(n, k), lcm(n, n-k))); \\ Michel Marcus, Jan 18 2021

from math import gcd
for n in range(1, 41):
    print(n*sum([k*(n-k)//(gcd(n,k)**2) for k in range(1, n)]), end=', ')

a(n) = n*Sum_{k=1..n-1} k*(n-k)/gcd(n,k)^2.
a(n) = (1/6)*n*Sum_{d|n} d*(d*phi(d) - A023900(d)).
a(p^e) = (1/6)*p^(e+1)*(p^e-1)*(p^(e+1) + p^(2*e+1) + p^2 + 2*p + 1)/(p^2 + p + 1).
a(prime(n)) = A138421(n). - Michel Marcus, Jan 20 2021

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

Original entry on oeis.org

1, 3, 8, 16, 35, 45, 98, 116, 183, 215, 396, 316, 663, 609, 750, 912, 1513, 1107, 2128, 1560, 2135, 2453, 3818, 2428, 4325, 4095, 4914, 4452, 7743, 4425, 9486, 7280, 8613, 9299, 10640, 8088, 16243, 13053, 14378, 12100, 22181, 12663, 25628, 17996, 19305, 23345, 33558, 19200, 34251, 26075

Offset: 1

Seiichi Manyama, May 21 2021

nonn

Cf. A057661, A344508.

a[n_] := Sum[k * LCM[k, n], {k, 1, n}]/n; Array[a, 50] (* Amiram Eldar, May 21 2021 *)

PARI
```
a(n) = sum(k=1, n, k*lcm(k, n))/n;
```

a(n) = A344508(n)/n.

Sum_{k=1..n} a(k) ~ zeta(3) * n^4 / (2*Pi^2). - Vaclav Kotesovec, May 29 2021

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

Original entry on oeis.org

0, 0, 1, 1, 6, 2, 15, 5, 15, 8, 45, 7, 66, 18, 30, 21, 120, 18, 153, 23, 70, 50, 231, 24, 190, 72, 147, 56, 378, 40, 435, 85, 194, 128, 280, 55, 630, 162, 284, 87, 780, 68, 861, 153, 264, 242, 1035, 91, 861, 200, 502, 213, 1326, 156, 788, 205, 642, 392, 1653, 110, 1770, 450, 606, 341, 1136

Offset: 1

Ilya Gutkovskiy, Sep 26 2021

nonn

Cf. A057661, A062355, A348061.

Table[Sum[If[GCD[n, k] == 1, (k - 1)/GCD[n, k - 1], 0], {k, n}], {n, 65}]

a(n) = sum(k=1, n, if (gcd(n, k)==1, (k-1)/gcd(n, k-1))); \\ Michel Marcus, Sep 27 2021

A365076 Number of length-n binary words x such that the infinite word xxxx... is balanced.

Original entry on oeis.org

2, 4, 8, 12, 22, 22, 44, 44, 62, 64, 112, 78, 158, 130, 148, 172, 274, 184, 344, 232, 302, 334, 508, 302, 522, 472, 548, 474, 814, 442, 932, 684, 778, 820, 904, 672, 1334, 1030, 1100, 904, 1642, 904, 1808, 1222, 1282, 1522, 2164, 1198, 2102, 1564, 1912, 1728

Offset: 1

Jeffrey Shallit, Aug 20 2023

nonn

A binary word w is "balanced" if for all lengths and all blocks b of the same length appearing in it, the number of 1's in b can take only two different values. For example, 00111 is not balanced because 00 has no 1's, 01 has one, and 11 has two.

			For n = 4, the 12 such words are 0000, 0001, 0010, 0100, 0101, 0111 and their bitwise binary complements.

Laurent Vuillon, Balanced words, Bull. Belg. Math. Soc. Simon Stevin 10(5): 787-805 (December 2003).

Cf. A057660, A057661.

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

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

a(n) = 2*A057661(n).

a(n) = A057660(n) + 1.

A292303 a(1) = 1; a(n+1) = Sum_{k=1..n} lcm(a(k),n)/n.

Original entry on oeis.org

1, 1, 2, 4, 4, 12, 9, 33, 50, 78, 99, 173, 264, 658, 570, 1056, 1099, 4113, 2443, 10129, 18866, 23226, 39775, 102665, 171529, 256039, 610467, 815809, 1795028, 3854202, 3044396, 10752800, 5509162, 22665306, 25847226, 66558954, 25219183, 167266731, 264535960, 163511658, 346473322, 1109093102

Offset: 1

Ilya Gutkovskiy, Sep 14 2017

nonn

			a(1) = 1;
a(2) = lcm(a(1),1)/1 = lcm(1,1)/1 = 1;
a(3) = lcm(a(1),2)/2 + lcm(a(2),2)/2 = lcm(1,2)/2 + lcm(1,2)/2 = 2;
a(4) = lcm(a(1),3)/3 + lcm(a(2),3)/3 + lcm(a(3),3)/3 = lcm(1,3)/3 + lcm(1,3)/3 + lcm(2,3)/3 = 4, etc.

Index entries for sequences related to lcm's

Cf. A056147, A057661, A286946, A287006.

a[1] = 1; a[n_] := a[n] = Sum[LCM[a[k - 1], n - 1]/(n - 1), {k, 2, n}]; Table[a[n], {n, 42}]
a[1] = 1; a[n_] := a[n] = Sum[a[k - 1]/GCD[a[k - 1], n - 1], {k, 2, n}]; Table[a[n], {n, 42}]

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

cp's OEIS Frontend

A356472 Numerator of the average of gcd(i,n) for i = 1..n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

A143613 Triangle read by rows: A051731 * A127368.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A159936 Triangle read by rows, A051731 * A054533 * transpose(A101688), provided A101688 is read as a square array.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A308457 Expansion of e.g.f. (1/(1 - x)) * Product_{k>=2} 1/(1 - x^k)^(phi(k)/2), where phi() is the Euler totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A331388 a(n) = Sum_{k=1..n} mu(gcd(n, k)) * k / gcd(n, k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

A365076 Number of length-n binary words x such that the infinite word xxxx... is balanced.