A018805 -id:A018805 - cp's OEIS frontend

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

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

A137243 Number of coprime pairs (a,b) with -n <= a,b <= n.

Original entry on oeis.org

8, 16, 32, 48, 80, 96, 144, 176, 224, 256, 336, 368, 464, 512, 576, 640, 768, 816, 960, 1024, 1120, 1200, 1376, 1440, 1600, 1696, 1840, 1936, 2160, 2224, 2464, 2592, 2752, 2880, 3072, 3168, 3456, 3600, 3792, 3920, 4240, 4336, 4672, 4832, 5024, 5200, 5568

Offset: 1

Kilian Kilger (kilian(AT)mathi.uni-heidelberg.de), May 11 2008

nonn

Number of square lattice points in the region {(x, y): |x| <= n, |y| <= n} visible from the origin. - Paolo Xausa, Mar 25 2023

			a(1) = 8 because there are eight coprime pairs (1,1), (1,0), (1,-1), (0,1), (0,-1), (-1,1), (-1,0), (-1,-1) with integral entries of absolute value <= 1.
In the same way a(2) = 16 as there are sixteen coprime pairs (2,1), (2,-1), (1,2), (1,1), (1,0), (1,-1), (1,-2), (0,1), (0,-1), (-1,2), (-1,1), (-1,0), (-1,-1), (-1,-2), (-2,1), (-2,-1) of integral entries of absolute value <= 2.

Paolo Xausa, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Seiichi Manyama).
Tom M. Apostol, Introduction to Analytic Number Theory, Springer, New York, NY, 1976, pp. 62-64.

Cf. A018805, A059956.

A137243[nmax_]:=8Accumulate[EulerPhi[Range[nmax]]];A137243[100] (* Paolo Xausa, Mar 25 2023 *)

a(n)=4*sum(k=1, n, moebius(k)*(n\k)^2)+4 \\ Charles R Greathouse IV, Aug 06 2012

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

a(n) = 4*A018805(n) + 4. - Charles R Greathouse IV, Aug 06 2012
a(n) = a(n-1) + 8*EulerPhi(n), with a(1)=8. - Juan M. Marquez, Apr 24 2015
a(n) ~ (24/Pi^2)*n^2 = 4*A059956*n^2. - Paolo Xausa, Mar 25 2023

A242114 Triangle read by rows: T(n,k) = number of pairs (x,y) in {1..n}X{1..n} with gcd(x,y) = k.

Original entry on oeis.org

1, 3, 1, 7, 1, 1, 11, 3, 1, 1, 19, 3, 1, 1, 1, 23, 7, 3, 1, 1, 1, 35, 7, 3, 1, 1, 1, 1, 43, 11, 3, 3, 1, 1, 1, 1, 55, 11, 7, 3, 1, 1, 1, 1, 1, 63, 19, 7, 3, 3, 1, 1, 1, 1, 1, 83, 19, 7, 3, 3, 1, 1, 1, 1, 1, 1, 91, 23, 11, 7, 3, 3, 1, 1, 1, 1, 1, 1, 115, 23

Offset: 1

Reinhard Zumkeller, May 04 2014

T(n,1) = A018805(n);
sum(T(n,k): k = 1..n) = A000290(n);
sum(T(n,k): k = 2..n) = A100613(n);
T(floor(n/k),1) = A018805(n).

			T(4,1) = #{(1,1), (1,2), (1,3), (1,4), (2,1), (2,3), (3,1), (3,2), (3,4), (4,1), (4,3)} = 11;
