A015631 - OEIS

%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_