|
%I #63 Sep 08 2022 08:44:40
%S 1,3,8,15,29,42,69,95,134,172,237,287,377,452,552,652,804,915,1104,
%T 1252,1450,1635,1910,2106,2416,2674,3007,3301,3735,4027,4522,4914,
%U 5404,5844,6432,6870,7572,8121,8805,9389,10249,10831,11776,12506
%N Number of ordered triples of integers from [ 1..n ] with no global factor.
%C Number of integer-sided triangles with at least two sides <= n and sides relatively prime. - _Henry Bottomley_, Sep 29 2006
%H R. J. Mathar, <a href="/A015631/b015631.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = (A071778(n)+3*A018805(n)+2)/6. - _Vladeta Jovovic_, Dec 01 2004
%F Partial sums of the Moebius transform of the triangular numbers (A007438). - _Steve Butler_, Apr 18 2006
%F a(n) = 2*A123324(n) - A046657(n) for n>1. - _Henry Bottomley_, Sep 29 2006
%F Row sums of triangle A134543. - _Gary W. Adamson_, Oct 31 2007
%F a(n) ~ n^3 / (6*Zeta(3)). - _Vaclav Kotesovec_, Jan 31 2019
%F G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^3. - _Ilya Gutkovskiy_, Feb 14 2020
%F a(n) = n*(n+1)*(n+2)/6 - Sum_{j=2..n} a(floor(n/j)) = A000292(n) - Sum_{j=2..n} a(floor(n/j)). - _Chai Wah Wu_, Mar 30 2021
%e a(4) = 15 because the 15 triples in question are in lexicographic order: [1,1,1], [1,1,2], [1,1,3], [1,1,4], [1,2,2], [1,2,3], [1,2,4], [1,3,3], [1,3,4], [1,4,4], [2,2,3], [2,3,3], [2,3,4], [3,3,4] and [3,4,4]. - _Wolfdieter Lang_, Apr 04 2013
%e The a(4) = 15 triangles with at least two sides <= 4 and sides relatively prime (see _Henry Bottomley_'s comment above) are: [1,1,1], [1,2,2], [2,2,3], [1,3,3], [2,3,3], [2,3,4], [3,3,4], [3,3,5], [1,4,4], [2,4,5], [3,4,4], [3,4,5], [3,4,6], [4,4,5], [4,4,7]. - _Alois P. Heinz_, Feb 14 2020
%p with(numtheory):
%p b:= proc(n) option remember;
%p add(mobius(n/d)*d*(d+1)/2, d=divisors(n))
%p end:
%p a:= proc(n) option remember;
%p b(n) + `if`(n=1, 0, a(n-1))
%p end:
%p seq(a(n), n=1..60); # _Alois P. Heinz_, Feb 09 2011
%t a[1] = 1; a[n_] := a[n] = Sum[MoebiusMu[n/d]*d*(d+1)/2, {d, Divisors[n]}] + a[n-1]; Table[a[n], {n, 1, 60}] (* _Jean-François Alcover_, Jan 20 2014, after Maple *)
%t Accumulate[Table[Sum[MoebiusMu[n/d]*d*(d + 1)/2, {d, Divisors[n]}], {n, 1, 50}]] (* _Vaclav Kotesovec_, Jan 31 2019 *)
%o (Magma) [n eq 1 select 1 else Self(n-1)+ &+[MoebiusMu(n div d) *d*(d+1)/2:d in Divisors(n)]:n in [1..50]]; // _Marius A. Burtea_, Feb 14 2020
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def A015631(n):
%o if n == 0:
%o return 0
%o c, j = 1, 2
%o k1 = n//j
%o while k1 > 1:
%o j2 = n//k1 + 1
%o c += (j2-j)*A015631(k1)
%o j, k1 = j2, n//j2
%o return n*(n-1)*(n+4)//6-c+j # _Chai Wah Wu_, Mar 30 2021
%o (PARI) a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+1, 2))); \\ _Seiichi Manyama_, Jun 12 2021
%o (PARI) a(n) = binomial(n+2, 3)-sum(k=2, n, a(n\k)); \\ _Seiichi Manyama_, Jun 12 2021
%o (PARI) my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^3)/(1-x)) \\ _Seiichi Manyama_, Jun 12 2021
%Y Column k=3 of A177976.
%Y Cf. A000292, A002088, A015616, A015634, A015650, A134543.
%K nonn
%O 1,2
%A _Olivier Gérard_
|
