The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A018805 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y)=1}. 68
 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 (list; graph; refs; listen; history; text; internal format)
 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]]-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)^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. Sequence in context: A092109 A117991 A118260 * A191037 A292083 A135932 Adjacent sequences:  A018802 A018803 A018804 * A018806 A018807 A018808 KEYWORD nonn,nice AUTHOR EXTENSIONS More terms from Reinhard Zumkeller, Apr 08 2006 Link to Moree's paper corrected by Peter Luschny, Aug 08 2009 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 15 17:50 EDT 2021. Contains 343920 sequences. (Running on oeis4.)