T(4,2) = #{(2,2), (2,4), (4,2)} = 3;
T(4,3) = #{(3,3)} = 1;
T(4,4) = #{(4,4)} = 1.
The triangle begins:                                            row sums
.   1:    1                                                            1
.   2:    3   1                                                        4
.   3:    7   1   1                                                    9
.   4:   11   3   1   1                                               16
.   5:   19   3   1   1  1                                            25
.   6:   23   7   3   1  1  1                                         36
.   7:   35   7   3   1  1  1  1                                      49
.   8:   43  11   3   3  1  1  1  1                                   64
.   9:   55  11   7   3  1  1  1  1  1                                81
.  10:   63  19   7   3  3  1  1  1  1  1                            100
.  11:   83  19   7   3  3  1  1  1  1  1  1                         121
.  12:   91  23  11   7  3  3  1  1  1  1  1  1                      144
.  13:  115  23  11   7  3  3  1  1  1  1  1  1  1                   169
.  14:  127  35  11   7  3  3  3  1  1  1  1  1  1  1                196
.  15:  143  35  19   7  7  3  3  1  1  1  1  1  1  1  1             225
.  16:  159  43  19  11  7  3  3  3  1  1  1  1  1  1  1  1          256
.  17:  191  43  19  11  7  3  3  3  1  1  1  1  1  1  1  1  1       289
.  18:  203  55  23  11  7  7  3  3  3  1  1  1  1  1  1  1  1  1    324 .

Reinhard Zumkeller, Rows n = 1..125 of table, flattened

a242114 n k = a242114_tabl !! (n-1) !! (k-1)
a242114_row n = a242114_tabl !! (n-1)
a242114_tabl = map (map a018805) a010766_tabl

T[n_, k_] := 2 Total[EulerPhi[Range[Quotient[n, k]]]] - 1;
Table[T[n, k], {n, 1, 18}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 20 2021 *)

T(n,k) = A018805(A010766(n,k));

A343282 Number of ordered 5-tuples (v,w, x, y, z) with gcd(v, w, x, y, z) = 1 and 1 <= {v, w, x, y, z} <= 10^n.

Original entry on oeis.org

1, 96601, 9645718621, 964407482028001, 96438925911789115351, 9643875373658964992585011, 964387358678775616636890654841, 96438734235127451288511508421855851, 9643873406165059293451290072800801506621

Offset: 0

Karl-Heinz Hofmann, Apr 10 2021

nonn

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.

Chai Wah Wu, Table of n, a(n) for n = 0..15

Cf. A082544, A013663, A342586, A342841, A343193.
Related counts of k-tuples:
pairs: A018805, A342632, A342586;
triples: A071778, A342935, A342841;
quadruples: A082540, A343527, A343193;
5-tuples: A343282;
6-tuples: A343978, A344038. - N. J. A. Sloane, Jun 13 2021

