The OEIS is supported by the many generous donors to the OEIS 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}. 77
 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[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

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

Last modified July 23 17:14 EDT 2024. Contains 374552 sequences. (Running on oeis4.)