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

8, 16, 32, 48, 80, 96, 144, 176, 224, 256, 336, 368, 464, 512, 576, 640, 768, 816, 960, 1024, 1120, 1200, 1376, 1440, 1600, 1696, 1840, 1936, 2160, 2224, 2464, 2592, 2752, 2880, 3072, 3168, 3456, 3600, 3792, 3920, 4240, 4336, 4672, 4832, 5024, 5200, 5568

Offset

1,1

Comments

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

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Seiichi Manyama).

Tom M. Apostol, Introduction to Analytic Number Theory, Springer, New York, NY, 1976, pp. 62-64.

Formula

a(n) = 4*A018805(n) + 4. - Charles R Greathouse IV, Aug 06 2012

a(n) = a(n-1) + 8*EulerPhi(n), with a(1)=8. - Juan M. Marquez, Apr 24 2015

a(n) ~ (24/Pi^2)*n^2 = 4*A059956*n^2. - Paolo Xausa, Mar 25 2023

Example

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.
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.

Mathematica

A137243[nmax_]:=8Accumulate[EulerPhi[Range[nmax]]]; A137243[100] (* Paolo Xausa, Mar 25 2023 *)

Prog

(PARI) a(n)=4*sum(k=1, n, moebius(k)*(n\k)^2)+4 \\ Charles R Greathouse IV, Aug 06 2012
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A137243(n):
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(A137243(k1)//4-1)
        j, k1 = j2, n//j2
    return 4*(n*(n-1)-c+j) # Chai Wah Wu, Mar 29 2021

Crossrefs

Cf. A018805, A059956.

Sequence in context: A106841 A260711 A139598 * A360124 A303026 A068935

Adjacent sequences: A137240 A137241 A137242 * A137244 A137245 A137246

Keyword

nonn

Author

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

Status

approved