A177976 -id:A177976 - cp's OEIS frontend

A015631 Number of ordered triples of integers from [ 1..n ] with no global factor.

1, 3, 8, 15, 29, 42, 69, 95, 134, 172, 237, 287, 377, 452, 552, 652, 804, 915, 1104, 1252, 1450, 1635, 1910, 2106, 2416, 2674, 3007, 3301, 3735, 4027, 4522, 4914, 5404, 5844, 6432, 6870, 7572, 8121, 8805, 9389, 10249, 10831, 11776, 12506

Offset: 1

Olivier Gérard

nonn

Number of integer-sided triangles with at least two sides <= n and sides relatively prime. - Henry Bottomley, Sep 29 2006

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

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

Column k=3 of A177976.

Cf. A000292, A002088, A015616, A015634, A015650, A134543.

[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

with(numtheory):
b:= proc(n) option remember;
       add(mobius(n/d)*d*(d+1)/2, d=divisors(n))
    end:
a:= proc(n) option remember;
      b(n) + `if`(n=1, 0, a(n-1))
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Feb 09 2011

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 *)
Accumulate[Table[Sum[MoebiusMu[n/d]*d*(d + 1)/2, {d, Divisors[n]}], {n, 1, 50}]] (* Vaclav Kotesovec, Jan 31 2019 *)

a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+1, 2))); \\ Seiichi Manyama, Jun 12 2021

a(n) = binomial(n+2, 3)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021

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

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

a(n) = (A071778(n)+3*A018805(n)+2)/6. - Vladeta Jovovic, Dec 01 2004
Partial sums of the Moebius transform of the triangular numbers (A007438). - Steve Butler, Apr 18 2006
a(n) = 2*A123324(n) - A046657(n) for n>1. - Henry Bottomley, Sep 29 2006
Row sums of triangle A134543. - Gary W. Adamson, Oct 31 2007
a(n) ~ n^3 / (6*Zeta(3)). - Vaclav Kotesovec, Jan 31 2019
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^3. - Ilya Gutkovskiy, Feb 14 2020
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

A015634 Number of ordered quadruples of integers from [ 1..n ] with no global factor.

Original entry on oeis.org

1, 4, 13, 29, 63, 106, 189, 289, 444, 626, 911, 1203, 1657, 2130, 2766, 3462, 4430, 5359, 6688, 7992, 9670, 11405, 13704, 15840, 18730, 21548, 25037, 28521, 33015, 37067, 42522, 47690, 53940, 60108, 67760, 74748, 83886, 92433, 102629, 112469, 124809, 135763, 149952

Offset: 1

Olivier Gérard

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Column k=4 of A177976.
Partial sums of A117108.
Cf. A000332, A002088, A013662, A015631, A015650.

a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*Binomial[# + 2, 3] &], {k, 1, n}]; Array[a, 45] (* Amiram Eldar, Jun 07 2025 *)

a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+2, 3))); \\ Seiichi Manyama, Jun 12 2021

a(n) = binomial(n+3, 4)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^4)/(1-x)) \\ Seiichi Manyama, Jun 12 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A015634(n):
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A015634(k1)
        j, k1 = j2, n//j2
    return n*(n+1)*(n+2)*(n+3)//24-c+j-n # Chai Wah Wu, Apr 18 2021

G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^4. - Ilya Gutkovskiy, Feb 14 2020
a(n) = n*(n+1)*(n+2)*(n+3)/24 - Sum_{j=2..n} a(floor(n/j)) = A000332(n+3) - Sum_{j=2..n} a(floor(n/j)). - Chai Wah Wu, Apr 18 2021
a(n) ~ n^4 / (24*zeta(4)). - Amiram Eldar, Jun 08 2025

A015650 Number of ordered 5-tuples of integers from [ 1..n ] with no global factor.

Original entry on oeis.org

1, 5, 19, 49, 118, 225, 434, 729, 1209, 1850, 2850, 4059, 5878, 8044, 11020, 14566, 19410, 24789, 32103, 40213, 50615, 62260, 77209, 93099, 113504, 135431, 162341, 191396, 227355, 264463, 310838, 359322, 417212, 478408, 551944, 626971, 718360, 812311, 922407, 1036667

Offset: 1

Olivier Gérard

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Column k=5 of A177976.
Partial sums of A117109.
Cf. A000389, A002088, A013663, A015631, A015634.

a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*Binomial[# + 3, 4] &], {k, 1, n}]; Array[a, 40] (* Amiram Eldar, Jun 07 2025 *)

a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+3, 4))); \\ Seiichi Manyama, Jun 12 2021

a(n) = binomial(n+4, 5)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^5)/(1-x)) \\ Seiichi Manyama, Jun 12 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A015650(n):
    if n == 0:
        return 0
    c, j = n+1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A015650(k1)
        j, k1 = j2, n//j2
    return n*(n+1)*(n+2)*(n+3)*(n+4)//120-c+j # Chai Wah Wu, Apr 18 2021

G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^5. - Ilya Gutkovskiy, Feb 14 2020
a(n) = n*(n+1)*(n+2)*(n+3)*(n+4)/120 - Sum_{j=2..n} a(floor(n/j)) = A000389(n+4) - Sum_{j=2..n} a(floor(n/j)). - Chai Wah Wu, Apr 18 2021
a(n) ~ n^5 / (120*zeta(5)). - Amiram Eldar, Jun 08 2025

A177975 Square array T(n,k) read by antidiagonals up. Each column is the first column in the matrix inverse of a triangular matrix that is the k-th differences of A051731 in the column direction.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 2, 5, 3, 1, 0, 4, 7, 9, 4, 1, 0, 2, 14, 16, 14, 5, 1, 0, 6, 13, 34, 30, 20, 6, 1, 0, 4, 27, 43, 69, 50, 27, 7, 1, 0, 6, 26, 83, 107, 125, 77, 35, 8, 1, 0, 4, 39, 100, 209, 226, 209, 112, 44, 9, 1, 0, 10, 38, 155, 295, 461, 428, 329, 156, 54, 10, 1

