A100613 -id:A100613 - cp's OEIS frontend

A018805 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y)=1}.

1, 3, 7, 11, 19, 23, 35, 43, 55, 63, 83, 91, 115, 127, 143, 159, 191, 203, 239, 255, 279, 299, 343, 359, 399, 423, 459, 483, 539, 555, 615, 647, 687, 719, 767, 791, 863, 899, 947, 979, 1059, 1083, 1167, 1207, 1255, 1299, 1391, 1423, 1507, 1547, 1611, 1659, 1763

Offset: 1

David W. Wilson

Number of positive rational numbers of height at most n, where the height of p/q is max(p, q) when p and q are relatively prime positive integers. - Charles R Greathouse IV, Jul 05 2012
The number of ordered pairs (i,j) with 1<=i<=n, 1<=j<=n, gcd(i,j)=d is a(floor(n/d)). - N. J. A. Sloane, Jul 29 2012
Equals partial sums of A140434 (1, 2, 4, 4, 8, 4, 12, 8, ...) and row sums of triangle A143469. - Gary W. Adamson, Aug 17 2008
Number of distinct solutions to k*x+h=0, where 1 <= k,h <= n. - Giovanni Resta, Jan 08 2013
a(n) is the number of rational numbers which can be constructed from the set of integers between 1 and n, without combination of multiplication and division. a(3) = 7 because {1, 2, 3} can only create {1/3, 1/2, 2/3, 1, 3/2, 2, 3}. - Bernard Schott, Jul 07 2019

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 110-112.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954. See Theorem 332.

Olivier Gérard, Table of n, a(n) for n = 1..100000 [Replaces an earlier b-file from Charles R Greathouse IV]
Jin-Yi Cai and Eric Bach, On testing for zero polynomials by a set of points with bounded precision, Theoret. Comput. Sci. 296 (2003), no. 1, 15-25. MR1965515 (2004m:68279).
Pieter Moree, Counting carefree couples, arXiv:math/0510003 [math.NT], 2005-2014.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Carefree Couple

Cf. A015614, A002088, A100613 (gcd > 1), A071778 (triples), A143469, A140434, A013661, A059956, A137243, A171503.
Cf. A177853 (partial sums).
The main diagonal of A331781, also of A333295.

a018805 n = length [()| x <- [1..n], y <- [1..n], gcd x y == 1]
-- Reinhard Zumkeller, Jan 21 2013

/* based on the first formula */ A018805:=func< n | 2*&+[ EulerPhi(k): k in [1..n] ]-1 >; [ A018805(n): n in [1..60] ]; // Klaus Brockhaus, Jan 27 2011

/* based on the second formula */ A018805:=func< n | n eq 1 select 1 else n^2-&+[ $$(n div j): j in [2..n] ] >; [ A018805(n): n in [1..60] ]; // Klaus Brockhaus, Feb 07 2011

N:= 1000; # to get the first N entries
P:= Array(1..N,numtheory:-phi);
A:= map(t -> 2*round(t)-1, Statistics:-CumulativeSum(P));
convert(A,list); # Robert Israel, Jul 16 2014

FoldList[ Plus, 1, 2 Array[ EulerPhi, 60, 2 ] ] (* Olivier Gérard, Aug 15 1997 *)
Accumulate[2*EulerPhi[Range[60]]]-1 (* Harvey P. Dale, Oct 21 2013 *)

PARI
```
a(n)=sum(k=1,n,moebius(k)*(n\k)^2)
```

A018805(n)=2 *sum(j=1, n, eulerphi(j)) - 1;
for(n=1, 99, print1(A018805(n), ", ")); /* show terms */

a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)*(n\k[1])^2); s \\ Charles R Greathouse IV, Jan 08 2018

from sympy import sieve
def A018805(n): return 2*sum(t for t in sieve.totientrange(1,n+1)) - 1 # Chai Wah Wu, Mar 23 2021

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

