A015616 -id:A015616 - 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

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

Original entry on oeis.org

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

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.

A343716 Numbers k such that k^2 divides 5^k - 4^k - 3^k.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 18, 24, 26, 30, 36, 50, 72, 74, 90, 130, 150, 338, 370, 450, 650, 962, 1402, 1850, 2738, 2974, 4810, 8450, 12506, 24050, 35594, 64382, 68450, 184706, 270150, 312650, 462722, 889850, 11568050

Offset: 1

Jon E. Schoenfield, May 08 2021

If it exists, a(41) > 10^9.
Of the 4*A015616(10) = 4*109 = 436 integer sequences of one of the forms
     Numbers k such that k^2 | A^k + B^k + C^k,
     Numbers k such that k^2 | A^k + B^k - C^k,
     Numbers k such that k^2 | A^k - B^k + C^k,
  or Numbers k such that k^2 | A^k - B^k - C^k
such that 0 < C < B < A <= 10 and gcd(A,B,C)=1, this one appears to have the largest number of terms.
By comparison, A127074 (k such that k^2 | 3^k - 2^k - 1) and A343115 (k such that k^2 | 5^k - 3^k - 2^k) seem unlikely to have any terms beyond A127074(9)=17807 and A343115(14)=876, respectively. Only 25 of the 436 above sequences have any 4-, 5-, or 6-digit terms at all.
a(41) > 10^11 if it exists. - Chai Wah Wu, May 16 2021

			5^2 - 4^2 - 3^2 = 25 - 16 - 9 = 0, which is divisible by 2^2 = 4, so 2 is a term.
5^18 - 4^18 - 3^18 = 3745590368400 = 11560464100 * 18^2, so 18 is a term.

Cf. A015616, A127074, A343115.

def afind(startat=1, limit=10**9):
  for k in range(startat, limit+1):
    kk = k*k
    if (pow(5, k, kk) - pow(4, k, kk) - pow(3, k, kk))%kk == 0:
      print(k, end=", ")
afind(limit=10**5) # Michael S. Branicky, May 16 2021

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

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

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

A343716 Numbers k such that k^2 divides 5^k - 4^k - 3^k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python