A344522 -id:A344522 - cp's OEIS frontend

A071778 Number of ordered triples (a, b, c) with gcd(a, b, c) = 1 and 1 <= {a, b, c} <= n.

1, 7, 25, 55, 115, 181, 307, 439, 637, 841, 1171, 1447, 1915, 2329, 2881, 3433, 4249, 4879, 5905, 6745, 7861, 8911, 10429, 11557, 13297, 14773, 16663, 18355, 20791, 22495, 25285, 27541, 30361, 32905, 36289, 38845, 42841, 46027, 49987, 53395

Offset: 1

Michael Malak (mmalak(AT)alum.mit.edu), Jun 04 2002

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
IBM Ponder This, Coin-weighing problem, Jun 01 2002
Eric Weisstein's World of Mathematics, Greatest Common Divisor

Cf. A018805 (ordered pairs), A082540, A082544, A343978, A344522.

public class Triples { public static void main(String[] argv) { int i, j, k, a, m, n, d; boolean cf; try {a = Integer.parseInt(argv[0]);} catch (Exception e) {a = 10;}
for (m = 1; m <= a; m++) { n = 0; for (i = 1; i <= m; i++) for (j = 1; j <= m; j++) for (k = 1; k <= m; k++) { cf = false; for (d = 2; d <= m; d++) cf = cf || ((i % d == 0) && (j % d == 0) && (k % d == 0)); if (!cf) n++; } System.out.println(m + ": " + n); } } }

f:=proc(n) local i,j,k,t1,t2,t3; t1:=0; for i from 1 to n do for j from 1 to n do t2:=gcd(i,j); for k from 1 to n do t3:=gcd(t2,k); if t3 = 1 then t1:=t1+1; fi; od: od: od: t1; end;

a[n_] := Sum[MoebiusMu[k]*Quotient[n, k]^3, {k, 1, n}]; Array[a, 40] (* Jean-François Alcover, Apr 14 2014, after Benoit Cloitre *)

PARI
```
a(n)=sum(k=1,n,moebius(k)*(n\k)^3)
```

a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)*(n\k[1])^3); s \\ Charles R Greathouse IV, Jan 08 2018

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k*(1+4*x^k+x^(2*k))/(1-x^k)^3)/(1-x)) \\ Seiichi Manyama, May 22 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A071778(n):
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A071778(k1)
        j, k1 = j2, n//j2
    return n*(n**2-1)-c+j # Chai Wah Wu, Mar 29 2021

a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^3. - Benoit Cloitre, May 11 2003
a(n) = n^3 - Sum_{j=2..n} a(floor(n/j)). - Vladeta Jovovic, Nov 30 2004
G.f.: (1/(1 - x)) * Sum_{k >= 1} mu(k) * x^k * (1 + 4*x^k + x^(2*k))/(1 - x^k)^3. - Seiichi Manyama, May 22 2021
a(n) ~ n^3/zeta(3). - Vaclav Kotesovec, Sep 14 2021

A344479 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{1 <= x_1, x_2, ..., x_k <= n} gcd(x_1, x_2, ..., x_k).

Original entry on oeis.org

1, 1, 3, 1, 5, 6, 1, 9, 12, 10, 1, 17, 30, 24, 15, 1, 33, 84, 76, 37, 21, 1, 65, 246, 276, 141, 61, 28, 1, 129, 732, 1060, 649, 267, 80, 36, 1, 257, 2190, 4164, 3165, 1417, 400, 112, 45, 1, 513, 6564, 16516, 15697, 8091, 2528, 624, 145, 55, 1, 1025, 19686, 65796, 78261, 47521, 17128, 4432, 885, 189, 66

Offset: 1

Seiichi Manyama, May 22 2021

			G.f. of column 3: (1/(1 - x)) * Sum_{i>=1} phi(i) * (x^i + 4*x^(2*i) + x^(3*i))/(1 - x^i)^3.
Square array begins:
   1,  1,   1,    1,    1,     1, ...
   3,  5,   9,   17,   33,    65, ...
   6, 12,  30,   84,  246,   732, ...
  10, 24,  76,  276, 1060,  4164, ...
  15, 37, 141,  649, 3165, 15697, ...
  21, 61, 267, 1417, 8091, 47521, ...

Seiichi Manyama, Antidiagonals n = 1..140, flattened

Columns k=1..5 give A000217, A018806, A344522, A344523, A344524.
T(n,n) gives A344525.
Cf. A343510, A343516, A344527.

T[n_, k_] := Sum[EulerPhi[j] * Quotient[n, j]^k, {j, 1, n}]; Table[T[k, n - k + 1], {n, 1, 11}, {k, 1, n}] // Flatten (* Amiram Eldar, May 22 2021 *)

T(n, k) = sum(j=1, n, eulerphi(j)*(n\j)^k);

G.f. of column k: (1/(1 - x)) * Sum_{i>=1} phi(i) * ( Sum_{j=1..k} A008292(k, j) * x^(i*j) )/(1 - x^i)^k.

T(n,k) = Sum_{j=1..n} phi(j) * floor(n/j)^k.

