Spoiler for New Scientist Enigma 1759: “Cell count” (Follow the link to see the puzzle.)
I can’t see an easy way to do this by hand, but it can be done in a spreadsheet; the key is to figure out the needed formula.
Consider just the upper right quadrant; of course the number of cells crossed for the whole circle will be 4 times the number for the quadrant. Now consider each increment along the x axis from 0 to 1 to 2 to … to r, the radius. When x goes to (x+1), y goes from √(r2–x2) to √(r2–(x+1)2). The number of cells passed through in this column is 1 greater than the number of times the circle crosses a horizontal line (not counting lines started or ended on). Think about it hard enough and you realize the number of cells crossed in the file starting at x is:
where ⌈x⌉and ⌊x⌋are respectively the ceiling and floor functions. Multiply that by 4 and sum over all x from 0 to r–1 and you have the number of cells crossed.
So put that into a spreadsheet and graph the result: