login
Number of coprime pairs (a,b) with -n <= a,b <= n.
5

%I #36 Apr 09 2023 02:31:29

%S 8,16,32,48,80,96,144,176,224,256,336,368,464,512,576,640,768,816,960,

%T 1024,1120,1200,1376,1440,1600,1696,1840,1936,2160,2224,2464,2592,

%U 2752,2880,3072,3168,3456,3600,3792,3920,4240,4336,4672,4832,5024,5200,5568

%N Number of coprime pairs (a,b) with -n <= a,b <= n.

%C Number of square lattice points in the region {(x, y): |x| <= n, |y| <= n} visible from the origin. - _Paolo Xausa_, Mar 25 2023

%H Paolo Xausa, <a href="/A137243/b137243.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from Seiichi Manyama).

%H Tom M. Apostol, <a href="https://doi.org/10.1007/978-1-4757-5579-4">Introduction to Analytic Number Theory</a>, Springer, New York, NY, 1976, pp. 62-64.

%F a(n) = 4*A018805(n) + 4. - _Charles R Greathouse IV_, Aug 06 2012

%F a(n) = a(n-1) + 8*EulerPhi(n), with a(1)=8. - _Juan M. Marquez_, Apr 24 2015

%F a(n) ~ (24/Pi^2)*n^2 = 4*A059956*n^2. - _Paolo Xausa_, Mar 25 2023

%e a(1) = 8 because there are eight coprime pairs (1,1), (1,0), (1,-1), (0,1), (0,-1), (-1,1), (-1,0), (-1,-1) with integral entries of absolute value <= 1.

%e In the same way a(2) = 16 as there are sixteen coprime pairs (2,1), (2,-1), (1,2), (1,1), (1,0), (1,-1), (1,-2), (0,1), (0,-1), (-1,2), (-1,1), (-1,0), (-1,-1), (-1,-2), (-2,1), (-2,-1) of integral entries of absolute value <= 2.

%t A137243[nmax_]:=8Accumulate[EulerPhi[Range[nmax]]];A137243[100] (* _Paolo Xausa_, Mar 25 2023 *)

%o (PARI) a(n)=4*sum(k=1, n, moebius(k)*(n\k)^2)+4 \\ _Charles R Greathouse IV_, Aug 06 2012

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A137243(n):

%o if n == 0:

%o return 0

%o c, j = 0, 2

%o k1 = n//j

%o while k1 > 1:

%o j2 = n//k1 + 1

%o c += (j2-j)*(A137243(k1)//4-1)

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

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

%Y Cf. A018805, A059956.

%K nonn

%O 1,1

%A Kilian Kilger (kilian(AT)mathi.uni-heidelberg.de), May 11 2008