login
Number of points of norm^2 <= n^2 in the square lattice that are visible from the origin.
1

%I #10 Jun 15 2014 14:08:28

%S 1,5,9,17,33,49,73,89,121,153,193,225,265,313,385,441,481,545,617,673,

%T 769,833,929,1001,1113,1193,1281,1385,1489,1585,1705,1817,1961,2073,

%U 2225,2345,2481,2601,2753,2913,3065,3185,3361,3481,3697,3857,4017,4177

%N Number of points of norm^2 <= n^2 in the square lattice that are visible from the origin.

%C A lattice point (i,j) is "visible" from the origin if no other lattice point lies on the line segment from (0,0) to (i,j), which is equivalent to saying that i and j are relatively prime. By convention, we say that (0,0) is visible from the origin.

%D Tom M. Apostol, "Introduction to Analytic Number Theory", Springer-Verlag, Section 3.8.

%H Robert Israel, <a href="/A059743/b059743.txt">Table of n, a(n) for n = 0..7152</a>

%p N:= 100; # to get a(0) to a(N)

%p for n from 1 to N do

%p C[n]:= Array(1..n,j -> `if`(igcd(n,j)=1,1,0)):

%p B[n]:= map(round,Statistics[CumulativeSum](C[n]));

%p od:

%p 1, 5, 9, seq(1 + 8*(add(numtheory[phi](x),x=1..floor(n/sqrt(2)))+add(B[x][floor(sqrt(n^2-x^2))],x=ceil(n/sqrt(2))..n-1)), n = 3 .. N); # _Robert Israel_, Jun 15 2014

%Y See also A000328, where visibility is not required.

%K nonn

%O 0,2

%A _John W. Layman_, Oct 13 2001