Detailed mathematical approach

Problem Summary

For each ordered pair \((a,b)\) with \(2 \le a,b \le 223\) and \(a \ne b\), define the generalized Kolakoski sequence \(K_{a,b}=x_1,x_2,\dots\) on the alphabet \(\{a,b\}\). The first term is \(x_1=a\), the symbols in the runs alternate \(a,b,a,b,\dots\), and the run lengths are the sequence itself. The task is to compute

$T(a,b;N)=\sum_{i=1}^{N} x_i$

at the huge index \(N=22332223332233\), then sum \(T(a,b;N)\) over all ordered pairs and report the result modulo \(2233222333\).

A direct construction of the first \(N\) terms is completely infeasible. The solution works because the sequence is self-describing: one level of the sequence tells us how many blocks appear at the next level. The implementations exploit that recursive structure by evaluating large blocks and memoizing complete block summaries.

Mathematical Approach

The central idea is to stop thinking term-by-term and instead summarize recursively generated blocks. For this problem, the right mathematical objects are the run decomposition of \(K_{a,b}\), prefix counts of \(a\) and \(b\), and a state transition that remembers where the alternating run mechanism is currently positioned.

The self-describing run decomposition

Write \(K_{a,b}=x_1,x_2,\dots\), where every \(x_i\) is either \(a\) or \(b\). By definition, the sequence decomposes into maximal runs as

$K_{a,b}= \underbrace{a\cdots a}_{x_1} \underbrace{b\cdots b}_{x_2} \underbrace{a\cdots a}_{x_3} \underbrace{b\cdots b}_{x_4}\cdots.$

So the same symbols play two roles. At the top level they are the values of the sequence, and at the same time they dictate the lengths of the alternating runs. That is the self-describing feature behind the whole algorithm.

Prefix sums reduce to counting symbols

Let \(A_{a,b}(n)\) be the number of \(a\)'s among the first \(n\) terms, and let \(B_{a,b}(n)\) be the number of \(b\)'s. Then

$A_{a,b}(n)+B_{a,b}(n)=n,$

and the weighted prefix sum we need is

$T(a,b;n)=a\,A_{a,b}(n)+b\,B_{a,b}(n).$

Therefore the computational problem is not “generate the whole prefix and add it up”; it is “count how many \(a\)'s and \(b\)'s occur in a huge self-referential prefix.” Once those counts are known, \(T(a,b;n)\) follows immediately.

Depth-\(d\) blocks and the recursive length/count equations

A depth-0 block is one maximal run. Depending on the current state, it emits either \(a\) or \(b\) copies of the current symbol. A depth-1 block is a concatenation of \(a\) or \(b\) depth-0 blocks. More generally, a depth-\(d\) block is a concatenation of \(a\) or \(b\) depth-\((d-1)\) blocks.

For a state \(s\), let

$F_d(s;n)=\bigl(\alpha_d(s;n),\beta_d(s;n),\nu_d(s;n)\bigr)$

denote the summary of the first \(n\) emitted terms of a depth-\(d\) block: \(\alpha_d\) is the number of \(a\)'s produced, \(\beta_d\) is the number of \(b\)'s produced, and \(\nu_d\) is the next state after that prefix. When the whole block is taken, we simply write \(F_d(s)\).

If \(\lambda_d(s)\in\{a,b\}\) is the number of children at depth \(d\), and \(s_1,s_2,\dots\) are the successive child states, then the full block length satisfies

$L_0(s)=\lambda_0(s),\qquad L_d(s)=\sum_{j=1}^{\lambda_d(s)} L_{d-1}(s_j).$

The symbol counts obey the same additive rule:

$\alpha_d(s)=\sum_{j=1}^{\lambda_d(s)} \alpha_{d-1}(s_j),\qquad \beta_d(s)=\sum_{j=1}^{\lambda_d(s)} \beta_{d-1}(s_j).$

If a requested prefix ends in the middle of the last child, only that last child has to be evaluated partially; all earlier children are complete blocks. This is exactly the recurrence used by the implementations.

The state invariant encoded by the implementations

The recursive formulas need a compact way to say what kind of block comes next. The implementation state is a bit vector with a clear invariant. Its least significant bit tells us whether the next emitted symbol at the base level is \(a\) or \(b\). For each recursion level \(r \ge 0\), the bit in position \(r+1\) tells us whether the currently active multiplicity at that level is \(a\) or \(b\).

Mathematically, that state records the frontier of all open recursion levels. Once the state \(s\) and the depth \(d\) are fixed, the entire full block is determined: how many \(a\)'s it produces, how many \(b\)'s it produces, and what the next state is after the block closes. This is why a full block summary depends only on \((s,d)\), which makes memoization correct.

Why a logarithmic number of depths is enough

Because \(a,b \ge 2\), every block has at least 2 children. Hence full block lengths grow at least exponentially:

$L_d(s)\ge 2^{d+1}.$

So some depth \(d=O(\log N)\) must eventually produce a block long enough to cover the first \(N\) terms. The implementations simply increase the depth until the block beginning from the initial state is long enough, then extract the desired prefix from that block.

Worked Example: \(K_{2,3}\)

For \((a,b)=(2,3)\), the sequence begins

$K_{2,3}=2,2,3,3,2,2,2,3,3,3,\dots$

Grouping into runs gives

$22\;33\;222\;333\;\cdots,$

so the run lengths are again \(2,2,3,3,\dots\), exactly the sequence itself. In the first 10 terms there are five 2's and five 3's, therefore

$T(2,3;10)=5\cdot 2+5\cdot 3=25.$

This concrete case appears in the validation logic and is a useful miniature model of the full computation.

From one ordered pair to the full Euler sum

Once one pair \((a,b)\) has been handled, the Project Euler quantity is

$S(N)=\sum_{\substack{2\le a,b\le 223\\ a\ne b}} T(a,b;N)\pmod{2233222333},\qquad N=22332223332233.$

There are \(222 \times 221 = 49062\) ordered pairs. They are independent, so the same mathematical evaluator can be reused for every pair and the contributions can then be added modulo \(2233222333\).

How the Code Works

Evaluating a single pair

For fixed \(a\) and \(b\), the C++, Python, and Java implementations create a block evaluator for \(K_{a,b}\). They test increasing recursion depths until the initial block is long enough to cover \(N\). The returned summary already contains the counts of \(a\) and \(b\) needed for the formula \(T(a,b;N)=aA+bB\).

Memoizing complete blocks

The cache key is the pair “state plus depth”. Each cached entry stores three quantities: the total number of \(a\)'s in the full block, the total number of \(b\)'s in the full block, and the next state after that block ends. A cached entry can be reused only when the remaining prefix budget is large enough to include the whole block. If the budget cuts through the block, the evaluator descends recursively, because a truncated final child changes both the counts and the next state.

Summing over all ordered pairs

After one pair is evaluated, the implementation converts symbol counts into a weighted prefix sum and adds that contribution modulo \(2233222333\). The C++ and Java implementations distribute different \(a\)-values across worker threads, while the Python implementation performs the same pair loop serially. The mathematical core is identical in all three languages.

Complexity Analysis

For a fixed pair \((a,b)\), the running time is controlled by the number of distinct full block states that are actually reached, not by the raw prefix length \(N\). If that number is denoted by \(M_{a,b}\), then the memory usage is \(O(M_{a,b})\), because each reachable memo entry stores one full block summary.

The work attached to each memo entry is bounded by the number of child blocks it needs to inspect, which is at most \(\max(a,b)\le 223\). So a natural description is \(O(\max(a,b)\,M_{a,b})\) time per ordered pair and \(O(M_{a,b})\) memory. The full Euler computation repeats that process for 49062 ordered pairs and accumulates the results modulo \(2233222333\). The essential point is that the algorithm scales with the reachable recursive state space, not with \(N=22332223332233\) itself.

Footnotes and References

1. Problem page: Project Euler 943
2. Kolakoski sequence: Wikipedia - Kolakoski sequence
3. Run-length encoding: Wikipedia - Run-length encoding
4. Memoization: Wikipedia - Memoization