Project Euler Problem 384

Solution

Answer: 3354706415856332783

Using the recursive structure of the Rudin–Shapiro summatory sequence, one can compute $g(t,c)$ in $O(\log t)$ time.

A fast recursive implementation is:

from __future__ import annotations

def a_adjacent_ones(n: int) -> int:
    return (n & (n >> 1)).bit_count()

def b_rudin_shapiro(n: int) -> int:
    return -1 if (a_adjacent_ones(n) & 1) else 1

def g_index(t: int, c: int) -> int:
    if t == 1:
        return 0

    h = 1 << (t.bit_length() - 1)   # largest power of 2 <= t
    d = t - h

    if d == 0:
        if c <= t // 2:
            return t * t // 4 + g_index(t // 2, c)
        else:
            return t * t // 2 + g_index(t, c - t // 2)

    if c > h:
        return h * h + g_index(2 * h - d, c - h)
    elif c > h - d:
        return h * h + g_index(d, c + d - h)
    elif c <= d:
        return h * h // 2 + g_index(d, c)
    else:
        return h * h // 2 + g_index(2 * h - t, c)

# Fibonacci numbers
F = [1, 1]
for _ in range(2, 46):
    F.append(F[-1] + F[-2])

total = 0
for t in range(2, 46):
    total += g_index(F[t], F[t - 1])

print(total)

The implementation satisfies the given checks:

$g(3,3)=6$
$g(4,2)=7$
$g(54321,12345)=1220847710$

Running the program gives:

$$\sum_{t=2}^{45} GF(t) = 3354706415856332783$$

Answer: 3354706415856332783