A344523 a(n) = Sum_{1 <= i, j, k, l <= n} gcd(i,j,k,l).

Original entry on oeis.org

1, 17, 84, 276, 649, 1417, 2528, 4432, 7033, 10905, 15556, 22836, 30673, 41729, 54944, 71968, 89969, 115457, 140820, 175444, 212537, 257113, 302720, 366160, 426505, 500873, 580676, 677108, 769761, 895377, 1008928, 1153120, 1300417, 1469073, 1640020, 1860340, 2054921

Offset: 1

Seiichi Manyama, May 22 2021

nonn

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

Column k=4 of A344479.

Cf. A082540, A343498, A344138, A344522, A344524, A344525.

a[n_] := Sum[EulerPhi[k] * Quotient[n, k]^4, {k, 1, n}]; Array[a, 50] (* Amiram Eldar, May 22 2021 *)

a(n) = sum(i=1, n, sum(j=1, n, sum(k=1, n, sum(l=1, n, gcd([i, j, k, l])))));

a(n) = sum(k=1, n, eulerphi(k)*(n\k)^4);

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k*(1+11*x^k+11*x^(2*k)+x^(3*k))/(1-x^k)^4)/(1-x))

a(n) = Sum_{k=1..n} phi(k) * floor(n/k)^4.
G.f.: (1/(1 - x)) * Sum_{k >= 1} phi(k) * x^k * (1 + 11*x^k + 11*x^(2*k) + x^(3*k))/(1 - x^k)^4.
a(n) ~ 90 * zeta(3) * n^4 / Pi^4. - Vaclav Kotesovec, May 23 2021

A344524 a(n) = Sum_{1 <= i, j, k, l, m <= n} gcd(i,j,k,l,m).

Original entry on oeis.org

1, 33, 246, 1060, 3165, 8091, 17128, 33936, 60645, 103825, 164886, 259368, 381841, 557595, 784200, 1091056, 1462353, 1968261, 2554810, 3327120, 4230561, 5361463, 6644196, 8302020, 10113445, 12352041, 14873418, 17924356, 21225165, 25341375, 29670556, 34920348, 40625541, 47297365

Offset: 1

Seiichi Manyama, May 22 2021

nonn

In general, for m > 2, Sum_{k=1..n} phi(k) * floor(n/k)^m ~ zeta(m-1) * n^m / zeta(m). - Vaclav Kotesovec, May 23 2021

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

Column k=5 of A344479.

Cf. A082544, A343499, A344139, A344522, A344523, A344525.

a[n_] := Sum[EulerPhi[k] * Quotient[n, k]^5, {k, 1, n}]; Array[a, 50] (* Amiram Eldar, May 22 2021 *)

a(n) = sum(i=1, n, sum(j=1, n, sum(k=1, n, sum(l=1, n, sum(m=1, n, gcd([i, j, k, l, m]))))));

a(n) = sum(k=1, n, eulerphi(k)*(n\k)^5);

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k*(1+26*x^k+66*x^(2*k)+26*x^(3*k)+x^(4*k))/(1-x^k)^5)/(1-x))

a(n) = Sum_{k=1..n} phi(k) * floor(n/k)^5.
G.f.: (1/(1 - x)) * Sum_{k >= 1} phi(k) * x^k * (1 + 26*x^k + 66*x^(2*k) + 26*x^(3*k) + x^(4*k))/(1 - x^k)^5.
a(n) ~ Pi^4 * n^5 / (90*zeta(5)). - Vaclav Kotesovec, May 23 2021

A344525 a(n) = Sum_{1 <= x_1, x_2, ... , x_n <= n} gcd(x_1,x_2, ... ,x_n).

Original entry on oeis.org

1, 5, 30, 276, 3165, 47521, 826000, 16843792, 387723045, 10009889889, 285360865350, 8918311872516, 302888304741841, 11112685595264369, 437898699063881208, 18447025862624951488, 827242515246907227633, 39346558373191515582161

Offset: 1

Seiichi Manyama, May 22 2021

nonn

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

Main diagonal of A344479.

Cf. A018806, A344140, A344522, A344523, A344524.

a[n_] := Sum[EulerPhi[k] * Quotient[n, k]^n, {k, 1, n}]; Array[a, 20] (* Amiram Eldar, May 22 2021 *)

a(n) = sum(k=1, n, eulerphi(k)*(n\k)^n);

