cp's OEIS Frontend

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

%I A100448 #23 Mar 29 2021 14:47:37
%S A100448 0,1,4,9,19,30,51,73,106,140,195,241,319,388,480,572,708,813,984,1124,
%T A100448 1310,1485,1738,1926,2216,2462,2777,3059,3465,3749,4214,4590,5060,
%U A100448 5484,6048,6474,7140,7671,8331,8899,9719,10289,11192,11902,12754,13535,14616
%N A100448 Number of triples (i,j,k) with 1 <= i <= j < k <= n and gcd{i,j,k} = 1.
%C A100448 Probably the partial sums of A102309. - _Ralf Stephan_, Jan 03 2005
%H A100448 R. J. Mathar, <a href="/A100448/b100448.txt">Table of n, a(n) for n = 1..10000</a>
%F A100448 a(n) = (A071778(n)-1)/6. - _Vladeta Jovovic_, Nov 30 2004
%F A100448 a(n) = (1/6)*(-1 + Sum_{k=1..n} moebius(k)*floor(n/k)^3). - _Ralf Stephan_, Jan 03 2005
%p A100448 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;
%t A100448 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 *)
%o A100448 (Python)
%o A100448 from functools import lru_cache
%o A100448 @lru_cache(maxsize=None)
%o A100448 def A100448(n):
%o A100448     if n == 0:
%o A100448         return 0
%o A100448     c, j = 2, 2
%o A100448     k1 = n//j
%o A100448     while k1 > 1:
%o A100448         j2 = n//k1 + 1
%o A100448         c += (j2-j)*(6*A100448(k1)+1)
%o A100448         j, k1 = j2, n//j2
%o A100448     return (n*(n**2-1)-c+j)//6 # _Chai Wah Wu_, Mar 29 2021
%Y A100448 Cf. A015616, A015631, A027430, A071778, A018805.
%K A100448 nonn,easy
%O A100448 1,3
%A A100448 _N. J. A. Sloane_, Nov 21 2004
%E A100448 More terms from _Robert G. Wilson v_, Dec 14 2004
%E A100448 Edited by _N. J. A. Sloane_, Sep 06 2008 at the suggestion of _R. J. Mathar_