A082544 -id:A082544 - 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

A082540 Number of ordered quadruples (a,b,c,d) with gcd(a,b,c,d)=1 (1 <= {a,b,c,d} <= n).

Original entry on oeis.org

1, 15, 79, 239, 607, 1199, 2303, 3823, 6223, 9279, 13919, 19183, 27007, 35743, 47519, 60735, 78719, 97103, 122447, 148527, 181839, 216959, 262543, 306863, 365343, 423855, 495855, 569055, 661679, 748527, 862047, 972191, 1104831, 1237247

Offset: 1

Benoit Cloitre, May 11 2003

nonn

Karl-Heinz Hofmann, Table of n, a(n) for n = 1..10000

Column k=4 of A344527.
Cf. A018805, A071778, A082544, A343978.
Cf. A015634.

a(n)=sum(k=1,n,moebius(k)*floor(n/k)^4)

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

a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^4.
a(n) is asymptotic to c*n^4 with c=0.92393....
Lim_{n->infinity} a(n)/n^4 = 1/zeta(4) = A215267 = 90/Pi^4. - Karl-Heinz Hofmann, Apr 11 2021
Lim_{n->infinity} n^4/a(n) =   zeta(4) = A013662 = Pi^4/90. - Karl-Heinz Hofmann, Apr 11 2021
a(n) = n^4 - Sum_{k=2..n} a(floor(n/k)). - Seiichi Manyama, Sep 13 2024

A343978 Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= n).

Original entry on oeis.org

1, 63, 727, 4031, 15559, 45863, 116855, 257983, 526615, 983583, 1755143, 2935231, 4776055, 7407727, 11256623, 16498719, 23859071, 33434063, 46467719, 62949975, 84644439, 111486599, 146142583, 187854119, 240880239, 303814503, 382049919, 473813703, 586746719

Offset: 1

Karl-Heinz Hofmann, May 06 2021

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.

Karl-Heinz Hofmann, Table of n, a(n) for n = 1..10000
Joachim von zur Gathen and Jürgen Gerhard, Extract from "3.4. (Non-)Uniqueness of the gcd" chapter, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.

Column k=6 of A344527.
Cf. A343359, A013664, A018805, A071778, A082540, A082544.
Cf. A342632, A342586, A342935, A342841, A343527, A343193.

a(n)={sum(k=1, n+1, moebius(k)*(n\k)^6)} \\ Andrew Howroyd, May 08 2021

