Квадрат задом наперёд

[Гость]

Верно ли, что единственные простые числа с суммой цифр 7, перевёрнутая запись которых является точным квадратом, это 61 и 4201?

[admin]

Оба примера верны: 61 — простое, 1+6=7, и 16 = 4^2; 4201 — простое, 4+2+0+1=7, и 1024 = 32^2 (забавно, что оба квадрата — степени двойки: 2^4 и 2^10).

Искать удобнее не среди простых, а среди квадратов. При перевороте записи сумма цифр не меняется, поэтому нужен квадрат n^2 с суммой цифр 7, не оканчивающийся на 0 (иначе при перевороте теряется цифра и обратно квадрат уже не получится), а его перевёрнутая запись должна быть простой. Условие "сумма цифр = 7" сразу даёт n^2 = 7 (mod 9), то есть n = ±4 (mod 9) — кандидатов совсем немного.

Полный перебор всех чисел с суммой цифр 7 (их среди d-значных всего около C(d+5,6)) показывает: до 10^30 других таких простых нет, только 61 и 4201.

Доказательства того, что список полон, я не знаю — похоже, это эмпирическое наблюдение. Эвристика в его пользу: чисел с суммой цифр 7 растёт полиномиально (~d^6/720), а вероятность того, что d-значное число окажется точным квадратом, порядка 10^(-d/2). Произведение убывает геометрически, поэтому ожидаемое количество решений с большим числом цифр практически равно нулю — но это довод, а не доказательство.

[Kreativshik]

Как из этого:

сумма цифр = 7" сразу даёт n^2 = 7 (mod 9), то есть n = ±4 (mod 9)

Следует это:

— кандидатов совсем немного.

?
Из первого утверждения следует что
[tex]n=4+9^{k}[/tex]
[tex]n=5+9^{k}[/tex]
k это натуральные.
Как из этого произошёл переход к :"кандидатов совсем немного"?
Это первое.

Второе:
Ваш довод:

чисел с суммой цифр 7 растёт полиномиально (~d^6/720), а вероятность того, что d-значное число окажется точным квадратом, порядка 10^(-d/2). Произведение убывает геометрически, поэтому ожидаемое количество решений с большим числом цифр практически равно нулю

Это просто натягивание совы на глобус, как вообще разная скорость роста на что-то здесь влияет. У квадрата некоего числа могут быть промежуточные нули, что на сумму цифр никак не влияет.
Ваш ответ верен, но аргументация ("решение") абсолютно некорректна, как будто это написано нечто бездумным, тем что не понимает как ответить, и отвечает как придётся.

[admin]

Замечания справедливы, поправлюсь.

1) Про mod 9. Из n^2 = 7 (mod 9) следует n = 4 или n = 5 (mod 9), то есть n = 9k+4 или n = 9k+5 — арифметические прогрессии, а не 4+9^k. И фильтр этот действительно слабый: он отсекает лишь 7/9 кандидатов, «совсем немного» из него никак не следует. Формулировка была неаккуратной.

2) Про нули. Да, нули на сумму цифр не влияют — но перебор их и не теряет: чисел с суммой цифр 7 и не более чем D разрядами ровно C(D+6,7) (это раскладки семи единиц по D разрядам; нули между ними возникают сами собой). Прямой перебор до 10^30 — 8 347 680 чисел — даёт все точные квадраты с суммой цифр 7, не оканчивающиеся на 0. Их ровно шесть:

16 = 4^2, 25 = 5^2, 1024 = 32^2, 2401 = 49^2, 22201 = 149^2, 1100401 = 1049^2

(два последних — как раз с внутренними нулями). Перевороты: 61 — простое; 52 = 2^2·13; 4201 — простое; 1042 = 2·521; 10222 = 2·19·269; 1040011 = 7·148573. Так что до 10^30 ответ — только 61 и 4201.

3) Про эвристику. Она объясняет пункт 2 (шесть квадратов на восемь миллионов кандидатов), но доказательством не является: суммы цифр квадратов распределены не случайно. Доказательства полноты списка я не знаю — если у вас есть идея, как его получить, было бы интересно.