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
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
KEYWORD
nonn
AUTHOR
Kilian Kilger (kilian(AT)mathi.uni-heidelberg.de), May 11 2008
STATUS
approved