n и n^2 являются палиндромами в двоичной записи

[maxal]

Найдите все такие натуральные числа $n$, что числа $n$ и $n^2$, будучи записанными в двоичной системе счисления, являются палиндромами.

[Руст]

Что значит палиндром?

[ИСН]

Палиндром - значит читается справа налево и слева направо одинаково.
Но...
все? их можно найти все? их так мало?
неужели?
ну-ка, ну-ка...

[Руст]

Тогда число $n=1+2^k+..+2^{m-k}+2^m$. Случай с одной цифрой дает решение $n=1$, с двумя решений нет кроме $n=3$, С тремя цифрами $n=1+2^k+2^{2k}$ уже нет решений.
Если количество цифр больше 3 так же получаем, что решений нет. Отдельно разбираем $k>2$ (очевидно), $k=2$ и $k=1$.

[maxal]

Руст писал(а):

Если количество цифр больше 3 так же получаем, что решений нет. Отдельно разбираем $k>2$ (очевидно)

Как именно? В этом доказательстве вся соль задачи.

[Руст]

Если $k>2$ то $2^m+2^{m-k}+..<2^m(\frac 54)$, соответственно это число меньше $2^{m+1}$ (старшая цифра $2^m$) а расстояние между старшим и последующим разрядом меньше k, в то время как между нижними k: $n^2=1+2^{k+1}+...$.
Так как квадрат меньше $2^{m+2}$ и оканчивается всегда на 001 (по модулю 8 равен 1), то должен быть $n^2=2^{m+1}+2^{m-l}+...+001$. Отсюда легко исключается $k=1$. Более длинно разбирается $k=2$.

[maxal]

Для каких натуральных $b$ количество натуральных чисел $n$, вместе со своими квадратами являющихся палиндромами в $b$-ичной системе счисления, бесконечно?
В частности, является ли $b=3$ таковым?

[Руст]

Начиная с b=3 это верно. Достаточно взять $n=b^k+1$ тогда $n^2=b^{2k}+2b^k+1$ - палиндром.

[maxal]

maxal в сообщении #133388 писал(а):

Найдите все такие натуральные числа $n$, что числа $n$ и $n^2$, будучи записанными в двоичной системе счисления, являются палиндромами.

Задача опубликована под номером 11922 в AMM.