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

%I #139 Aug 05 2024 04:06:21

%S 1,3,7,11,19,23,35,43,55,63,83,91,115,127,143,159,191,203,239,255,279,

%T 299,343,359,399,423,459,483,539,555,615,647,687,719,767,791,863,899,

%U 947,979,1059,1083,1167,1207,1255,1299,1391,1423,1507,1547,1611,1659,1763

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

%C 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

%C 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

%C 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

%C Number of distinct solutions to k*x+h=0, where 1 <= k,h <= n. - _Giovanni Resta_, Jan 08 2013

%C 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

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 110-112.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954. See Theorem 332.

%H Olivier Gérard, <a href="/A018805/b018805.txt">Table of n, a(n) for n = 1..100000</a> [Replaces an earlier b-file from Charles R Greathouse IV]

%H Jin-Yi Cai and Eric Bach, <a href="http://dx.doi.org/10.1016/S0304-3975(02)00429-2">On testing for zero polynomials by a set of points with bounded precision</a>, Theoret. Comput. Sci. 296 (2003), no. 1, 15-25. MR1965515 (2004m:68279).

%H Pieter Moree, <a href="http://arxiv.org/abs/math/0510003">Counting carefree couples</a>, arXiv:math/0510003 [math.NT], 2005-2014.

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CarefreeCouple.html">Carefree Couple</a>

%F a(n) = 2*(Sum_{j=1..n} phi(j)) - 1.

%F a(n) = n^2 - Sum_{j=2..n} a(floor(n/j)).

%F a(n) = 2*A015614(n) + 1. - _Reinhard Zumkeller_, Apr 08 2006

%F a(n) = 2*A002088(n) - 1. - _Hugo van der Sanden_, Nov 22 2008

%F 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

%F a(n) ~ 6*n^2/Pi^2 + O(n*log n). - _N. J. A. Sloane_, May 31 2020

%F a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^2. - _Benoit Cloitre_, May 11 2003

%F a(n) = A000290(n) - A100613(n) = A015614(n) + A002088(n). - _Reinhard Zumkeller_, Jan 21 2013

%F a(n) = A242114(floor(n/k),1), 1<=k<=n; particularly a(n) = A242114(n,1). - _Reinhard Zumkeller_, May 04 2014

%F a(n) = 2 * A005728(n) - 3. - _David H Post_, Dec 20 2016

%F a(n) ~ 6*n^2/Pi^2, cf. A059956. [Hardy and Wright] - _M. F. Hasler_, Jan 20 2017

%F G.f.: (1/(1 - x)) * (-x + 2 * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - _Ilya Gutkovskiy_, Feb 14 2020

%p N:= 1000; # to get the first N entries

%p P:= Array(1..N,numtheory:-phi);

%p A:= map(t -> 2*round(t)-1, Statistics:-CumulativeSum(P));

%p convert(A,list); # _Robert Israel_, Jul 16 2014

%t FoldList[ Plus, 1, 2 Array[ EulerPhi, 60, 2 ] ] (* _Olivier Gérard_, Aug 15 1997 *)

%t Accumulate[2*EulerPhi[Range[60]]]-1 (* _Harvey P. Dale_, Oct 21 2013 *)

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

%o (PARI) A018805(n)=2 *sum(j=1, n, eulerphi(j)) - 1;

%o for(n=1, 99, print1(A018805(n), ", ")); /* show terms */

%o (PARI) a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)*(n\k[1])^2); s \\ _Charles R Greathouse IV_, Jan 08 2018

%o (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

%o (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

%o (Haskell)

%o a018805 n = length [()| x <- [1..n], y <- [1..n], gcd x y == 1]

%o -- _Reinhard Zumkeller_, Jan 21 2013

%o (Python)

%o from sympy import sieve

%o def A018805(n): return 2*sum(t for t in sieve.totientrange(1,n+1)) - 1 # _Chai Wah Wu_, Mar 23 2021

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A018805(n): # based on second formula

%o if n == 0:

%o return 0

%o c, j = 1, 2

%o k1 = n//j

%o while k1 > 1:

%o j2 = n//k1 + 1

%o c += (j2-j)*A018805(k1)

%o j, k1 = j2, n//j2

%o return n*(n-1)-c+j # _Chai Wah Wu_, Mar 24 2021

%Y Cf. A015614, A002088, A100613 (gcd > 1), A071778 (triples), A143469, A140434, A013661, A059956, A137243, A171503.

%Y Cf. A177853 (partial sums).

%Y The main diagonal of A331781, also of A333295.

%K nonn,nice

%O 1,2

%A _David W. Wilson_

%E More terms from _Reinhard Zumkeller_, Apr 08 2006

%E Link to Moree's paper corrected by _Peter Luschny_, Aug 08 2009