login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A071778 Number of ordered triples (a, b, c) with gcd(a, b, c) = 1 and 1 <= {a, b, c} <= n. 21
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
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
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
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 *)
PROG
(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); } } }
(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
CROSSREFS
Cf. A018805 (ordered pairs), A082540, A082544, A343978, A344522.
Sequence in context: A155286 A155313 A213390 * A350156 A155250 A155260
KEYWORD
nonn
AUTHOR
Michael Malak (mmalak(AT)alum.mit.edu), Jun 04 2002
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 07:48 EDT 2024. Contains 371235 sequences. (Running on oeis4.)