from labmath import mobius
def A343978(n): return sum(mobius(k)*(n//k)**6 for k in range(1, n+1))

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

a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^6.
Lim_{n->infinity} a(n)/n^6 = 1/zeta(6) = A343359 = 945/Pi^6.
a(n) = n^6 - Sum_{k=2..n} a(floor(n/k)). - Seiichi Manyama, Sep 13 2024

Edited by N. J. A. Sloane, Jun 13 2021

A344527 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of ordered k-tuples (x_1, x_2, ..., x_k) with gcd(x_1, x_2, ..., x_k) = 1 (1 <= {x_1, x_2, ..., x_k} <= n).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 25, 11, 1, 1, 31, 79, 55, 19, 1, 1, 63, 241, 239, 115, 23, 1, 1, 127, 727, 991, 607, 181, 35, 1, 1, 255, 2185, 4031, 3091, 1199, 307, 43, 1, 1, 511, 6559, 16255, 15559, 7501, 2303, 439, 55, 1, 1, 1023, 19681, 65279, 77995, 45863, 16531, 3823, 637, 63, 1

Offset: 1

Seiichi Manyama, May 22 2021

			G.f. of column 3: (1/(1 - x)) * Sum_{i>=1} mu(i) * (x^i + 4*x^(2*i) + x^(3*i))/(1 - x^i)^3.
Square array begins:
  1,  1,   1,    1,    1,     1, ...
  1,  3,   7,   15,   31,    63, ...
  1,  7,  25,   79,  241,   727, ...
  1, 11,  55,  239,  991,  4031, ...
  1, 19, 115,  607, 3091, 15559, ...
  1, 23, 181, 1199, 7501, 45863, ...

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

Columns k=1..6 give A000012, A018805, A071778, A082540, A082544, A343978.
T(n,n) gives A332468.
Cf. A343510, A343516, A344479.

T[n_, k_] := Sum[MoebiusMu[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, moebius(j)*(n\j)^k);

PARI
```
T(n, k) = n^k-sum(j=2, n, T(n\j, k));
```

from functools import lru_cache
from itertools import count, islice
@lru_cache(maxsize=None)
def A344527_T(n,k):
    if n == 0:
        return 0
    c, j, k1 = 1, 2, n//2
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A344527_T(k1,k)
        j, k1 = j2, n//j2
    return n*(n**(k-1)-1)-c+j
def A344527_gen(): # generator of terms
    return (A344527_T(k+1, n-k) for n in count(1) for k in range(n))
A344527_list = list(islice(A344527_gen(),30)) # Chai Wah Wu, Nov 02 2023

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

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

A343282 Number of ordered 5-tuples (v,w, x, y, z) with gcd(v, w, x, y, z) = 1 and 1 <= {v, w, x, y, z} <= 10^n.

Original entry on oeis.org

1, 96601, 9645718621, 964407482028001, 96438925911789115351, 9643875373658964992585011, 964387358678775616636890654841, 96438734235127451288511508421855851, 9643873406165059293451290072800801506621

Offset: 0

Karl-Heinz Hofmann, Apr 10 2021

nonn

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.

Chai Wah Wu, Table of n, a(n) for n = 0..15

Cf. A082544, A013663, A342586, A342841, A343193.
Related counts of k-tuples:
pairs: A018805, A342632, A342586;
triples: A071778, A342935, A342841;
quadruples: A082540, A343527, A343193;
5-tuples: A343282;
6-tuples: A343978, A344038. - N. J. A. Sloane, Jun 13 2021

from labmath import mobius
def A343282(n): return sum(mobius(k)*(10**n//k)**5 for k in range(1, 10**n+1))

Lim_{n->infinity} a(n)/10^(5*n) = 1/zeta(5) = A343308.

a(n) = A082544(10^n). - Chai Wah Wu, Apr 11 2021

Edited by N. J. A. Sloane, Jun 13 2021

A344038 Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= 10^n).

Original entry on oeis.org

1, 983583, 983029267047, 982960635742968103, 982953384128772770413831, 982952672223441253533233827367, 982952600027678075050509511271466303, 982952593055042000417993486008754893529583, 982952592342881094406730790044111038427637071855

Offset: 0

Karl-Heinz Hofmann, May 07 2021

Chai Wah Wu, Table of n, a(n) for n = 0..15

Cf. A342586, A342841, A343193, A343282, A343359, A013664.
Cf. A343978, A071778, A018805, A082540, A082544.
Related counts of k-tuples:
pairs: A018805, A342632, A342586;
triples: A071778, A342935, A342841;
quadruples: A082540, A343527, A343193;
5-tuples: A343282;
6-tuples: A343978, A344038. - N. J. A. Sloane, Jun 13 2021

a(n)={sum(k=1, 10^n+1, moebius(k)*(10^n\k)^6)} \\ Andrew Howroyd, May 08 2021

from labmath import mobius
def A344038(n): return sum(mobius(k)*(10**n//k)**6 for k in range(1, 10**n+1))

Lim_{n->infinity} a(n)/10^(6*n) = 1/zeta(6) = A343359 = 945/Pi^4.

a(n) = A343978(10^n).

Edited by N. J. A. Sloane, Jun 13 2021

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

Original entry on oeis.org

1, 3, 25, 239, 3091, 45863, 821227, 16711423, 387138661, 9990174303, 285262663291, 8913906888703, 302861978789371, 11111328334033327, 437889112287422401, 18446462446101903615, 827238009323454485641, 39346257879101283645743, 1978418304199236175597105

Offset: 1

Ilya Gutkovskiy, Feb 13 2020

nonn

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

Main diagonal of A344527.

Cf. A008683, A018805, A071778, A082540, A082544, A332469, A343978.

[&+[MoebiusMu(k)*Floor(n/k)^n:k in [1..n]]:n in [1..20]]; // Marius A. Burtea, Feb 13 2020

Table[Sum[MoebiusMu[k] Floor[n/k]^n, {k, 1, n}], {n, 1, 19}]
b[n_, k_] := b[n, k] = n^k - Sum[b[Floor[n/j], k], {j, 2, n}]; a[n_] := b[n, n]; Table[a[n], {n, 1, 19}]

a(n)={sum(k=1, n, moebius(k) * floor(n/k)^n)} \\ Andrew Howroyd, Feb 13 2020

from functools import lru_cache
@lru_cache(maxsize=None)
def A344527_T(n,k):
    if n == 0:
        return 0
    c, j, k1 = 1, 2, n//2
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A344527_T(k1,k)
        j, k1 = j2, n//j2
    return n*(n**(k-1)-1)-c+j
def A332468(n): return A344527_T(n,n) # Chai Wah Wu, Nov 02 2023

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

A101467 Number of distinct n-term ratios x_1 : x_2 : ... : x_n where each x_i is in the range [1-10].

Original entry on oeis.org

10, 63, 841, 9279, 96601, 983583, 9919561, 99602559, 998026681, 9990174303, 99950992681, 999755323839, 9998777694361, 99993891685023, 999969468040201, 9999847368997119, 99999236931275641, 999996184915051743, 9999980925350886121, 99999904629080526399

Offset: 1

Su Jianning (sujianning(AT)yahoo.com.cn), Jan 21 2005

Number of elements of {1,...,10}^n with gcd 1. - Robert Israel, Nov 28 2014

			For n=2: Consider the ratios 1:1, 1:2, ..., 1:10, 2:1, 2:2, ..., 2:10, ..., 10:1, 10:2, ..., 10:10. We get 63 different ratios from the 100 numbers list above after removing duplication. So a(2) = 63, and this is A018805(10).

Colin Barker, Table of n, a(n) for n = 1..999
Index entries for linear recurrences with constant coefficients, signature (21,-151,471,-640,300).

Cf. A018805 (2 terms), A071778 (3 terms), A082540 (4 terms), A082544 (5 terms).

1, seq(10^n - 5^n - 3^n - 2^n + 1, n=2..20); # Robert Israel, Nov 28 2014

Vec(x*(2700*x^5-5460*x^4+3579*x^3-1028*x^2+147*x-10)/((x-1)*(2*x-1)*(3*x-1)*(5*x-1)*(10*x-1)) + O(x^100)) \\ Colin Barker, Nov 28 2014

a(1) = 10; for n>1, a(n) = 10^n - 5^n - 3^n - 2^n + 1.
G.f.: x*(2700*x^5-5460*x^4+3579*x^3-1028*x^2+147*x-10) / ((x-1)*(2*x-1)*(3*x-1)*(5*x-1)*(10*x-1)). - Colin Barker, Nov 28 2014
a(n+4) = -300*a(n)+340*a(n+1)-131*a(n+2)+20*a(n+3)+72 for n >= 2. - Robert Israel, Dec 02 2014
a(n) = 21*a(n-1) - 151*a(n-2) + 471*a(n-3) - 640*a(n-4) + 300*a(n-5) for n > 6. - Chai Wah Wu, Apr 15 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

A082540 Number of ordered quadruples (a,b,c,d) with gcd(a,b,c,d)=1 (1 <= {a,b,c,d} <= n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula

A343978 Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= n).

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Python

Python

Formula

Extensions

A344527 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of ordered k-tuples (x_1, x_2, ..., x_k) with gcd(x_1, x_2, ..., x_k) = 1 (1 <= {x_1, x_2, ..., x_k} <= n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

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

A343282 Number of ordered 5-tuples (v,w, x, y, z) with gcd(v, w, x, y, z) = 1 and 1 <= {v, w, x, y, z} <= 10^n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Formula

Extensions

A344038 Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= 10^n).

Views

Author

Keywords