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

Author

David W. Wilson

Keywords

• nonn
• nice

Comments

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

References

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

Links

• 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

Crossrefs

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.

Programs

Haskell

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

Magma

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

Magma

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

Maple

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

Mathematica

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)

PARI

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

PARI

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

Python

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

Python

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

Formula

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

Extensions

More terms from Reinhard Zumkeller, Apr 08 2006

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