Offset: 1

Mats Granvik, May 16 2010

The first column in this array is the first column in A134540 which is the matrix inverse of A177978. The second column is the first column in A159905. The rows in this array are described by both binomial expressions and closed form polynomials.

			Table begins:
  1..1...1...1....1.....1.....1......1......1.......1.......1
  0..1...2...3....4.....5.....6......7......8.......9......10
  0..2...5...9...14....20....27.....35.....44......54......65
  0..2...7..16...30....50....77....112....156.....210.....275
  0..4..14..34...69...125...209....329....494.....714....1000
  0..2..13..43..107...226...428....749...1234....1938....2927
  0..6..27..83..209...461...923...1715...3002....5004....8007
  0..4..26.100..295...736..1632...3312...6270...11220...19162
  0..6..39.155..480..1266..2975...6399..12825...24255...43692
  0..4..38.182..641..1871..4789..11103..23807...47896...91367
  0.10..65.285.1000..3002..8007..19447..43757...92377..184755
  0..4..50.292.1209..4066.11837..30920..74139..165748..349438
  0.12..90.454.1819..6187.18563..50387.125969..293929..646645
  0..6..75.473.2166..8101.26202..75797.200479..492406.1136048
  0..8.100.636.2976.11482.38523.115915.319231..816421.1960190
  0..8.100.696.3546.14712.52548.167112.483879.1296064.3249312

Seiichi Manyama, Antidiagonals n = 1..140, flattened

Column k=1..5 gives A063524, A000010, A007438, A117108, A117109.
Main diagonal gives A332470.
Cf. A177976, A177977.

T(n, k) = sumdiv(n, d, moebius(n/d)*binomial(d+k-2, d-1)); \\ Seiichi Manyama, Jun 12 2021

From Seiichi Manyama, Jun 12 2021: (Start)
G.f. of column k: Sum_{j>=1} mu(j) * x^j/(1 - x^j)^k.
T(n,k) = Sum_{d|n} mu(n/d) * binomial(d+k-2,d-1). (End)

A177977 Triangle read by rows. Polynomials based on sums of Moebius transforms.

Original entry on oeis.org

1, 1, 0, 1, 3, -2, 1, 6, 5, -6, 1, 10, 35, 26, -48, 1, 15, 85, 165, -26, -120, 1, 21, 175, 735, 1264, -36, -1440, 1, 28, 322, 1960, 5929, 8092, -1212, -10080, 1, 36, 546, 4536, 22449, 60564, 57644, -24816, -80640, 1, 45, 870, 9450, 63273, 254205, 572480

Offset: 1

Mats Granvik, May 16 2010

These polynomials were found by entering the rows of A177976 in Wolfram Alpha. The lower left half equals part of the Stirling numbers of the first kind given in table A094638. To evaluate, enter a value for n and divide row sums with factorial numbers as shown in the example section. n=-1 gives A092149, n=0 gives the Mertens function A002321, n=1 gives A000012, n=2 gives A002088, n=3 gives A015631, and n=4 gives A015634.

			Triangle begins and the polynomials are:
(1*n^0)/1
(1*n^1 +0*n^0)/1
(1*n^2 +3*n^1 -2*n^0)/2
(1*n^3 +6*n^2 +5*n^1 -6*n^0)/6
(1*n^4 +10*n^3 +35*n^2 +26*n^1 -48*n^0)/24
(1*n^5 +15*n^4 +85*n^3 +165*n^2 -26*n^1 -120*n^0)/120
(1*n^6 +21*n^5 +175*n^4 +735*n^3 +1264*n^2 -36*n^1 -1440*n^0)/720

Typo in sequence (erroneous comma) corrected by N. J. A. Sloane, May 22 2010

A345131 Number of ordered n-tuples of integers from [ 1..n ] with no global factor.

Original entry on oeis.org

1, 2, 8, 29, 118, 427, 1671, 6260, 24034, 91301, 351261, 1345434, 5191170, 20018845, 77500485, 300290041, 1166450850, 4535971707, 17670369300, 68913194733, 269114332057, 1051984590581, 4116622325140, 16123381985750, 63204699026898, 247956554702702

Offset: 1

Seiichi Manyama, Jun 12 2021

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1000

Main diagonal of A177976.

Cf. A332470.

a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#] * Binomial[n + # - 2, # - 1] &], {k, 1, n}]; Array[a, 25] (* Amiram Eldar, Jun 13 2021 *)

a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+n-2, d-1)));

a(n) = Sum_{k=1..n} Sum_{d|k} mu(k/d) * binomial(d+n-2, d-1).
a(n) = [x^n] (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^n.
a(n) ~ 2^(2*n-1) / sqrt(Pi*n). - Vaclav Kotesovec, Jun 19 2021

cp's OEIS Frontend

A015631 Number of ordered triples of integers from [ 1..n ] with no global factor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A015634 Number of ordered quadruples of integers from [ 1..n ] with no global factor.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Python

Formula

A015650 Number of ordered 5-tuples of integers from [ 1..n ] with no global factor.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Python

Formula

A177975 Square array T(n,k) read by antidiagonals up. Each column is the first column in the matrix inverse of a triangular matrix that is the k-th differences of A051731 in the column direction.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A177977 Triangle read by rows. Polynomials based on sums of Moebius transforms.

Views

Author

Keywords

Comments

Examples

Extensions

A345131 Number of ordered n-tuples of integers from [ 1..n ] with no global factor.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula