Detailed mathematical approach

Problem Summary

Problem 1000 is a milestone problem that bundles three independent sub-problems whose answers are then fed into a single meta-recurrence. The final answer is one residue modulo \(p=10^9+7\).

The three sub-problems are:

• Max-And \(I(n)\). Partition \(\{1,2,\dots,n\}\) into two groups \(A\) and \(B\). Score a partition by \(\sum_{a\in A,\,b\in B}(a \mathbin{\&} b)\), the sum of the bitwise AND over every cross pair. \(I(n)\) is the maximum score. We are told \(I(10)=50\) and must find \(I(1000)\).
• Max-Xor \(X(N)\). For integers write \([x,y]=x^2\oplus y^2\) (the XOR of the squares). Consider sequences \(a_0,a_1,\dots,a_r\) with \(1\le a_i\le N\) whose consecutive weights strictly increase, \([a_{i-1},a_i]\lt [a_i,a_{i+1}]\). \(X(N)\) is the maximum possible value of \(\sum_i [a_{i-1},a_i]\). We are told \(X(4)=71\) and \(X(10)=702\), and must find \(X(1000)\).
• Unreachable Nim \(C(N)\). In three-pile Nim a status \((a,b,c)\) is unreachable if it can only ever occur as a starting position. \(C(N)\) counts unreachable statuses with \(0\le a,b,c\lt N\). We are told \(C(10)=123\) and must find \(C(1000)\).

The meta-recurrence \(M\) is then defined by

$$M(0)=I(1000),\quad M(1)=X(1000),\quad M(2)=C(1000),$$

$$M(k)=M(k-1)\,M(k-2)\,M(k-3)\pmod{p}\quad(k\ge 3),$$

with the checkpoint \(M(4)\equiv 457587170 \pmod p\). The required answer is \(M(1000)\bmod p\).

None of the three sub-problems is solved by brute force at \(n=1000\); each collapses to a structural formula or a small dynamic program. The brute-force routines in the code exist only to validate the fast ones on small inputs.

Mathematical Approach

Sub-problem \(I(n)\): a bitwise maximum cut

The bitwise AND distributes over bits. Writing the \(k\)-th bit of an integer \(x\) as \(x_k\in\{0,1\}\),

$$a \mathbin{\&} b=\sum_{k\ge0}2^k\,a_k b_k.$$

Summing over all cross pairs and exchanging the order of summation, the score depends on the bits only through how many elements on each side carry each bit:

$$\sum_{a\in A,\,b\in B}(a\mathbin{\&} b)=\sum_{k\ge0}2^k\Big(\sum_{a\in A}a_k\Big)\Big(\sum_{b\in B}b_k\Big)=\sum_{k\ge0}2^k\,x_k\,y_k,$$

where \(x_k\) and \(y_k\) count the elements of \(A\) and \(B\) having bit \(k\) set. Let

$$m_k=\#\{1\le v\le n : v_k=1\}=x_k+y_k$$

be the total number of integers in \([1,n]\) whose bit \(k\) is set. This total is fixed by \(n\); only its split \((x_k,y_k)\) depends on the partition.

For each bit independently, \(x_k y_k\) is maximized under \(x_k+y_k=m_k\) by the most balanced split, giving \(\big\lfloor m_k^2/4\big\rfloor\). Hence we always have the upper bound

$$I(n)\le U(n):=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor.$$

The subtlety is that one single partition must balance every bit at once. The construction that does so is to colour each integer by the parity of its population count: put \(v\) in \(A\) when \(\operatorname{popcount}(v)\) is even and in \(B\) when it is odd. For a fixed bit \(k\), let

$$s_k=\#\{v_k=1,\ \operatorname{popcount}(v)\text{ even}\}-\#\{v_k=1,\ \operatorname{popcount}(v)\text{ odd}\}$$

be the signed discrepancy. Then \(x_k=(m_k+s_k)/2\), \(y_k=(m_k-s_k)/2\), and the achieved value of bit \(k\) is

$$x_k y_k=\frac{m_k^2-s_k^2}{4}.$$

This matches the optimum \(\lfloor m_k^2/4\rfloor\) exactly when \(|s_k|=m_k\bmod 2\), i.e. the parity colouring balances the integers carrying bit \(k\) to within a single element. That is indeed the case: among the integers in \([1,n]\) with bit \(k\) set, toggling the lowest bit different from \(k\) is an involution that flips the population-count parity while staying inside the range, so it matches even-parity elements with odd-parity ones up to at most one leftover. Therefore \(s_k=0\) when \(m_k\) is even and \(s_k=\pm1\) when \(m_k\) is odd, and the parity partition is simultaneously optimal on every bit:

$$\boxed{\,I(n)=\sum_{k\ge0}2^k\left\lfloor\frac{m_k^2}{4}\right\rfloor\,}.$$

The code computes both \(U(n)\) (the per-bit optimum) and the value achieved by the explicit parity partition, and asserts they are equal — turning the optimality proof into a runtime check.

Worked example \(I(10)=50\). The bit totals over \(\{1,\dots,10\}\) are \(m_0=5\) (odd numbers \(1,3,5,7,9\)), \(m_1=5\) (\(2,3,6,7,10\)), \(m_2=4\) (\(4,5,6,7\)), \(m_3=3\) (\(8,9,10\)). Hence

$$I(10)=1\!\cdot\!\Big\lfloor\tfrac{25}{4}\Big\rfloor+2\!\cdot\!\Big\lfloor\tfrac{25}{4}\Big\rfloor+4\!\cdot\!\Big\lfloor\tfrac{16}{4}\Big\rfloor+8\!\cdot\!\Big\lfloor\tfrac{9}{4}\Big\rfloor=6+12+16+16=50.$$

Sub-problem \(X(N)\): a longest increasing-weight walk

Place a vertex at each integer \(1,\dots,N\) and give the (undirected) edge between \(u\) and \(v\) the weight

$$w(u,v)=u^2\oplus v^2.$$

A valid sequence \(a_0,a_1,\dots,a_r\) is a walk \(a_0\to a_1\to\cdots\to a_r\) whose consecutive edge weights are strictly increasing, and \(X(N)\) is the maximum total weight of such a walk. This is the classic longest path under increasing edge weights, which is solvable greedily by processing edges in nondecreasing weight order.

Maintain \(\textit{best}[v]\) = the largest total weight of a valid (strictly increasing) walk that ends at vertex \(v\); initialise all entries to \(0\) (an empty walk). Sort all directed edges by weight and sweep through them. For an edge \(u\to v\) of weight \(w\), a walk ending at \(u\) with all weights \(\lt w\) can be extended by this edge, giving the candidate \(\textit{best}[u]+w\). To honour the strict inequality, all edges sharing the same weight \(w\) must be handled as one batch: every candidate in the batch is computed from the \(\textit{best}\) values before the batch, and only after the whole batch is scored are the \(\textit{best}\) entries updated. This prevents two equal-weight edges from chaining inside one walk. The answer is the maximum candidate seen over the whole sweep:

$$X(N)=\max_{\text{edges }u\to v}\big(\textit{best}[u]+w(u,v)\big).$$

Correctness. In any valid walk the weights strictly increase, so when an edge of weight \(w\) is processed every lighter edge has already been relaxed and \(\textit{best}[u]\) already reflects the best walk into \(u\) using only weights \(\lt w\). Batching equal weights guarantees no walk uses two edges of the same weight consecutively, which is exactly the strict-increase condition. The published checkpoints \(X(4)=71\) and \(X(10)=702\) are reproduced by this sweep.

Sub-problem \(C(N)\): unreachable Nim positions by digit DP

In normal-play Nim each move strictly decreases exactly one pile. Recall the Sprague–Grundy / Bouton theory: a position is a losing \(P\)-position exactly when the nim-sum \(s=a\oplus b\oplus c\) is \(0\); otherwise it is a winning \(N\)-position and the winning move sends it to a \(P\)-position. Under optimal play the visited positions therefore alternate \(N,P,N,P,\dots\)

Fix an \(N\)-position \((a,b,c)\) with nim-sum \(s\ne0\) and let \(\beta\) be the highest set bit of \(s\). Suppose it is reached as the result of a move out of a \(P\)-position \((x,y,z)\) (so \(x\oplus y\oplus z=0\)) by reducing one pile, say \(z\to z'\lt z\). The new nim-sum is \(z\oplus z'\), whose top bit is the highest bit where \(z\) and \(z'\) differ; since \(z'\lt z\), that pile \(z'\) does not carry bit \(\beta\). So any \(N\)-position that can follow a \(P\)-position has at least one pile lacking bit \(\beta\). Contrapositively:

$$\big(a,b,c\big)\text{ is unreachable }\iff s\ne0\ \text{ and bit }\beta\text{ is set in all of }a,b,c.$$

(If some pile lacks bit \(\beta\), one can raise that pile to the XOR of the other two — a strictly larger value, since the missing top bit forces it up — producing a genuine \(P\)-position predecessor, so the position does occur mid-game.) Hence

$$C(N)=\#\Big\{(a,b,c)\in[0,N)^3 : s=a\oplus b\oplus c\ne0,\ a_\beta=b_\beta=c_\beta=1,\ \beta=\text{top bit of }s\Big\}.$$

This is counted with a bitwise digit DP. Enumerate the candidate top bit \(\beta\). For a triple to contribute with this \(\beta\):

• at every bit above \(\beta\), the three bits must XOR to \(0\) (so \(s\) has no set bit above \(\beta\));
• at bit \(\beta\) all three bits are \(1\) (so \(s\) has bit \(\beta\), it is the top bit, and all piles carry it);
• at every bit below \(\beta\) the bits are free.

Each pile must additionally satisfy \(a,b,c\le N-1\). The DP scans bits from most to least significant carrying a \(3\)-bit mask recording which of the three piles is still tight (equal so far to the prefix of \(N-1\)); a tight pile may not exceed the corresponding bit of \(N-1\), and stays tight only while it matches. Summing the surviving counts over all \(\beta\) gives \(C(N)\); the code checks the published value \(C(10)=123\) and cross-checks the DP against the triple loop for all \(n\le20\).

The meta-recurrence \(M\)

With the three answers in hand, the seeds are \(M(0)=I(1000)\), \(M(1)=X(1000)\), \(M(2)=C(1000)\), and

$$M(k)\equiv M(k-1)\,M(k-2)\,M(k-3)\pmod{p},\qquad p=10^9+7.$$

Because every term is taken modulo the prime \(p\), each step is just two modular multiplications, and reaching \(k=1000\) costs only about a thousand multiplications. The code slides a window of the last three values forward, reducing modulo \(p\) at each step. The intermediate checkpoint \(M(4)\equiv457587170\) guards the chain, and the final output is \(M(1000)\bmod p\).

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. Helper routines parity_sign (population-count parity via repeated \(v \mathbin{\&}(v-1)\)), bit_count, and highest_bit provide the bit utilities.

parity_and_candidate sweeps \(1\le v\le n\), accumulating for each bit the total \(m_k\) and the signed parity discrepancy \(s_k\); it returns both \(U(n)=\sum2^k\lfloor m_k^2/4\rfloor\) and the parity-partition value \(\sum2^k(m_k^2-s_k^2)/4\). max_and_value asserts these are equal, which is the runtime certificate that the parity partition is optimal, and returns \(I(n)\). brute_max_and verifies \(I(10)=50\) by trying all \(2^{10}\) partitions.

max_xor_sum tabulates the squares, builds every directed edge \((u^2\oplus v^2,\,u,\,v)\), sorts by weight, and runs the batched longest-increasing-weight DP described above, returning \(X(n)\).

count_unreachable_nim runs the digit DP: an outer loop over the top bit \(\beta\), an inner descent over bits maintaining the \(8\)-state tightness mask, applying the "XOR to zero above \(\beta\)", "all ones at \(\beta\)", and "free below \(\beta\)" rules together with the \(\le N-1\) bound. brute_unreachable_nim recomputes \(C(n)\) directly for the cross-check.

mul_mod multiplies modulo \(p\) (the C++ version widens to \(128\) bits; Java keeps the product inside \(64\) bits because both factors are already \(\lt p\)); meta_value iterates the triple-product recurrence. run_checkpoints asserts \(I(10)=50\), \(X(4)=71\), \(X(10)=702\), \(C(n)=\)brute for \(n\le20\), and \(C(10)=123\); main then verifies \(M(4)\equiv457587170\) before printing \(M(1000)\bmod p\).

Complexity Analysis

\(I(n)\): tabulating the bit totals costs \(O(n\log n)\) (each of \(n\) integers contributes to \(O(\log n)\) bits), and combining them is \(O(\log n)\); memory is \(O(\log n)\).

\(X(N)\): the graph has \(\Theta(N^2)\) directed edges, so building and sorting them dominates at \(O(N^2\log N)\) time and \(O(N^2)\) memory. This is the most expensive stage; for \(N=1000\) it is on the order of a million edges, completed in well under a second.

\(C(N)\): the digit DP has \(O(\log N)\) choices of \(\beta\), each an \(O(\log N)\) descent over a constant \(8\times 8\) state space, so \(O(\log^2 N)\) time and \(O(1)\) memory.

Meta-recurrence: \(O(k)\) modular multiplications, i.e. \(O(1000)\) here. The overall running time is therefore governed by the \(\Theta(N^2\log N)\) of the Max-Xor stage.

Footnotes and References

1. Problem page: Project Euler 1000
2. Maximum cut: Wikipedia - Maximum cut
3. Bitwise operation (AND / XOR): Wikipedia - Bitwise operation
4. Hamming weight (population count): Wikipedia - Hamming weight
5. Nim and the Bouton / Sprague–Grundy theory: Wikipedia - Nim
6. Longest path problem (DAG / edge ordering): Wikipedia - Longest path problem
7. Modular arithmetic: Wikipedia - Modular arithmetic