Project Euler Problem 710

Solution

Answer: 1275000

Let

$P(n)$ = number of palindromic tuples summing to $n$,
$a(n)$ = number of palindromic tuples summing to $n$ that do not contain a $2$,
$t(n)$ = number of twopals.

Then

$$t(n)=P(n)-a(n).$$

For palindromic compositions, the left half determines the whole tuple, so

$$P(n)=2^{\lfloor n/2 \rfloor}.$$

The sequence $a(n)$ satisfies the recurrence

$$a(n)=a(n-2)+a(n-3),$$

with initial values

$$a(1)=1,\quad a(2)=1,\quad a(3)=2.$$

Therefore,

$$t(n)=2^{\lfloor n/2 \rfloor}-a(n).$$

We now compute $t(n)\bmod 10^6$ until it becomes $0$ for the first time with $n>42$.

MOD = 10**6

# a[n] = number of palindromic sums of n with no element equal to 2
a = [0, 1, 1, 2]   # indices 0..3

n = 3

while True:
    n += 1

    # recurrence: a(n) = a(n-2) + a(n-3)
    a.append((a[n - 2] + a[n - 3]) % MOD)

    # total palindromic sums = 2^(floor(n/2))
    total = pow(2, n // 2, MOD)

    # twopals
    t = (total - a[n]) % MOD

    if n > 42 and t == 0:
        print(n)
        break

Walkthrough

a[n] stores the number of palindromic sums avoiding the number 2.
We only keep values modulo $10^6$, because divisibility by one million is all that matters.
pow(2, n // 2, MOD) computes $2^{\lfloor n/2\rfloor}\bmod 10^6$.
We test each $n>42$ until $t(n)\equiv 0 \pmod{10^6}$.

Verification

The formula reproduces the values given in the problem:

$t(20)=824$
$t(42)=1999923$

and the first $n>42$ with

$$t(n)\equiv 0 \pmod{10^6}$$

is:

Answer: 1275000