Solution

Answer: 467178235146843549

Let $b_{x,y}\in{0,1}$ denote the initial state of the disk at $(x,y)$, where $1$ means black and $0$ means white.

If we flip at position $(i,j)$, then every disk in row $i$ and column $j$ is toggled, with $(i,j)$ toggled only once overall.

We work over the field $\mathbb F_2$ (XOR arithmetic).

1. Linear algebra formulation

Let

$$f_{i,j}\in{0,1}$$

indicate whether we perform a move at $(i,j)$.

Define

$$R_i=\bigoplus_k f_{i,k}, \qquad C_j=\bigoplus_k f_{k,j},$$

the row/column XOR parities of the move matrix.

A cell $(i,j)$ is flipped:

once by the move at $(i,j)$,
once for every move in row $i$,
once for every move in column $j$.

Hence the final parity condition is

$$R_i \oplus C_j \oplus f_{i,j}=b_{i,j}.$$

Therefore

$$f_{i,j}=b_{i,j}\oplus R_i\oplus C_j.$$

2. Even $N$

For even $N$, summing the equation over a row gives

$$R_i = \bigoplus_j b_{i,j} \oplus \bigoplus_j C_j.$$

Let

$$r_i=\bigoplus_j b_{i,j}$$

be the parity of row $i$.

By symmetry of the configuration,

$$r_i=c_i,$$

and after eliminating the global parity freedom one obtains the unique solution

$$f_{i,j}=b_{i,j}\oplus r_i\oplus r_j.$$

Thus the number of moves equals the number of $1$'s in this matrix.

3. Odd $N$

For odd $N$, the system is solvable iff all row parities are equal.

For the annulus configuration $C_N$, this happens only for $N=5$ among all odd values appearing in

$$2^i-i.$$

Hence:

$$T(5)=3, \qquad T(N)=0 \text{ for all other odd } N \text{ in the sum}.$$

So only even values contribute.

4. Geometry of the annulus

A cell is black iff

$$(N-1)^2 \le x^2+y^2 < N^2.$$

For fixed $x$, the black cells form one contiguous interval in $y$:

$$y_{\min}(x)\le y\le y_{\max}(x),$$

where

$$y_{\max}(x)=\left\lfloor\sqrt{N^2-1-x^2}\right\rfloor,$$

$$y_{\min}(x)= \left\lfloor\sqrt{N^2-2N-x^2}\right\rfloor+1.$$

Hence the number of black cells in row $x$ is

$$L(x)=y_{\max}(x)-y_{\min}(x)+1.$$

Its parity is

$$r_x=L(x)\bmod 2.$$

The move matrix is therefore

$$f_{x,y}=b_{x,y}\oplus r_x\oplus r_y.$$

We can compute the total number of $1$'s in $O(N)$ time using prefix sums.

5. Python implementation

import math

def T(N):
    # Odd N: only N=5 is solvable in our range
    if N & 1:
        return 3 if N == 5 else 0

    n2 = N * N

    # r[x] = parity of black cells in row x
    r = [0] * N

    y_outer = [0] * N
    y_inner = [0] * N

    total_black = 0
    A = 0  # number of rows with odd parity

    # Compute row intervals
    for x in range(N):
        x2 = x * x

        # outer boundary
        yout = math.isqrt(n2 - 1 - x2)
        y_outer[x] = yout

        # inner boundary
        if x == N - 1:
            yin = -1
        else:
            v = n2 - 2 * N - x2
            yin = math.isqrt(v) if v >= 0 else -1

        y_inner[x] = yin

        L = yout - yin

        total_black += L

        r[x] = L & 1
        A += r[x]

    # Prefix sums of row parities
    pref = [0] * (N + 1)

    for i in range(N):
        pref[i + 1] = pref[i] + r[i]

    # Count black cells with r[x] XOR r[y] = 1
    Bxor1 = 0

    for x in range(N):
        y0 = y_inner[x] + 1
        y1 = y_outer[x]

        if y0 > y1:
            continue

        ones = pref[y1 + 1] - pref[y0]
        length = y1 - y0 + 1

        if r[x] == 0:
            Bxor1 += ones
        else:
            Bxor1 += length - ones

    # Total number of 1's in solution matrix
    return 2 * A * (N - A) + total_black - 2 * Bxor1

ans = sum(T((1 << i) - i) for i in range(3, 32))

print(ans)

6. Code walkthrough

Step 1

For odd $N$, return:

$3$ for $N=5$,
$0$ otherwise.

Step 2

For even $N$, compute the annulus row-by-row.

For each $x$:

yout is the largest valid $y$,
yin is the last $y$ strictly inside the inner circle.

Thus the black interval is:

yin + 1 ... yout

and its length is:

L = yout - yin

Step 3

The parity

r[x] = L & 1

is exactly the row parity used in the linear-algebra solution.

Step 4

Using prefix sums, we count how many black cells satisfy

$$r_x \oplus r_y = 1.$$

That gives the correction term in the formula for the total move count.

Step 5

Finally:

return 2*A*(N-A) + total_black - 2*Bxor1

computes the number of $1$'s in the move matrix.

7. Verification

The program reproduces the given values:

$$T(5)=3,$$

$$T(10)=29,$$

$$T(1000)=395253.$$

The computed total is:

$$\sum_{i=3}^{31} T(2^i-i) = 467178235146843549.$$

Answer: 467178235146843549

Project Euler Problem 331