Detailed mathematical approach

Problem Summary

Problem 949 assigns a recursive left-versus-right position to every binary word \(w\) of length \(n\). The one-bit words are the starting numbers \(0\mapsto +1\) and \(1\mapsto -1\). For longer words, the recurrence treats proper suffixes as options on one side of the game and proper prefixes as options on the other. The implementations do not keep the full game tree; instead, they compute a signed score \(u(w)\) together with a cold/non-cold classification.

The target quantity is \(G(20,7)\bmod 1001001011\). Direct enumeration is impossible: there are \(2^{20}\) words of length 20 and therefore \((2^{20})^7\) ordered 7-tuples. The successful strategy is to evaluate each single word once, compress equal scores into histograms, and then count tuples by convolving those histograms.

Mathematical Approach

All three implementations follow the same two-stage plan. First they solve the single-word recurrence for every binary string up to length \(n\). Then they turn the multiset of resulting scores into a counting problem on discrete distributions.

The recursive bounds from shorter words

For a word \(w\) of length \(\ell\ge 2\), let \(\mathrm{Suf}(w)\) be the set of proper suffixes of \(w\), and let \(\mathrm{Pre}(w)\) be the set of proper prefixes. Every such option is shorter than \(w\), so a bottom-up dynamic program by increasing length is valid.

Each shorter word \(t\) carries two stored endpoints \(u(t)\) and \(d(t)\). The new raw bounds are

$u_{\mathrm{raw}}(w)=\max_{t\in\mathrm{Suf}(w)} d(t),\qquad d_{\mathrm{raw}}(w)=\min_{t\in\mathrm{Pre}(w)} u(t).$

The one-bit layer is initialized as

$u(0)=d(0)=+1,\qquad u(1)=d(1)=-1,$

after a global scaling that will be described next. Those formulas are the real core of the problem: every later value is forced by the best suffix-side bound and the best prefix-side bound coming from shorter words.

Why a dyadic grid is enough

The solutions represent every value on the dyadic grid with denominator dividing \(2^n\). Instead of storing a rational number directly, they multiply everything by \(2^n\) and store integers. A dyadic number \(p/2^m\) is therefore encoded as \(p\,2^{\,n-m}\).

This choice makes all comparisons exact and keeps the recurrence purely integer-based. The floor and ceiling operations that appear when searching for a new value become simple divisions by powers of two. Because the recursion depth is at most \(n\), this dyadic representation is sufficient for every value created by the algorithm.

Cold states and the canonical value inside a strict gap

If the raw bounds satisfy

$u_{\mathrm{raw}}(w)\lt d_{\mathrm{raw}}(w),$

then the word falls into the cold bucket. In that case the implementations choose a single canonical dyadic number \(x\) strictly between those two bounds and set

$u(w)=d(w)=x.$

The chosen \(x\) is the simplest dyadic in the open interval \((u_{\mathrm{raw}}(w),d_{\mathrm{raw}}(w))\): the search tries coarse denominators first, so the first successful scale gives the smallest denominator; within that scale it prefers \(0\) if available, otherwise the admissible numerator closest to \(0\); and for non-integer dyadics it keeps the numerator odd so the representation is already reduced.

If there is no strict gap, the state is kept as non-cold and the implementations simply store

$u(w)=u_{\mathrm{raw}}(w),\qquad d(w)=d_{\mathrm{raw}}(w).$

This distinction matters later: only the cold states collapse to one exact number, while the non-cold states retain only their left-end score \(u(w)\) for the final count.

Histogram compression of the final layer

Once all words of length \(n\) have been processed, only two pieces of information are needed for each word: its stored score \(u(w)\) and whether it was cold. The implementations therefore compress the full layer into two histograms,

$H_{\mathrm{all}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\},$

$H_{\mathrm{cold}}(x)=\#\{w\in\{0,1\}^n:u(w)=x\text{ and }w\text{ is cold}\}.$

This is the step that removes the exponential blow-up in \(k\). Many different words share the same score, so the tuple problem can be solved on score frequencies instead of on individual words.

Turning \(k\)-tuples into convolution counts

For odd \(k\), set

$a=\left\lfloor\frac{k}{2}\right\rfloor,\qquad b=k-a.$

Let \(D_a\) and \(D_b\) be the \(a\)-fold and \(b\)-fold convolutions of \(H_{\mathrm{all}}\), and let \(C_a\) and \(C_b\) be the corresponding convolution powers of \(H_{\mathrm{cold}}\). Thus \(D_a(s)\) is the number of ordered \(a\)-tuples of length-\(n\) words whose stored scores sum to \(s\), and similarly for the other distributions.

The answer is then

$G(n,k)=\sum_{x+y\lt 0} D_a(x)D_b(y)+\sum_x C_a(x)C_b(-x)\pmod{1001001011}.$

The first term counts all ordered \(k\)-tuples whose total stored score is negative. The second term adds the exact-zero cases, but only when every component comes from the cold histogram. Splitting the tuple into an \(a\)-part and a \(b\)-part is only a counting device; it preserves the total sum because \(a+b=k\).

Worked example: why \(G(2,3)=14\)

For \(n=2\), the global scale is \(2^2=4\). The four binary words are \(00,01,10,11\).

For \(00\), both the only proper suffix and the only proper prefix are \(0\), so the stored score is \(+4\). For \(11\), the same reasoning gives \(-4\). For \(01\), the suffix contributes \(-4\) and the prefix contributes \(+4\), so there is a strict gap and the simplest dyadic between them is \(0\); this word is cold. For \(10\), the raw bounds are reversed, so the word is non-cold and keeps stored score \(+4\).

After dividing by the common scale, the multiset of scores is therefore

$\{1,0,1,-1\},$

and the only cold word has score \(0\). Now count ordered triples. Negative totals occur in exactly four patterns:

$(-1,-1,-1)\quad\text{gives }1,$

$(-1,-1,0)\quad\text{gives }3,$

$(-1,0,0)\quad\text{gives }3,$

$(-1,-1,+1)\quad\text{gives }3\cdot 2=6,$

because the \(+1\) entry can be chosen from two distinct words. Altogether this gives \(1+3+3+6=13\) negative triples. The only cold zero-sum triple is \((01,01,01)\), contributing one more case, so

$G(2,3)=13+1=14,$

which matches the built-in check used by the C++ implementation.

How the Code Works

Bottom-up evaluation of all binary words

The implementations enumerate all non-empty binary words of lengths \(1,2,\dots,n\) level by level. For each final-layer word they inspect every proper suffix length and every proper prefix length, form the two raw bounds, and either collapse the state to one canonical dyadic number or keep the raw endpoints. The C++ version can parallelize the loop over words of a fixed length with OpenMP; the Python and Java versions execute the same recurrence serially.

Building the two score histograms

After the layer of length \(n\) is complete, the implementations no longer need the full prefix/suffix structure. They sweep once over the final scores, count how often each score appears, and separately count how often it appears among cold words. This produces the all-words histogram and the cold-only histogram described above.

Repeated convolutions and the final count

Because \(k=7\) is small, the implementations build the required convolution powers by repeated hash-map convolution rather than by FFT-style machinery. To count negative totals, one of the two resulting supports is sorted and prefix-summed, so every score from the other side can add all compatible partners with a single binary search. Exact-zero cold totals are even simpler: they are found by matching a score with its negation in the opposite cold distribution.

Complexity Analysis

The dynamic program processes every binary word of length at most \(n\), so it visits \((2^{n+1}-2)\) states in total. For each state it scans all proper suffix lengths and all proper prefix lengths, and in the cold case it may search through up to \(n\) dyadic scales. This gives overall time \(O(n2^n)\) and memory \(O(2^n)\) for the recurrence phase.

If \(M\) is the largest support size among the intermediate score distributions, each hash-map convolution costs \(O(M^2)\) in the naive representation, so the convolution phase is \(O(kM^2)\). The negative-total count adds a sorting step \(O(M\log M)\). The crucial point is that the algorithm depends on the number of distinct reachable scores, not on the full tuple space \((2^n)^k\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=949
2. Combinatorial game theory: Wikipedia - Combinatorial game theory
3. Partisan game: Wikipedia - Partisan game
4. Dyadic rational: Wikipedia - Dyadic rational
5. Convolution: Wikipedia - Convolution