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,2

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

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

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

Prog

(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
(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
(Haskell)
a018805 n = length [()| x <- [1..n], y <- [1..n], gcd x y == 1]
-- Reinhard Zumkeller, Jan 21 2013
(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

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.

Sequence in context: A277878 A117991 A118260 * A191037 A292083 A135932

Adjacent sequences: A018802 A018803 A018804 * A018806 A018807 A018808

Keyword

nonn,nice

Author

David W. Wilson

Extensions

More terms from Reinhard Zumkeller, Apr 08 2006

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

Status

approved