from labmath import mobius
def A343282(n): return sum(mobius(k)*(10**n//k)**5 for k in range(1, 10**n+1))

Lim_{n->infinity} a(n)/10^(5*n) = 1/zeta(5) = A343308.

a(n) = A082544(10^n). - Chai Wah Wu, Apr 11 2021

Edited by N. J. A. Sloane, Jun 13 2021

A344038 Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= 10^n).

Original entry on oeis.org

1, 983583, 983029267047, 982960635742968103, 982953384128772770413831, 982952672223441253533233827367, 982952600027678075050509511271466303, 982952593055042000417993486008754893529583, 982952592342881094406730790044111038427637071855

Offset: 0

Karl-Heinz Hofmann, May 07 2021

Chai Wah Wu, Table of n, a(n) for n = 0..15

Cf. A342586, A342841, A343193, A343282, A343359, A013664.
Cf. A343978, A071778, A018805, A082540, A082544.
Related counts of k-tuples:
pairs: A018805, A342632, A342586;
triples: A071778, A342935, A342841;
quadruples: A082540, A343527, A343193;
5-tuples: A343282;
6-tuples: A343978, A344038. - N. J. A. Sloane, Jun 13 2021

a(n)={sum(k=1, 10^n+1, moebius(k)*(10^n\k)^6)} \\ Andrew Howroyd, May 08 2021

from labmath import mobius
def A344038(n): return sum(mobius(k)*(10**n//k)**6 for k in range(1, 10**n+1))

Lim_{n->infinity} a(n)/10^(6*n) = 1/zeta(6) = A343359 = 945/Pi^4.

a(n) = A343978(10^n).

Edited by N. J. A. Sloane, Jun 13 2021

A143270 a(n) = n*A002088(n).

Original entry on oeis.org

1, 4, 12, 24, 50, 72, 126, 176, 252, 320, 462, 552, 754, 896, 1080, 1280, 1632, 1836, 2280, 2560, 2940, 3300, 3956, 4320, 5000, 5512, 6210, 6776, 7830, 8340, 9548, 10368, 11352, 12240, 13440, 14256, 15984, 17100, 18486, 19600, 21730, 22764, 25112

Offset: 1

Gary W. Adamson, Aug 03 2008

nonn

Also number of reduced fractions with denominators <= n and values between 1/n and n (inclusive). - Reinhard Zumkeller, Jan 15 2009

			a(4) = 24 = n*A002088(n) = 4*6.
a(4) = 24 = sum of row 4 terms of triangle A143269: (4 + 4 + 8 + 8).
a(3) = #{1/3,1/2,2/3,1,4/3,3/2,5/3,2,7/3,5/2,8/3,3} = 12. - _Reinhard Zumkeller_, Jan 15 2009

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A000010, A002088, A143269.

Module[{nn=50,ps},ps=Accumulate[EulerPhi[Range[nn]]];Times@@@Thread[{Range[nn],ps}]] (* Harvey P. Dale, Jun 04 2023 *)

list(nmax) = {my(s = vector(nmax, k, eulerphi(k))); for(k = 2, nmax, s[k] += s[k-1]); for(k = 1, nmax, s[k] = k*s[k]); s} \\ Amiram Eldar, Jun 01 2025

from functools import lru_cache
@lru_cache(maxsize=None)
def A143270(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A143270(k1)//k1-1)
        j, k1 = j2, n//j2
    return n*(n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 25 2021

a(n) = n*A002088(n), where A002088(n) = partial sums of phi(n).
Equals row sums of triangle A143269.
a(n) = Sum_{i=1..n} Sum_{j=1..i*n} 0^(gcd(i,j)-1). - Reinhard Zumkeller, Jan 15 2009
a(n) = (3/Pi^2) * n^3 + O(n^2*log(n)). - Amiram Eldar, Jun 01 2025

More terms from Reinhard Zumkeller, Jan 15 2009

A185670 Number of pairs (x,y) with 1 <= x < y <= n with at least one common factor.

Original entry on oeis.org

0, 0, 0, 1, 1, 4, 4, 7, 9, 14, 14, 21, 21, 28, 34, 41, 41, 52, 52, 63, 71, 82, 82, 97, 101, 114, 122, 137, 137, 158, 158, 173, 185, 202, 212, 235, 235, 254, 268, 291, 291, 320, 320, 343, 363, 386, 386, 417, 423, 452, 470, 497, 497, 532, 546, 577, 597, 626, 626, 669, 669, 700, 726, 757, 773, 818, 818, 853, 877, 922, 922, 969, 969, 1006, 1040

Offset: 1

Olivier Gérard, Feb 09 2011

			For n=9, the a(9)=9 pairs are {(2,4),(2,6),(2,8),(3,6),(3,9),(4,6),(4,8),(6,8),(6,9)}.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Oliver Knill, Some experiments in number theory, arXiv preprint arXiv:1606.05971 [math.NT], 2016.

Cf. A016035, A063985, A100613.

a185670 n = length [(x,y) | x <- [1..n-1], y <- [x+1..n], gcd x y > 1]
-- Reinhard Zumkeller, Mar 02 2012

with(numtheory): A185670:=n->n*(n-1)/2 + 1 - add( phi(i), i=1..n): seq(A185670(n), n=1..100); # Wesley Ivan Hurt, Jan 30 2017

1 + Accumulate[ Table[n - EulerPhi[n] - 1, {n, 1, 75}]] (* Jean-François Alcover, Jan 04 2013 *)

a185670(n) = sum(i=2, n, sum(j=2, i-1, gcd(i,j)>1)) \\ Hugo Pfoertner, Sep 04 2024

from functools import lru_cache
@lru_cache(maxsize=None)
def A185670(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 2, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(k1*(k1-1)+1-2*A185670(k1))
        j, k1 = j2, n//j2
    return (c-j)//2 # Chai Wah Wu, Mar 24 2021

a(p) = a(p-1) when p is prime.
a(n)-a(n-1) = A016035(n).
a(n) = n*(n-1)/2 + 1 - Sum_{i=1..n} phi(i).
a(n) = A100613(n) - A063985(n). - Reinhard Zumkeller, Jan 21 2013

Definition clarified by Reinhard Zumkeller, Mar 02 2012

A206297 Position of n in the canonical bijection from the positive integers to the positive rational numbers.

Original entry on oeis.org

1, 3, 5, 9, 13, 21, 25, 37, 45, 57, 65, 85, 93, 117, 129, 145, 161, 193, 205, 241, 257, 281, 301, 345, 361, 401, 425, 461, 485, 541, 557, 617, 649, 689, 721, 769, 793, 865, 901, 949, 981, 1061, 1085, 1169, 1209, 1257, 1301, 1393, 1425, 1509, 1549

Offset: 1

Clark Kimberling, Feb 06 2012

nonn

The canonical bijection from the positive integers to the positive rational numbers is given by A038568(n)/A038569(n).
Appears to be a variant of A049691. - R. J. Mathar, Feb 11 2012
It appears that a(n) = 2*A005728(n) - 1. - Chris Boyd, Mar 21 2015

			The canonical bijection starts with 1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, so that this sequence starts with 1,3,5,9,13 and A206350 starts with 1,2,4,8,12.

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A038568, A038569, A206350.

A049691 is an essentially identical sequence. See also A018805.

a[n_] := Module[{s = 1, k = 2, j = 1},
  While[s <= n, s = s + 2*EulerPhi[k]; k = k + 1];
  s = s - 2*EulerPhi[k - 1];
  While[s <= n, If[GCD[j, k - 1] =
    = 1, s = s + 2]; j = j + 1];
  If[s > n + 1, j - 1, k - 1]];
t = Table[a[n], {n, 0, 3000}];   (* A038568 *)
ReplacePart[1 + Flatten[Position[t, 1]], 1, 1]
(* A206297 *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A206297(n):
    if n == 1:
        return 1
    c, j = 1, 2
    k1 = (n-1)//j
    while k1 > 1:
        j2 = (n-1)//k1 + 1
        c += (j2-j)*(A206297(k1+1)-2)
        j, k1 = j2, (n-1)//j2
    return (n-2)*(n-1)-c+j+2 # Chai Wah Wu, Aug 04 2024

A225531 Number of ordered pairs (i, j) with i, j >= 0, i + j <= n and gcd(i, j) <= 1.

Original entry on oeis.org

1, 3, 4, 6, 8, 12, 14, 20, 24, 30, 34, 44, 48, 60, 66, 74, 82, 98, 104, 122, 130, 142, 152, 174, 182, 202, 214, 232, 244, 272, 280, 310, 326, 346, 362, 386, 398, 434, 452, 476, 492, 532, 544, 586, 606, 630, 652, 698, 714, 756, 776

Offset: 0

Robert Price, May 09 2013

This sequence is in reply to an extension request made in A100449.

Note that gcd(0,m) = m for any m.

Robert Price, Table of n, a(n) for n = 0..400

Cf. A018805, A027430, A100448, A100449, A100450, A213207, A213208, A213212, A213213.

f[n_] := Length[Complement[Union[Flatten[Table[If[i + j <= n && GCD[i, j] <= 1, {i, j}], {i, 0, n}, {j, 0, n}], 1]], {Null}]]; Table[f[n], {n, 0, 100}]

alist(N) = my(c=2); vector(N, i, if(1==i, 1, c+=eulerphi(i-1))); \\ Ruud H.G. van Tol, Jul 09 2024

A280877 Occurrences of decrease of the probability density P(a(n)) of coprime numbers k,m, satisfying 1 <= k <= a(n) and 1 <= m <= a(n); i.e., P(a(n)) < P(a(n)-1).

Original entry on oeis.org

2, 4, 6, 8, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 28, 30, 32, 33, 34, 36, 38, 40, 42, 44, 45, 46, 48, 50, 52, 54, 56, 58, 60, 62, 63, 64, 66, 68, 70, 72, 74, 75, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128

Offset: 1

A.H.M. Smeets, Jan 09 2017

nonn

Probability densities satisfying P(a(n)) < P(a(n)-1).
A285022 is a subset.
Related to Euler phi function by P(a(n)) = ((2*Sum_{1 <= m <= a(n)} phi(m))-1)/a(n)^2.
The sequence is very regular in the sense that all {0 < i} 2i appear in this sequence, as well as all {0 < i} 30i - 15 appear in this sequence.
Presuming P(n) > 0.6: phi(n)/n < 1/2 for n congruent to 0 mod 2, P(n) < P(n-1).
Presuming P(n) > 0.6: phi(n)/n < 8/15 for n congruent to 15 mod 30, P(n) < P(n-1).
A280877 = {i > 0 | 2i} union {i > 0 | 30i - 15} union A280878 union A280879.
The irregular appearances are given in the two disjoint sequences A280878 and A280879.
See also A285022.
Experimental observation: n/a(n) < Euler constant (A001620).
Probability density P(a(n)) = A018805(a(n))/a(n)^2.
There seems, with good reason, to be a high correlation between the odd numbers in this sequence and A079814. - Peter Munn, Apr 11 2021

A.H.M. Smeets, Table of n, a(n) for n = 1..5682
Mark Kac, Statistical independence in probability, analysis and number theory, Carus Monograph 12, Math. Assoc. Amer., 1959, pp. 53-79.

Cf. A001620, A018805, A079814, A279796, A280878, A285022.

P[n_] := P[n] = (2 Sum[CoprimeQ[i, j] // Boole, {i, n}, {j, i-1}] + 1)/n^2;
Select[Range[2, 200], P[#] < P[#-1]&] (* Jean-François Alcover, Nov 15 2019 *)

P(n) = sum(i=1, n, sum(j=1, n, gcd(i,j)==1))/n^2;
isok(n) = P(n) < P(n-1); \\ Michel Marcus, Jan 28 2017

from math import gcd
t = 1
to = 1
i = 1
x = 1
while x < 10000:
    x = x + 1
    y = 0
    while y < x:
        y = y + 1
        if gcd(x,y) == 1:
            t = t + 2
    e = t*(x-1)*(x-1) - to*x*x
    if e < 0:
        print(i,x)
        i = i + 1
    to = t

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A137243 Number of coprime pairs (a,b) with -n <= a,b <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A242114 Triangle read by rows: T(n,k) = number of pairs (x,y) in {1..n}X{1..n} with gcd(x,y) = k.

Views

Author

Keywords

Comments

Examples

Links

Programs

Haskell

Mathematica

Formula

A343282 Number of ordered 5-tuples (v,w, x, y, z) with gcd(v, w, x, y, z) = 1 and 1 <= {v, w, x, y, z} <= 10^n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Formula

Extensions

A344038 Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= 10^n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A143270 a(n) = n*A002088(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A185670 Number of pairs (x,y) with 1 <= x < y <= n with at least one common factor.

Views

Author

Keywords

Examples

Links