= Project Euler problem 943
{c}
{title2=May 2025}
https://projecteuler.net/problem=943
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.
https://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 $α = log(2)/ log(3) \approx 0.631$
and provides exactly a recurrence relation and a <dynamic programming> approach.
https://www.reddit.com/r/dailyprogrammer/comments/8df7sm/20180419_challenge_357_intermediate_kolakoski/ might offer some reference implementations. It references a longer slide by Brent: https://maths-people.anu.edu.au/~brent/pd/Kolakoski-UNSW.pdf
https://www.reddit.com/r/algorithms/comments/8cv3se/kolakoski_sequence/ asks for an implementation but no one gave anything. Dupe question: https://math.stackexchange.com/questions/2740997/kolakoski-sequence contains an answer with Python and Rust code but just for the original 1,2 case.
https://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:
* https://mastodon.social/@cirosantilli/115446059895647190
* https://x.com/cirosantilli/status/1982782344135107043
* https://www.linkedin.com/feed/update/urn:li:activity:7386417197440454658/
Back to article page
