|
%I #135 Dec 04 2022 19:06:18
%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
|
