A015631 -id:A015631 - cp's OEIS frontend

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

0, 1, 4, 9, 19, 30, 51, 73, 106, 140, 195, 241, 319, 388, 480, 572, 708, 813, 984, 1124, 1310, 1485, 1738, 1926, 2216, 2462, 2777, 3059, 3465, 3749, 4214, 4590, 5060, 5484, 6048, 6474, 7140, 7671, 8331, 8899, 9719, 10289, 11192, 11902, 12754, 13535, 14616

Offset: 1

N. J. A. Sloane, Nov 21 2004

Probably the partial sums of A102309. - Ralf Stephan, Jan 03 2005

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

Cf. A015616, A015631, A027430, A071778, A018805.

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;

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

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

a(n) = (A071778(n)-1)/6. - Vladeta Jovovic, Nov 30 2004

a(n) = (1/6)*(-1 + Sum_{k=1..n} moebius(k)*floor(n/k)^3). - Ralf Stephan, Jan 03 2005

More terms from Robert G. Wilson v, Dec 14 2004

Edited by N. J. A. Sloane, Sep 06 2008 at the suggestion of R. J. Mathar

A090025 Number of distinct lines through the origin in 3-dimensional cube of side length n.

Original entry on oeis.org

0, 7, 19, 49, 91, 175, 253, 415, 571, 805, 1033, 1423, 1723, 2263, 2713, 3313, 3913, 4825, 5491, 6625, 7513, 8701, 9811, 11461, 12637, 14497, 16045, 18043, 19807, 22411, 24163, 27133, 29485, 32425, 35065, 38593, 41221, 45433, 48727, 52831

Offset: 0

Joshua Zucker, Nov 25 2003

nonn

Equivalently, lattice points where the GCD of all coordinates = 1.

			a(2) = 19 because the 19 points with at least one coordinate=2 all make distinct lines and the remaining 7 points and the origin are on those lines.

Cf. A000225, A001047, A060867, A090020, A090021, A090022, A090023, A090024 are for n dimensions with side length 1, 2, 3, 4, 5, 6, 7, 8, respectively. A049691, A090025, A090026, A090027, A090028, A090029 are this sequence for 2, 3, 4, 5, 6, 7 dimensions. A090030 is the table for n dimensions, side length k.

Cf. A071778.

aux[n_, k_] := If[k == 0, 0, (k + 1)^n - k^n - Sum[aux[n, Divisors[k][[i]]], {i, 1, Length[Divisors[k]] - 1}]];lines[n_, k_] := (k + 1)^n - Sum[Floor[k/i - 1]*aux[n, i], {i, 1, Floor[k/2]}] - 1;Table[lines[3, k], {k, 0, 40}]
a[n_] := Sum[MoebiusMu[k]*((Floor[n/k]+1)^3-1), {k, 1, n}]; Table[a[n], {n, 0, 39}] (* Jean-François Alcover, Nov 28 2013, after Vladeta Jovovic *)

a(n)=(n+1)^3-sum(j=2,n+1,a(floor(n/j)))

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

a(n) = A090030(3, n).
a(n) = Sum_{k=1..n} moebius(k)*((floor(n/k)+1)^3-1). - Vladeta Jovovic, Dec 03 2004
a(n) = (n+1)^3 - Sum_{j=2..n+1} a(floor(n/j)). - Seth A. Troisi, Aug 29 2013
a(n) = 6*A015631(n) + 1 for n>=1. - Hugo Pfoertner, Mar 30 2021

A007438 Moebius transform of triangular numbers.

Original entry on oeis.org

1, 2, 5, 7, 14, 13, 27, 26, 39, 38, 65, 50, 90, 75, 100, 100, 152, 111, 189, 148, 198, 185, 275, 196, 310, 258, 333, 294, 434, 292, 495, 392, 490, 440, 588, 438, 702, 549, 684, 584, 860, 582, 945, 730, 876, 803, 1127, 776, 1197, 910, 1168, 1020, 1430

Offset: 1

N. J. A. Sloane

nonn

a(n)=|{(x,y):1<=x<=y<=n, gcd(x,y,n)=1}|. E.g. a(4)=7 because of the pairs (1,1), (1,2), (1,3), (1,4), (2,3), (3,3), (3,4). - Steve Butler, Apr 18 2006
Partial sums of a(n) give A015631(n). - Steve Butler, Apr 18 2006
Equals row sums of triangle A159905. - Gary W. Adamson, Apr 25 2009; corrected by Mats Granvik, Apr 24 2010

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Transforms

Cf. A000217.

