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

Author

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

Keywords

• nonn

Links

• 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

Crossrefs

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

Programs

Java

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

Maple

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;

Mathematica

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)

PARI

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

PARI

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

Python

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

Formula

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