Solution

Answer: 313135496

Let the image size be $2^N\times 2^N$, and define

$$C = 2^{N-1},\qquad R^2 = 2^{2N-2}.$$

A pixel $(x,y)$ is black iff

$$(x-C)^2+(y-C)^2 \le R^2.$$

So $D_N$ is simply the discrete disk of radius $2^{N-1}$ centered at $(C,C)$.

1. Mathematical analysis

A quadtree node represents an axis-aligned square region

$$[x_0,x_0+s-1]\times [y_0,y_0+s-1]$$

with side length $s=2^k$.

For the encoding:

a monochromatic region costs 2 bits
10 for black
11 for white
a split costs
0 plus the encodings of the four children.

Therefore, if a region is mixed, its cost is

$$1+\sum_{\text{4 children}} \text{cost(child)}.$$

So the problem reduces to:

Determine whether a square is entirely inside the circle, entirely outside, or mixed.

Key geometric observation

For a square region:

Entirely black

The whole square is black iff the farthest pixel from the center is still inside the circle.

Because squared distance is convex, the farthest point of the square is always one of the four corners.

Thus define

$$d_{\max}=\max_{\text{corners}} (x-C)^2+(y-C)^2.$$

$$d_{\max}\le R^2,$$

the whole region is black.

Entirely white

The whole square is white iff the nearest pixel to the center is outside the circle.

The nearest point is obtained by clamping the center coordinate into the square interval:

$$x_n = \min(\max(C,x_0),,x_0+s-1),$$

$$y_n = \min(\max(C,y_0),,y_0+s-1).$$

Then

$$d_{\min}=(x_n-C)^2+(y_n-C)^2.$$

$$d_{\min}>R^2,$$

the whole square is white.

Otherwise: mixed

If neither condition holds, the circle boundary crosses the square, so we split into four quadrants.

2. Recursive formula

Let

$$F(x_0,y_0,s)$$

be the minimal encoding length for that square.

Then:

$$F= \begin{cases} 2 & \text{if entirely black or entirely white},\[4mm] 1+\displaystyle\sum_{i=1}^4 F_i & \text{otherwise}. \end{cases}$$

The recursion depth is only $N=24$, and only boundary-touching regions are expanded.

3. Python implementation

from functools import lru_cache

N = 24

CENTER = 1 << (N - 1)
R2 = 1 << (2 * N - 2)

@lru_cache(None)
def solve(x0, y0, size):
    """
    Return the minimal quadtree encoding length
    for the square:
        x in [x0, x0 + size - 1]
        y in [y0, y0 + size - 1]
    """

    x1 = x0 + size - 1
    y1 = y0 + size - 1

    # ---------------------------------------------------------
    # Test whether the whole square is black.
    # The farthest point from the center is one of the corners.
    # ---------------------------------------------------------

    max_d2 = max(
        (x - CENTER) ** 2 + (y - CENTER) ** 2
        for x in (x0, x1)
        for y in (y0, y1)
    )

    if max_d2 <= R2:
        return 2  # "10"

    # ---------------------------------------------------------
    # Test whether the whole square is white.
    # Find the nearest point in the square to the center.
    # ---------------------------------------------------------

    nearest_x = min(max(CENTER, x0), x1)
    nearest_y = min(max(CENTER, y0), y1)

    min_d2 = (
        (nearest_x - CENTER) ** 2 +
        (nearest_y - CENTER) ** 2
    )

    if min_d2 > R2:
        return 2  # "11"

    # ---------------------------------------------------------
    # Mixed region: split into four quadrants.
    # ---------------------------------------------------------

    half = size // 2

    return (
        1 +  # leading split bit "0"
        solve(x0,         y0 + half, half) +  # top-left
        solve(x0 + half,  y0 + half, half) +  # top-right
        solve(x0,         y0,        half) +  # bottom-left
        solve(x0 + half,  y0,        half)    # bottom-right
    )

answer = solve(0, 0, 1 << N)

print(answer)

4. Code walkthrough

Constants

CENTER = 1 << (N - 1)
R2 = 1 << (2 * N - 2)

These are:

$$C = 2^{N-1}, \qquad R^2 = 2^{2N-2}.$$

Entirely black test

max_d2 = max(...)

The farthest point of a rectangle from the center occurs at a corner.

If even the farthest corner is inside the circle, then every pixel is black.

Entirely white test

nearest_x = min(max(CENTER, x0), x1)
nearest_y = min(max(CENTER, y0), y1)

This computes the closest point in the square to the center.

If that nearest point is already outside the circle, then every pixel is white.

Recursive split

return 1 + ...

The 1 is the split bit 0.

Then we recursively encode the four quadrants in the required order:

top-left
top-right
bottom-left
bottom-right

5. Small sanity checks

For small $N$, the recursion behaves exactly as expected:

large monochromatic blocks compress to 2 bits,
only regions intersecting the circular boundary subdivide further.

The total size grows roughly proportionally to the circle perimeter times recursion depth, which is consistent with the final magnitude (~$3\times10^8$).

After running the program for $N=24$, we obtain:

$$313135496$$

Answer: 313135496

Project Euler Problem 287