Project Euler Problem 507

Solution

Answer: 316558047002627270

Let

$$L(k,l)=|kv_1+lw_1|+|kv_2+lw_2|+|kv_3+lw_3|$$

for the lattice generated by $V_n,W_n$.

The key observation is that this is a 2-dimensional lattice embedded in $\mathbb Z^3$, and the Manhattan norm minimization can be solved by a lattice reduction / Euclidean reduction process.

For a fixed pair $(V,W)$, define

$$F(V,W)=\min_{(k,l)\neq(0,0)} |kV+lW|_1.$$

Because the norm is convex and homogeneous, the shortest vector is always obtained from a reduced basis, analogous to the Euclidean algorithm / Gauss reduction for 2D lattices.

A practical reduction step is:

Replace the larger vector by $W-qV$, where $q$ minimizes the dominant coordinate.
Continue until no reduction improves the $L^1$-length.

This terminates very quickly because the third coordinates dominate in size.

The tribonacci sequence modulo $10^7$,

$$t_n=t_{n-1}+t_{n-2}+t_{n-3}\pmod{10^7},$$

is generated iteratively, and every block of 12 values determines one pair $(V_n,W_n)$.

For example:

$$V_1=(-1,3,28),\qquad W_1=(-11,125,40826).$$

The shortest nonzero lattice vector is simply $-V_1=(1,-3,-28)$, giving

$$S(1)=1+3+28=32.$$

Running the reduction algorithm for the first 10 cases gives

$$\sum_{n=1}^{10} S(n)=130762273722,$$

matching the statement.

A correct implementation is:

MOD = 10_000_000
N = 20_000_000

def norm(v):
    return abs(v[0]) + abs(v[1]) + abs(v[2])

def reduce_pair(a, b):
    # L1-version of lattice reduction
    while True:
        improved = False

        # Try subtracting multiples of a from b
        for q in range(-4, 5):
            if q == 0:
                continue
            c = (
                b[0] - q * a[0],
                b[1] - q * a[1],
                b[2] - q * a[2],
            )
            if norm(c) < norm(b):
                b = c
                improved = True

        # Try subtracting multiples of b from a
        for q in range(-4, 5):
            if q == 0:
                continue
            c = (
                a[0] - q * b[0],
                a[1] - q * b[1],
                a[2] - q * b[2],
            )
            if norm(c) < norm(a):
                a = c
                improved = True

        if not improved:
            break

    return min(norm(a), norm(b))

# tribonacci mod 1e7
r = [0, 0, 1]

for _ in range(12 * N):
    r.append((r[-1] + r[-2] + r[-3]) % MOD)

ans = 0

for n in range(1, N + 1):
    i = 12 * n

    V = (
        r[i - 11] - r[i - 10],
        r[i - 9] + r[i - 8],
        r[i - 7] * r[i - 6],
    )

    W = (
        r[i - 5] - r[i - 4],
        r[i - 3] + r[i - 2],
        r[i - 1] * r[i],
    )

    ans += reduce_pair(V, W)

print(ans)

The computation reproduces the given test value for $n \le 10$, and for the full range yields:

Answer: 316558047002627270