Cf. A159905. - Gary W. Adamson, Apr 25 2009

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

a[n_] := Sum[MoebiusMu[n/d]*d*(d+1)/2, {d, Divisors[n]}]; Array[a, 60] (* Jean-François Alcover, Apr 17 2014 *)

a(n) = sumdiv(n, d, moebius(n/d)*d*(d+1)/2); \\ Michel Marcus, Nov 05 2018

a(n) = (A007434(n)+A000010(n))/2, half the sum of the Mobius transforms of n^2 and n. Dirichlet g.f. (zeta(s-2)+zeta(s-1))/(2*zeta(s)). - R. J. Mathar, Feb 09 2011

G.f.: Sum_{n>=1} a(n)*x^n/(1 - x^n) = x/(1 - x)^3. - Ilya Gutkovskiy, Apr 25 2017

A015617 Number of (unordered) triples of integers from [1,n] with no common factors between pairs.

Original entry on oeis.org

0, 0, 1, 2, 7, 8, 19, 25, 37, 42, 73, 79, 124, 138, 159, 183, 262, 277, 378, 405, 454, 491, 640, 668, 794, 850, 959, 1016, 1257, 1285, 1562, 1668, 1805, 1905, 2088, 2150, 2545, 2673, 2866, 2968, 3457, 3522, 4063, 4228, 4431, 4620, 5269, 5385, 5936

Offset: 1

Olivier Gérard

nonn

Form the graph with nodes 1..n, joining two nodes by an edge if they are relatively prime; a(n) = number of triangles in this graph. - N. J. A. Sloane, Feb 06 2011. The number of edges in this graph is A015614. - Roberto Bosch Cabrera, Feb 07 2011.

			For n=5, there are a(5)=7 triples: (1,2,3), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,5) and (3,4,5) out of binomial(5,3) = 10 triples of distinct integers <= 5.

Charles R Greathouse IV, Table of n, a(n) for n = 1..1000

Subset of A015616 (triples with no common factor) and A015631 (ordered triples with no common factor).

Cf. A185953 (first differences), A186230, Column 3 of triangle A186974.

a[n_] := Select[Subsets[Range[n], {3}], And @@ (GCD @@ # == 1 & /@ Subsets[#, {2}]) &] // Length; a /@ Range[49]
(* Jean-François Alcover, Jul 11 2011 *)

a(n)=sum(a=1,n-2,sum(b=a+1,n-1,sum(c=b+1,n, gcd(a,b)==1 && gcd(a,c)==1 && gcd(b,c)==1))) \\ Charles R Greathouse IV, Apr 28 2015

For large n one can show that a(n) ~ C*binomial(n,3), where C = 0.28674... = A065473. - N. J. A. Sloane, Feb 06 2011.

a(n) = Sum_{r=1..n} Sum_{k=1..r} A186230(r,k). - Alois P. Heinz, Feb 17 2011

Added one example and 2 cross-references. - Olivier Gérard, Feb 06 2011.

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

A177976 Square array T(n,k) read by antidiagonals up. Cumulative column sums of A177975.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 8, 4, 1, 1, 10, 15, 13, 5, 1, 1, 12, 29, 29, 19, 6, 1, 1, 18, 42, 63, 49, 26, 7, 1, 1, 22, 69, 106, 118, 76, 34, 8, 1, 1, 28, 95, 189, 225, 201, 111, 43, 9, 1, 1, 32, 134, 289, 434, 427, 320, 155, 53, 10, 1, 1, 42, 172, 444, 729, 888, 748, 484, 209, 64, 11, 1

Offset: 1

Mats Granvik, May 16 2010

Each row is described by both a binomial expression and a closed form polynomial. The closed form polynomials given in A177977 extends this table to the left. For example the 0th column is A002321 and the -1st column is A092149.

Also number of ordered k-tuples of integers from [ 1..n ] with no global factor. - Seiichi Manyama, Jun 12 2021

			Table begins:
  1..1...1....1.....1.....1......1......1.......1.......1.......1
  1..2...3....4.....5.....6......7......8.......9......10......11
  1..4...8...13....19....26.....34.....43......53......64......76
  1..6..15...29....49....76....111....155.....209.....274.....351
  1.10..29...63...118...201....320....484.....703.....988....1351
  1.12..42..106...225...427....748...1233....1937....2926....4278
  1.18..69..189...434...888...1671...2948....4939....7930...12285
  1.22..95..289...729..1624...3303...6260...11209...19150...31447
  1.28.134..444..1209..2890...6278..12659...24034...43405...75139
  1.32.172..626..1850..4761..11067..23762...47841...91301..166506
  1.42.237..911..2850..7763..19074..43209...91598..183678..351261
  1.46.287.1203..4059.11829..30911..74129..165737..349426..700699
  1.58.377.1657..5878.18016..49474.124516..291706..643355.1347344
  1.64.452.2130..8044.26117..75676.200313..492185.1135761.2483392
  1.72.552.2766.11020.37599.114199.316228..811416.1952182.4443582
  1.80.652.3462.14566.52311.166747.483340.1295295.3248246.7692894

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

Column k=1..5 gives A000012, A002088, A015631, A015634, A015650.

Cf. A177975, A177977, A344527, A345229.

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

T(n, k) = binomial(n+k-1, k)-sum(j=2, n, T(n\j, k)); \\ Seiichi Manyama, Jun 12 2021

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

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

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

Original entry on oeis.org

0, 0, 1, 4, 10, 19, 34, 52, 79, 109, 154, 196, 262, 325, 409, 493, 613, 712, 865, 997, 1171, 1336, 1567, 1747, 2017, 2251, 2548, 2818, 3196, 3472, 3907, 4267, 4717, 5125, 5665, 6079, 6709, 7222, 7858, 8410, 9190, 9748, 10609, 11299, 12127

Offset: 1

Olivier Gérard

nonn

			For n=6, the a(6) = 19 solutions are the binomial(6,3) = (6*5*4)/(1*2*3) = 20 possible triples minus the triple (2,4,6) with GCD=2.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A000292, A100448, A027430, A015631.

f:=proc(n) local i,j,k,t1,t2,t3; t1:=0; for i from 1 to n-2 do for j from i+1 to n-1 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;
# program based on Moebius transform, partial sums of A000741:
with(numtheory):
b:= proc(n) option remember;
      add(mobius(n/d)*(d-2)*(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..100);  # Alois P. Heinz, Feb 08 2011

a[n_] := (cnt = 0; Do[cnt += Boole[GCD[i, j, k] == 1], {i, 1, n-2}, {j, i+1, n-1}, {k, j+1, n}]; cnt); Table[a[n], {n, 1, 45}] (* Jean-François Alcover, Mar 05 2013 *)

print1(c=0);for(k=1,99,for(j=1,k-1, gcd(j,k)==1 && (c+=j-1) && next; for(i=1,j-1, gcd([i,j,k])>1 || c++)); print1(", "c))

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

a(n) = (A071778(n) - 3*A018805(n) + 2)/6. - Vladeta Jovovic, Dec 01 2004
a(n) = Sum_{i=1..n} A000741(i). - Alois P. Heinz, Feb 08 2011
For n > 1, a(n) = n(n-1)(n-2)/6 - Sum_{j=2..n} a(floor(n/j)) = A000292(n-2) - Sum_{j=2..n} a(floor(n/j)). - Chai Wah Wu, Mar 30 2021

A134542 A134541 * A000012.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 3, 3, 2, 1, 1, 2, 3, 3, 2, 1, 1, 3, 4, 4, 3, 2, 1, 1, 3, 4, 4, 4, 3, 2, 1, 1, 3, 4, 5, 5, 4, 3, 2, 1, 1, 2, 4, 5, 5, 5, 4, 3, 2, 1

Offset: 1

Gary W. Adamson, Oct 31 2007

Row sums = A002088: (1, 2, 4, 6, 10, 12, 18, 22, ...).

A134542 * [1,2,3,...] = A015631: (1, 3, 8, 15, 29, 42, ...).

			First few rows of the triangle:
  1;
  1, 1;
  1, 2, 1;
  1, 2, 2, 1;
  1, 3, 3, 2, 1;
  1, 2, 3, 3, 2, 1;
  1, 3, 4, 4, 3, 2, 1;
  1, 3, 4, 4, 4, 3, 2, 1;
  1, 3, 4, 5, 5, 4, 3, 2, 1;
  1, 2, 4, 5, 5, 5, 4, 3, 2, 1;
  ...

Cf. A134541, A002088, A015631.

A134541 * A000012 as infinite lower triangular matrices.

Triangle read by rows, partial sums of A134541 terms starting from the right.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A090025 Number of distinct lines through the origin in 3-dimensional cube of side length n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A007438 Moebius transform of triangular numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A015617 Number of (unordered) triples of integers from [1,n] with no common factors between pairs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A177976 Square array T(n,k) read by antidiagonals up. Cumulative column sums of A177975.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

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

Views

Author