from sympy import totient
def A344525(n): return sum(totient(k)*(n//k)**n for k in range(1,n+1)) # Chai Wah Wu, Aug 05 2024

a(n) = Sum_{k=1..n} phi(k) * floor(n/k)^n.

a(n) ~ n^n. - Vaclav Kotesovec, May 23 2021

A344521 a(n) = Sum_{1 <= i <= j <= k <= n} gcd(i,j,k).

Original entry on oeis.org

1, 5, 13, 28, 47, 82, 116, 172, 235, 321, 397, 538, 641, 798, 980, 1192, 1361, 1655, 1863, 2218, 2553, 2912, 3210, 3766, 4171, 4661, 5183, 5840, 6303, 7168, 7694, 8510, 9283, 10095, 10951, 12190, 12929, 13932, 14990, 16414, 17315, 18925, 19913, 21438, 23055, 24500, 25674, 27862

Offset: 1

Seiichi Manyama, May 22 2021

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000

Column k=3 of A345229.
Partial sums of A309322.
Cf. A272718, A344132, A344522, A344992.

a[n_] := Sum[Sum[Sum[GCD[i, j, k], {i, 1, j}], {j, 1, k}], {k, 1, n}]; Array[a, 50] (* Amiram Eldar, May 25 2021 *)
nmax = 100; Rest[CoefficientList[Series[1/(1 - x)*Sum[EulerPhi[k]*x^k/(1 - x^k)^3, {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Jun 05 2021 *)
Accumulate[Table[Sum[EulerPhi[n/d] * d*(d+1)/2, {d, Divisors[n]}], {n, 1, 100}]] (* Vaclav Kotesovec, Jun 05 2021 *)

a(n) = sum(i=1, n, sum(j=i, n, sum(k=j, n, gcd([i, j, k]))));

From Vaclav Kotesovec, Jun 05 2021: (Start)
a(n) ~ Pi^2 * n^3 / (36*zeta(3)).
G.f.: 1/(1-x) * Sum_{k>=1} phi(k) * x^k/(1 - x^k)^3, where phi is the Euler totient function (A000010).
a(n) = Sum_{k=1..n} Sum_{d|k} phi(k/d) * d*(d+1)/2. (End)
a(n) = Sum_{k=1..n} phi(k) * binomial(floor(n/k)+2,3). - Seiichi Manyama, Sep 13 2024

A344599 a(n) = Sum_{k=1..n} phi(k) * (floor(n/k)^3 - floor((n-1)/k)^3).

Original entry on oeis.org

1, 8, 21, 46, 65, 126, 133, 224, 261, 364, 341, 618, 481, 722, 837, 1000, 833, 1404, 1045, 1718, 1641, 1798, 1541, 2760, 2065, 2516, 2673, 3346, 2465, 4410, 2821, 4256, 4041, 4312, 4469, 6462, 4033, 5390, 5637, 7504, 4961, 8532, 5461, 8186, 8613, 7906, 6533, 11736, 7861, 10640, 9621

Offset: 1

Seiichi Manyama, May 24 2021

nonn

Cf. A344522, A344598, A344600.

a[n_] := Sum[EulerPhi[k] * First @ Differences @ (Quotient[{n - 1, n}, k]^3), {k, 1, n}]; Array[a, 40] (* Amiram Eldar, May 24 2021 *)

a(n) = sum(k=1, n, eulerphi(k)*((n\k)^3-((n-1)\k)^3));

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k*(1+4*x^k+x^(2*k))/(1-x^k)^3))

Sum_{k=1..n} a(k) = A344522(n).

G.f.: Sum_{k >= 1} phi(k) * x^k * (1 + 4*x^k + x^(2*k))/(1 - x^k)^3.

A344526 a(n) = Sum_{k=1..n} k^3 * phi(k).

Original entry on oeis.org

1, 9, 63, 191, 691, 1123, 3181, 5229, 9603, 13603, 26913, 33825, 60189, 76653, 103653, 136421, 215029, 250021, 373483, 437483, 548615, 655095, 922769, 1033361, 1345861, 1556773, 1911067, 2174491, 2857383, 3073383, 3967113, 4491401, 5210141, 5839005, 6868005, 7427877, 9251385

Offset: 1

Seiichi Manyama, May 22 2021

nonn

Cf. A000010, A011755, A068970, A319087, A344522.

a[n_] := Sum[k^3 * EulerPhi[k], {k, 1, n}]; Array[a, 40] (* Amiram Eldar, May 22 2021 *)
Accumulate[Table[k^3*EulerPhi[k], {k, 1, 40}]] (* Vaclav Kotesovec, May 22 2021 *)

PARI
```
a(n) = sum(k=1, n, k^3*eulerphi(k));
```

a(n) ~ 6*n^5 / (5*Pi^2). - Vaclav Kotesovec, May 22 2021

cp's OEIS Frontend

A071778 Number of ordered triples (a, b, c) with gcd(a, b, c) = 1 and 1 <= {a, b, c} <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Java

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A344479 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{1 <= x_1, x_2, ..., x_k <= n} gcd(x_1, x_2, ..., x_k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A344523 a(n) = Sum_{1 <= i, j, k, l <= n} gcd(i,j,k,l).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A344524 a(n) = Sum_{1 <= i, j, k, l, m <= n} gcd(i,j,k,l,m).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A344525 a(n) = Sum_{1 <= x_1, x_2, ... , x_n <= n} gcd(x_1,x_2, ... ,x_n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A344521 a(n) = Sum_{1 <= i <= j <= k <= n} gcd(i,j,k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A344599 a(n) = Sum_{k=1..n} phi(k) * (floor(n/k)^3 - floor((n-1)/k)^3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica