Problem 710

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 > 42$ such that $t (n)$ is divisible by one million.

一百万名用户

2020年4月5日星期日，欧拉计划的用户突破了一百万人。我们设计了本题以纪念这一里程碑。感谢各位参与欧拉计划！

将 $6$ 写成一个回文数组的元素之和，共有八种不同的方式：
$(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)$

如果一个回文数组中至少有一个元素 $2$ ，则称之为二回数组。注意数组的元素并未被限定为一位数，例如， $(3, 2, 13, 6, 13, 2, 3)$ 也是一个合法的二回数组。

记 $t (n)$ 为元素之和为 $n$ 的二回数组的数目，可以看出 $t (6) = 4$ ：
$(1, 1, 2, 1, 1), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 2)$

类似地， $t (20) = 824$ 。

在寻找生命、宇宙以及任何事情的终极答案的过程中，我们发现 $t (42) = 1999923$ ，这恰好是第一个超过一百万的 $t (n)$ 。

你的新挑战是，寻找生命、宇宙以及任何事情的“最终极”答案：在 $n > 42$ 中，找出最小的使得 $t (n)$ 被一百万整除的数 $n$ 。