Задача 710
Один миллион участников

Пятого апреля 2020 г., в воскресенье, количество участников ProjectEuler.net впервые превысило один миллион. Чтобы отметить это достижение, мы хотим представить вам эту задачу. Спасибо всем за участие в Project Euler.

Число 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 \gt 42$, такое что $t(n)$ делится на миллион.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net