PHP, 85 83 bytes
The code:
function f($n){for($x=$n;$x;$c+=$x,$y++)for(;$n*$n<$x*$x+$y*$y;$x--);return$c*4+1;}
Its outcome (check https://3v4l.org/bC0cY for multiple PHP versions):
f(1001)=3147833
time=0.000236 seconds.
The ungolfed code:
/**
* Count all the points having x > 0, y >= 0 (a quarter of the circle)
* then multiply by 4 and add the origin.
*
* Walk the lattice points in zig-zag starting at ($n,0) towards (0,$n), in the
* neighbourhood of the circle. While outside the circle, go left.
* Go one line up and repeat until $x == 0.
* This way it checks about 2*$n points (i.e. its complexity is linear, O(n))
*
* @param int $n
* @return int
*/
function countLatticePoints2($n)
{
$count = 0;
// Start on the topmost right point of the circle ($n,0), go towards the topmost point (0,$n)
// Stop when reach it (but don't count it)
for ($y = 0, $x = $n; $x > 0; $y ++) {
// While outside the circle, go left;
for (; $n * $n < $x * $x + $y * $y; $x --) {
// Nothing here
}
// ($x,$y) is the rightmost lattice point on row $y that is inside the circle
// There are exactly $x lattice points on the row $y that have x > 0
$count += $x;
}
// Four quarters plus the center
return 4 * $count + 1;
}
A naive implementation that checks $n*($n+1) points (and runs 1000 times slower but still computes f(1001) in less than 0.5 seconds) and the test suite (using the sample data provided in the question) can be found on github.
