Задача 1.3. Палиндром, кратный 2¹⁴

Какое число ищем и почему не перебором

Сначала найдём делитель. $2^7=128$, а $2^{14}$ — это семь двоек, умноженные ещё на семь двоек. Поэтому

Нужно натуральное число, которое делится на $16384$ и читается одинаково слева направо и справа налево. Такие числа называют палиндромами: например, $7$, $121$, $4004$.

Можно выписывать кратные $16384$ подряд: $16384$, $32768$, $49152$, $65536$, $81920$, … В этих примерах симметрии нет. Продолжать вручную можно долго, и пока непонятно, где остановиться.

В условии сказано «найдите какое-нибудь»: годится любой пример, даже очень длинный. Поэтому не будем искать наугад, а построим число сами — так, чтобы оба условия выполнялись сразу. Для этого сначала поймём, от каких цифр зависит делимость на $16384$.

Делимость на 2, 4, 8, … решают последние цифры

Вспомним знакомые признаки. Число делится на $2$, если его последняя цифра чётная, и на $4$ — если две последние цифры образуют число, которое делится на $4$. Почему хватает последних цифр? Разрежем число перед ними. Например, для делимости на $8$ отрежем три последние цифры:

Первое слагаемое делится на $8$ при любой передней части: ведь $1000=8\cdot125$. Значит, всё решает второе слагаемое. А $384=8\cdot48$ делится на $8$ — поэтому и всё число делится на $8$.

Для $2^{14}$ всё устроено так же. Число $10^{14}$ — это четырнадцать десяток, а каждая десятка равна $2\cdot5$. Соберём отдельно четырнадцать двоек и четырнадцать пятёрок:

Разрежем любое число перед его последними $14$ цифрами: оно равно «передняя часть${}\cdot10^{14}$» плюс число из последних $14$ цифр. Первое слагаемое всегда делится на $16384$. Значит, делится ли число на $16384$, решают только его последние $14$ цифр: если число из них делится на $16384$, делится и всё число. А если не делится, то не делится и всё число: иначе число из последних цифр — разность всего числа и первого слагаемого — тоже делилось бы на $16384$. Нули в начале этих цифр можно не писать: $00000000016384$ — это просто $16384$.

Почему не подошло 4836116384

Вернёмся к первой попытке: к $16384$ приписали слева его цифры задом наперёд и получили палиндром $4836116384$. Он кончается на $16384$, и кажется, что делиться должен. Но смотреть надо на все последние $14$ цифр, а в этом числе всего $10$ цифр. Так что в эти $14$ мест попадает и зеркальная часть $48361$ (недостающие места слева заполняем нулями).

Разрежем число перед последними пятью цифрами:

Второе слагаемое — это $2^{14}$. А в первом $100000=2^5\cdot5^5=32\cdot3125$, поэтому первое слагаемое равно $32\cdot(48361\cdot3125)$. В скобках нечётное число: оба множителя нечётные. Значит, первое слагаемое делится на $32$, но не делится на $64$.

Тогда и всё число на $64$ не делится. Иначе первое слагаемое — разность всего числа и $16384$ — тоже делилось бы на $64$, ведь $16384=64\cdot256$. Итак, $4836116384$ делится на $2$ только пять раз подряд: $4836116384=32\cdot151128637$, а $151128637$ нечётное. До четырнадцати двоек далеко.

Вывод: зеркальную часть надо отодвинуть влево так, чтобы она не попала в последние $14$ цифр.

Отодвигаем зеркальную часть нулями

Вставим между $48361$ и $16384$ несколько нулей. Число останется палиндромом: слева по-прежнему $16384$ задом наперёд, а ряд нулей одинаково читается с обеих сторон.

Сколько нулей нужно? Добьёмся, чтобы в последние $14$ цифр попали только нули и $16384$. Число $16384$ занимает $5$ мест, а остальные $14-5=9$ мест займут нули:

В этом числе $19$ цифр: $48361$, девять нулей и $16384$. Его последние $14$ цифр — $00000000016384$, то есть число $16384$, а оно делится на $16384$. По шагу 2 и всё число делится на $16384$. С восемью нулями места не хватило бы ровно на одну цифру: в последние $14$ цифр попала бы единица из $48361$.

Проверим и прямым делением. Наше число — это $48361\cdot10^{14}+16384$. Первое слагаемое равно $16384\cdot(48361\cdot6103515625)$, второе — $16384\cdot1$. Значит, всё число равно $16384$, умноженному на $48361\cdot6103515625+1=295172119140626$. Итак, $4836100000000016384=16384\cdot295172119140626$.