A100448 Number of triples (i,j,k) with 1 <= i <= j < k <= n and gcd{i,j,k} = 1.

0, 1, 4, 9, 19, 30, 51, 73, 106, 140, 195, 241, 319, 388, 480, 572, 708, 813, 984, 1124, 1310, 1485, 1738, 1926, 2216, 2462, 2777, 3059, 3465, 3749, 4214, 4590, 5060, 5484, 6048, 6474, 7140, 7671, 8331, 8899, 9719, 10289, 11192, 11902, 12754, 13535, 14616

Offset

1,3

Comments

Probably the partial sums of A102309. - Ralf Stephan, Jan 03 2005

Links

R. J. Mathar, Table of n, a(n) for n = 1..10000

Formula

a(n) = (A071778(n)-1)/6. - Vladeta Jovovic, Nov 30 2004

a(n) = (1/6)*(-1 + Sum_{k=1..n} moebius(k)*floor(n/k)^3). - Ralf Stephan, Jan 03 2005

Maple

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

Mathematica

f[n_] := Length[ Union[ Flatten[ Table[ If[ GCD[i, j, k] == 1, {i, j, k}], {i, n}, {j, i, n}, {k, j + 1, n}], 2]]]; Table[ If[n > 3, f[n] - 1, f[n]], {n, 47}] (* Robert G. Wilson v, Dec 14 2004 *)

Prog

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

Crossrefs

Cf. A015616, A015631, A027430, A071778, A018805.

Sequence in context: A075649 A199972 A327753 * A059820 A180784 A015618

Adjacent sequences: A100445 A100446 A100447 * A100449 A100450 A100451

Keyword

nonn,easy

Author

N. J. A. Sloane, Nov 21 2004

Extensions

More terms from Robert G. Wilson v, Dec 14 2004

Edited by N. J. A. Sloane, Sep 06 2008 at the suggestion of R. J. Mathar

Status

approved