a(n) = 2*(Sum_{j=1..n} phi(j)) - 1.
a(n) = n^2 - Sum_{j=2..n} a(floor(n/j)).
a(n) = 2*A015614(n) + 1. - Reinhard Zumkeller, Apr 08 2006
a(n) = 2*A002088(n) - 1. - Hugo van der Sanden, Nov 22 2008
a(n) ~ (1/zeta(2)) * n^2 = (6/Pi^2) * n^2 as n goes to infinity (zeta is the Riemann zeta function, A013661, and the constant 6/Pi^2 is 0.607927..., A059956). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001
a(n) ~ 6*n^2/Pi^2 + O(n*log n). - N. J. A. Sloane, May 31 2020
a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^2. - Benoit Cloitre, May 11 2003
a(n) = A000290(n) - A100613(n) = A015614(n) + A002088(n). - Reinhard Zumkeller, Jan 21 2013
a(n) = A242114(floor(n/k),1), 1<=k<=n; particularly a(n) = A242114(n,1). - Reinhard Zumkeller, May 04 2014
a(n) = 2 * A005728(n) - 3. - David H Post, Dec 20 2016
a(n) ~ 6*n^2/Pi^2, cf. A059956. [Hardy and Wright] - M. F. Hasler, Jan 20 2017
G.f.: (1/(1 - x)) * (-x + 2 * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - Ilya Gutkovskiy, Feb 14 2020

More terms from Reinhard Zumkeller, Apr 08 2006

Link to Moree's paper corrected by Peter Luschny, Aug 08 2009

A140434 Number of new visible points created at each step in an n X n grid.

Original entry on oeis.org

1, 2, 4, 4, 8, 4, 12, 8, 12, 8, 20, 8, 24, 12, 16, 16, 32, 12, 36, 16, 24, 20, 44, 16, 40, 24, 36, 24, 56, 16, 60, 32, 40, 32, 48, 24, 72, 36, 48, 32, 80, 24, 84, 40, 48, 44, 92, 32, 84, 40, 64, 48, 104, 36, 80, 48, 72, 56, 116, 32, 120

Offset: 1

Gregg Whisler, Jun 25 2008, Jun 28 2008

nonn

Equals row sums of triangle A143467. - Gary W. Adamson, Aug 17 2008
Equals first differences of A018805: (1, 3, 7, 11, 19, 23, 35, ...). - Gary W. Adamson, Aug 17 2008
a(n) is the number of rationals p/q such that |p| + |q| = n. - Geoffrey Critzer, Oct 11 2011
a(n) is the number of nonempty lists of positive integers whose continuants are equal to n. For example, for n = 6 these continuants are [6], [5,1], [1,5], and [1,4,1]. - Jeffrey Shallit, May 18 2016
a(n) is the number of Christoffel words of length n, for n>=2. Here a binary word w is a Christoffel word if its first and last letters are different, say w = axb with a<>b, and x is a palindrome, and w is the concatenation of two palindromes.   See the book of Reutenauer. - Jeffrey Shallit, Apr 04 2024

			G.f. = x + 2*x^2 + 4*x^3 + 4*x^4 + 8*x^5 + 4*x^6 + 12*x^7 + 8*x^8 + 12*x^9 + ...

C. Reutenauer, From Christoffel words to Markoff numbers, Oxford University Press, 2019.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A018805, A100613, A140435. Equals twice A000010 (for n >= 2).

a140434 n = a140434_list !! (n-1)
a140434_list = 1 : zipWith (-) (tail a018805_list) a018805_list
-- Reinhard Zumkeller, May 04 2014

f[n_] := FoldList[Plus, 1, 2 Array[EulerPhi, n, 2]] // Differences // Prepend[#, 1]&
a[ n_] := If[ n < 3, Max[0, n], Sum[ MoebiusMu[d] (2 n/d - 1 - Mod[n/d, 2]), {d, Divisors@n}]]; (* Michael Somos, Jul 24 2015 *)

{a(n) = if( n<3, max(0, n), sumdiv(n, d, moebius(d) * (2*n/d - 1 - (n/d)%2)))}; /* Michael Somos, Jul 24 2015 */

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

from sympy import totient
def A140434(n): return totient(n)<<1 if n>1 else 1 # Chai Wah Wu, May 09 2025

a(n) = 2*phi(n), where phi is Euler's phi function, A000010, for n >= 2.
Sum_{k=1..n} a(k)*floor(n/k) = n^2. - Benoit Cloitre, Nov 09 2016
G.f.: Sum_{k>=1} mu(k) * x^k * (1 + x^k)/(1 - x^k)^2. - Seiichi Manyama, May 24 2021

Mathematica simplified by Jean-François Alcover, Jun 06 2013

A063985 Partial sums of cototient sequence A051953.

Original entry on oeis.org

0, 1, 2, 4, 5, 9, 10, 14, 17, 23, 24, 32, 33, 41, 48, 56, 57, 69, 70, 82, 91, 103, 104, 120, 125, 139, 148, 164, 165, 187, 188, 204, 217, 235, 246, 270, 271, 291, 306, 330, 331, 361, 362, 386, 407, 431, 432, 464, 471, 501, 520, 548, 549, 585, 600, 632, 653, 683

Offset: 1

Labos Elemer, Sep 06 2001

nonn

Number of elements in the set {(x,y): 1 <= x <= y <= n, 1 = gcd(x,y)}; a(n) = A000217(n) - A002088(n) = A100613(n) - A185670(n). - Reinhard Zumkeller, Jan 21 2013

8*a(n) is the number of dots not in direct reach via a straight line from the center of a 2*n+1 X 2*n+1 array of dots. - Kiran Ananthpur Bacche, May 25 2022

Harry J. Smith, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A000010, A000217, A002088, A048290, A051953.

a063985 n = length [()| x <- [1..n], y <- [x..n], gcd x y > 1]
-- Reinhard Zumkeller, Jan 21 2013

// Save the file as A063985.java to compile and run
import java.util.stream.IntStream;
import java.util.*;
public class A063985 {
  public static int getInvisiblePoints(int n) {
    Set slopes = new HashSet();
    IntStream.rangeClosed(1, n).forEach(i ->
      {IntStream.rangeClosed(1, n).forEach(j ->
        slopes.add(Float.valueOf((float)i/(float)j))); });
    return (n * n - slopes.size() + n - 1) / 2;
  }
  public static void main(String args[]) throws Exception {
    IntStream.rangeClosed(1, 30).forEach(i ->
      System.out.println(getInvisiblePoints(i)));
  }
} // Kiran Ananthpur Bacche, May 25 2022

f[n_] := n(n + 1)/2 - Sum[ EulerPhi@i, {i, n}]; Array[f, 58] (* Robert G. Wilson v *)
Accumulate[Table[n-EulerPhi[n],{n,1,60}]] (* Harvey P. Dale, Aug 19 2015 *)

{ a=0; for (n=1, 1000, write("b063985.txt", n, " ", a+=n - eulerphi(n)) ) } \\ Harry J. Smith, Sep 04 2009

from sympy.ntheory import totient
def a(n): return sum(x - totient(x) for x in range(1,n + 1))
[a(n) for n in range(1, 51)] # Indranil Ghosh, Mar 18 2017

from functools import lru_cache
@lru_cache(maxsize=None)
def A063985(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)*(k1*(k1+1)-2*A063985(k1)-1)
        j, k1 = j2, n//j2
    return (2*n+c-j)//2 # Chai Wah Wu, Mar 24 2021

a(n) = Sum_{x=1..n} (x - phi(x)) = Sum(x) - Sum(phi(x)) = A000217(n) - A002088(n), phi(n) = A000010(n), cototient(n) = A051953(n).
a(n) = n^2 - A091369(n). - Enrique Pérez Herrero, Feb 25 2012
G.f.: x/(1 - x)^3 - (1/(1 - x))*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 18 2017
a(n) = (1/2 - 3/Pi^2)*n^2 + O(n*log(n)). - Amiram Eldar, Jul 26 2022

Corrected by Robert G. Wilson v, Dec 13 2006

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

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

cp's OEIS Frontend

A018805 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y)=1}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

Extensions

A140434 Number of new visible points created at each step in an n X n grid.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

Extensions

A063985 Partial sums of cototient sequence A051953.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Java

Mathematica

PARI

Python

Python

Formula

Extensions

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula