Project Euler problem 943 (May 2025)

A naive T in Python is:

from collections import deque

def T(a: int, b: int, N: int) -> int:
    total = a
    q = deque([a] * (a - 1))
    is_a = False
    for i in range(N - 1):
        cur = q.popleft()
        total += cur
        q.extend([a if is_a else b] * cur)
        is_a = not is_a
    return total

assert T(2, 3, 10) == 25
assert T(4, 2, 10**4) == 30004
assert T(5, 8, 10**6) == 6499871

which passes the tests, but takes half a second on PyPy. So clearly it is not going to work for 22332223332233 which has 14 digits.

Maybe if T is optimized enough, then we can just bruteforce over the ~40k possible sum ranges 2 to 223. 1 second would mean 14 hours to do them all, so bruteforce but doable. Otherwise another optimization step may be needed at that level as well: one wonders if multiple sums can be factored out, or if the modularity can of the answer can help in a meaningful way. The first solver was ecnerwala using C/C++ in 1 hour, so there must be another insight missing, unless they have access to a supercomputer.

The first idea that comes to mind to try and optimize T is that this is a dynamic programming, but then the question is what is the recurrence relation.

The sequence appears to be a generalization of the Kolakoski sequence but to numbers other than 1 and 2.

maths-people.anu.edu.au/~brent/pd/Kolakoski-ACCMCC.pdf "A fast algorithm for the Kolakoski sequence" might provide the solution, the paper says:

It is conjectured that the algorithm runs in time $O (n^{α})$ and space $O (n^{α})$ , where $α = l o g (2) / l o g (3) \approx 0.631$

and provides exactly a recurrence relation and a dynamic programming approach.

www.reddit.com/r/dailyprogrammer/comments/8df7sm/20180419_challenge_357_intermediate_kolakoski/ might offer some reference implementations. It references a longer slide by Brent: maths-people.anu.edu.au/~brent/pd/Kolakoski-UNSW.pdf

www.reddit.com/r/algorithms/comments/8cv3se/kolakoski_sequence/ asks for an implementation but no one gave anything. Dupe question: math.stackexchange.com/questions/2740997/kolakoski-sequence contains an answer with Python and Rust code but just for the original 1,2 case.

github.com/runbobby/Kolakoski has some C++ code but it is not well documented so it's not immediately easy to understand what it actually does. It does appear to consider the m n case however.

Announcements:

Project Euler problem 943 (May 2025)

 Ancestors (12)