Шестизначный палиндром

698 896 = 836².

Ответ можно получить довольно быстро примерно следующим образом. Во-первых, заметим, что точные квадраты могут оканчиваться только пятью цифрами (ноль на конце мы не рассматриваем, поскольку искомое число должно быть палиндромом):

• Если число оканчивается на 1 или 9, то его квадрат оканчивается на 1.
• Если число оканчивается на 2 или 8, то его квадрат оканчивается на 4.
• Если число оканчивается на 5, то его квадрат оканчивается на 5.
• Если число оканчивается на 4 или 6, то его квадрат оканчивается на 6.
• Если число оканчивается на 3 или 7, то его квадрат оканчивается на 9.

Во-вторых, корень из искомого числа должен быть трёхзначным числом (назовём этот корень x). При этом:

1. Если 317 ≤ x < 448, то x² начинается с 1.
2. Если 448 ≤ x < 548, то x² начинается с 2.
3. Если 548 ≤ x < 633, то x² начинается с 3.
4. Если 633 ≤ x < 708, то x² начинается с 4.
5. Если 708 ≤ x < 775, то x² начинается с 5.
6. Если 775 ≤ x < 837, то x² начинается с 6.
7. Если 837 ≤ x < 895, то x² начинается с 7.
8. Если 895 ≤ x < 949, то x² начинается с 8.
9. Если 949 ≤ x < 999, то x² начинается с 9.

Поскольку искомое число является палиндромом, то из этого списка нужно проверить лишь числа, подпадающие под пункты 1, 4, 5, 6 и 9. При этом для первого пункта проверяем только числа, заканчивающиеся на 1 или 9, для четвёртого — на 2 или 8, для пятого — на 5, для шестого — на 4 или 6, для девятого — на 3 или 7. Получается следующий список чисел, которые нужно просто честно проверить: