One Million Members

On Sunday 5 April 2020 the Project Euler membership first exceeded one million members. We would like to present this problem to celebrate that milestone. Thank you to everyone for being a part of Project Euler.
The number 6 can be written as a palindromic sum in exactly eight different ways:
$$(1, 1, 1, 1, 1, 1), (1, 1, 2, 1, 1), (1, 2, 2, 1), (1, 4, 1), (2, 1, 1, 2), (2, 2, 2), (3, 3), (6)$$

We shall define a twopal to be a palindromic tuple having at least one element with a value of 2. It should also be noted that elements are not restricted to single digits. For example, $(3, 2, 13, 6, 13, 2, 3)$ is a valid twopal.
If we let $t(n)$ be the number of twopals whose elements sum to $n$, then it can be seen that $t(6) = 4$:
$$(1, 1, 2, 1, 1), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 2)$$

Similarly, $t(20) = 824$.
In searching for the answer to the ultimate question of life, the universe, and everything, it can be verified that $t(42) = 1999923$, which happens to be the first value of $t(n)$ that exceeds one million.However, your challenge to the “ultimatest” question of life, the universe, and everything is to find the least value of $n \gt 42$ such that $t(n)$ is divisible by one million.

This problem is a combinatorial problem with number theory. While there isn’t a simple mathematical formula to solve it, we can use Python to find the answer.

Here is a simple Python code that implements the dynamic programming algorithm:

“`python
P = [[0]*30001 for x in range(30001)]
P[0][0] = 1
for pal_len in range(1, 30001):
for total in range(30001):
if pal_len <= total:
P[pal_len][total] = (P[pal_len-1][total-pal_len] + P[pal_len][total-1]) % 10**6
else:
P[pal_len][total] = P[pal_len][total-1]

n = 42
while True:
n += 1
twopal_count = 0
for k in range(2, n//2+1):
twopal_count = (twopal_count + P[k][n-k*2]*2) % 10**6
if twopal_count == 0:
break
print(n)
“`

This Python code measures the number of palindromic tuples ending in k for size n by taking the cumulative sum in an array P[ ][ ] of the previous counts.

Element P[k][n] is calculated as the sum of P[k-1][n-k] (if k ≤ n, i.e., the number n can be achieved with the present k) and P[k][n-1]. Each compute is done modulo 10**6.

In sequence, all k options for palindrome lengths are cycled from 2 to n//2 (as these are the possible starting numbers for a palindrome summing to n) and the counts are added. Please note that these counts are doubled (since they are repeating over the palindrome center).

When twopal_count mod 10**6 equals 0, it means the number of twopals is divisible by one million, and the program will break out of the loop and print n.

Before running such an algorithm, however, be aware that this will be computational intensive and may take quite a bit of time.

As a note, Project Euler problems are meant to be solvable in under 1 minute if the correct approach is taken; brute force methods will not usually be efficient enough to get a solution in a reasonable time.

More Answers: