Counting unit squares circle passes through

Question

Write a program or function that given an integer radius r returns the number of unit squares the circle with radius r centered at the origin passes through. If the circle passes exactly through a point on the grid that does not count as passing through the adjacent unit squares.

Here's an illustration for r = 5:

illustration ^{Illustration by Kival Ngaokrajang, found on OEIS}

Examples:

0 → 0
1 → 4
4 → 28
5 → 28
49 → 388
50 → 380
325 → 2540
5524 → 44180
5525 → 44020

• Luke: OEIS - A242118
• Martin Ender: @Luke I just went looking for this, but it seems to use a slightly different definition (at least it doesn't agree on N = 50).
• orlp: @smls By counting in the bounding square. Make sure that you do not count squares where the circle only touches a corner. The numbers on OEIS are wrong, I have a correction in review right now.
• Patrick Roberts: I have a sudden urge to build domes in minecraft again...
• nitro2k01: Are you a fellow 3Blue1Brown viewer?

Answer 1

Python 2, 54 bytes

f=lambda r,x=0:r-x and-~((r*r-x*x)**.5%1>0)*4+f(r,x+1)

Try it online!

Less golfed (55 bytes) (TIO)

lambda r:8*r-4*sum((r*r-x*x)**.5%1==0for x in range(r))

This estimates the output as 8*r, then corrects for vertex crossings. The result is 8*r-g(r*r), where g(x) counts the number of ways to write x as a sum of two squares (except g(0)=0).

If the circle never went through any vertices, the number of cells touched would equal the number of edges crossed. The circle passes through 2*r vertical gridlines and 2*r horizontal gridlines, passing each one in both directions, for a total of 8*r.

But, each crossing at a vertex counts as two edge crossings while only entering one new cell. So, we compensate by subtracting the number of vertex crossings. This includes the points on axes like (r,0) as well as Pythagorean triples like (4,3) for r=5.

We count for a single quadrant the points (x,y) with x>=0 and y>0 with x*x+y*y==n, then multiply by 4. We do this by counting the numer of sqrt(r*r-x*x) that are whole number for x in the interval [0,r).

Answer 2

Mathematica, 48 bytes

4Count[Range@#~Tuples~2,l_/;Norm[l-1]<#<Norm@l]&

Looks at the first quadrant and counts the number of grid cells for which the input falls between the norms of the cell's lower left and upper right corners (multiplying the result by 4, of course).

• miles: Another method is 8#-SquaresR[2,#^2]Sign@#& based on xnor's post
• Martin Ender: @miles Oh wow, I had no clue SquaresR exists. Feel free to post that yourself (or let xnor post it).

Answer 3

Python 2, 72 bytes

lambda n:sum(0<n*n-x*x-y*y<2*(x-~y)for x in range(n)for y in range(n))*4

Try it online!

Answer 4

Jelly, (削除) 21 (削除ここまで) (削除) 13 (削除ここまで) (削除) 12 (削除ここまで) 11 bytes

×ばつ4

Try it online!

How it works

×ばつ4 Main link. Argument: r
R Range; yield [1, 2, ..., r].
 2 Square; yield [12, 22, ..., r2].
 2 Square; yield r2.
 ạ Absolute difference; yield [r2-12, r2-22, ..., r2-r2].
 Æ2 Test if each of the differences is a perfect square.
 S Sum, counting the number of perfect squares and thus the integer
 solutions of the equation x2 + y2 = r2 with x > 0 and y ≥ 0.
 Ḥ Un-halve; yield 2r.
 ạ Subtract the result to the left from the result to the right.
 ×ばつ4 Multiply by 4.

Answer 5

Perl 6, 61 bytes

->\r{4*grep {my &n={[+] $_»2};n(1 X+$_)>r2>.&n},(^r X ^r)}

How it works

->\r{ } # Lambda (accepts the radius).
 (^r X ^r) # Pairs from (0,0) to (r-1,r-1),
 # representing the bottom-left
 # corners of all squares in
 # the top-right quadrant.
 grep { } # Filter the ones matching:
 my &n={[+] $_»2}; # Lambda to calculate the norm.
 n(1 X+$_)>r2 # Top-right corner is outside,
 >.&n # and bottom-left is inside.
 4* # Return length of list times 4.

Answer 6

AWK, 90 bytes

{z=1ドル*1ドル
for(x=1ドル;x>=0;x--)for(y=0;y<=1ドル;y++){d=z-x*x-y*y
if(d>0&&d<2*(x+y)+2)c++}0ドル=4*c}1

Usage:

awk '{z=1ドル*1ドル
 for(x=1ドル;x>=0;x--)for(y=0;y<=1ドル;y++){d=z-x*x-y*y
 if(d>0&&d<2*(x+y)+2)c++}0ドル=4*c}1' <<< 5525

Just a simple search through quadrant 1 to find all boxes that will intersect the circle. Symmetry allows for the multiply by 4. Could go from -1ドル to 1ドル, but that would take a more bytes and be less efficient. Obviously this is not the most time efficient of algorithms, but it only takes about 16 seconds to run the 5525 case on my machine.

Answer 7

Haskell, 74 bytes

f n=sum[4|x<-[0..n],y<-[0..n],(1+n-x)^2+(1+n-y)^2>n^2,(n-x)^2+(n-y)^2<n^2]

Pretty straightforward, count the number of squares between (0,0) and (n,n) where the bottom left is inside the circle and the top right is outside the circle, then multiply by 4.

Answer 8

Pyth, 29 bytes

Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2

Try it!

Explanation

Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2 # implicit input: Q
Lsm*ddb # define norm function
 s # sum
 m b # map each coordinate to
 *dd # its square
 ^UQ2 # cartesian square of [0, 1, ..., Q - 1]
 # -> list of coordinates of all relevant grid points
 f # filter the list of coordinates T where:
 }*QQ # square of Q is in
 r # the range [
 hyT # 1 + norm(T),
 # ^ coordinate of lower left corner
 ym+1dT # norm(map({add 1}, T))
 # ^^^^^^^^^^^^^^^ coordinate of upper right corner
 # ) <- half-open range
 l # size of the filtered list
 # -> number of passed-through squares in the first quadrant
 *4 # multiply by 4
 # implicit print

Answer 9

Batch, 147 bytes

@set/an=0,r=%1*%1
@for /l %%i in (0,1,%1)do @for /l %%j in (0,1,%1)do @set/a"i=%%i,j=%%j,a=i*i+j*j-r,i+=1,j+=1,a&=r-i*i-j*j,n-=a>>31<<2
@echo %n%

Somewhat inspired by the AWK and Haskell answers.

• Robert Benson: Glad I can somewhat inspire someone :)

Answer 10

Bash + Unix utilities, 127 bytes

c()(d=$[(n/r+1ドル)**2+(n%r+1ドル)**2-r*r];((d))&&echo -n $[d<0])
r=1ドル
bc<<<`for((n=0;n<r*r;n++));{ c 0;c 1;echo;}|egrep -c 01\|10`*4

Try it online!

Just go through all the points in the first quadrant, count them up, and multiply by 4. It can be very slow, but it works.

Answer 11

JavaScript (ES7), 76 bytes

n=>4*(G=k=>k<n?Math.ceil((n**2-k++**2)**0.5)-(0|(n**2-k**2)**0.5)+G(k):0)(0)

• Neil: Can you perhaps shave off a couple of bytes by recursing from n down to 0?
• George Reith: @Neil I did try but couldn't see a way. Wanted to use just one function but still need to store both n radius and k iteration and all attempts came out same bytes
• George Reith: @Neil Ah I see what you are saying about k<n?... but I lose out on those bytes reordering at n**2-k++**2 because the operator precedence is wrong when going in reverse and subtraction is non-commutative so the left side always needs to have k-1 and needs parentheses. Unless you've found a way?
• Neil: Ah, I overlooked the subtraction... maybe you can multiply the whole thing by -4 instead of 4 to work around that? (Although that might still eat up into your saving...)