Переворачивающиеся при умножении числа24.02.2024 16:30

Здравствуйте!

Расскажу о серии задач, которая случайно возникла в процессе решения другой задачи. Мне на глаза попалось равенство:

81×27 = 2187

— Интересно, — подумал я. — А бывают ли ещё такие числа, чтобы цифры слева и справа повторялись?

Всего нашлось 7 двузначных пар, включая одну с теми же цифрами:

15×93 = 1395
21×60 = 1260
21×87 = 1827
27×81 = 2187
30×51 = 1530
35×41 = 1435
80×86 = 6880

Затем я решил посчитать, сколько пар n-значных чисел удовлетворяют этому свойству: набор цифр и количество повторений каждой из них слева и справа от знака «равно» совпадают. Заметим, что произведение двух n-значных чисел может иметь как 2n-1, так и 2n знаков. (Можно вычислить, что доля пар n-значных чисел, для которых в произведении 2n знаков составляет примерно 82,7%).

Для небольших значений n я получил результат с помощью программы на Питоне. Алгоритм очень простой — берём все пары чисел, переводим в десятичное представление и сравниваем наборы цифр в паре чисел и в их произведении. На вычисление количества пар для n=5 ушло более 3 часов. Переписав на С++, на вычисление ушло 25 минут, но т.к. следующее значение требует рассмотрение в 100 раз больше пар, то ждать так долго не хотелось.

Задумавшись о том, можно ли посчитать количество таких пар для бóльших чисел n, я придумал усовершенствованный алгоритм, который позволил получить значение для n=6: 4505706 за 62 минуты. Для n больше 6 уже требуется очень много памяти.

Если нанести полученные значения на график, получим вот такую картинку:

Было бы любопытно узнать, как график ведёт себя на бесконечности, — вероятно, есть какая-то асимптота.

Потом я задумался, а какие из всех этих чисел наиболее интересные. Например, существуют ли пары одинаковых чисел, обладающие описанным выше свойством. Оказывается, для n=5 и n=6 существуют:

72576×72576 = 5267275776
406512×406512 = 165252006144
415278×415278 = 172455817284
494462×494462 = 244492669444
603297×603297 = 363967270209
725760×725760 = 526727577600

Также возник вопрос, а может ли быть что-то вроде abc*def = abcdef. Очевидный ответ: нет, поскольку def должно в данном случае превышать 1000 (делим правую часть на abc).

Тогда резонный вопрос, а может ли быть что-то вроде abc*def = fedcba, то есть в произведении цифры идут в обратном порядке. (Отметим, что в данном случае порядок множителей имеет значение.) Будем называть такие числа переворачивающимися парами.

И оказывается, да! Такие случаи бывают.

При n < 6 – нет пар

n=6
218252×837281 = 182738252812

По этому поводу я придумал алгоритм побыстрее для решения конкретно этой задачи.

n=7 — нет пар

n=8
43275098×77535533 = 3355357789057234
47208027×56843862 = 2683486572080274
83321918×23007191 = 1917003281912338

n=9 — нет пар

n=10
6523664043×4475469192 = 29196457443404663256
7990749971×8794337207 = 70273349781799470997

n=11 — нет пар

n=12 — нет пар (вычисления длились 5 часов на 11-ядрах процессора)

Видна одна закономерность: для нечётных n не нашлось ни одной пары. Интересно, таких пар вообще не существует, или просто их число существенно меньше.

Неудачная идея доказательства

У меня было подозрение, что это как-то связано с признаком деления, например на 11: остаток от деления десятичного числа на 11 равен остатку от деления на 11 знакопеременной суммы цифр. Для чётных n и переворачивающейся пары с остатками от деления на 11 (x, y) получаем:

x*y mod 11 = (x+y) mod 11

Для нечётных n получаем:

x*y mod 11 = (x-y) mod 11

Однако эти равенства приводят к одинаковому количеству пар остатков от деления на 11 — по 10 пар (из 121 варианта) для чётных и нечётных n.

Кстати, из признака деления на 3 получаем, что x mod 3!= 1 и y mod 3!= 1.

Признак деления на 9 отсекает ещё часть вариантов — реализуются 6 из 81 варианта.

Другие системы счисления

Если посмотреть на системы счисления с другими основаниями M, то в некоторых из них существуют переворачивающиеся пары для нечётных n.

Hidden text

Также интересны случаи, когда в левой и правой части каждая цифра используется по 1 разу. И наиболее замечательны случаи, когда все цифры от 0 до 9 используются (n=5). Таких случаев я насчитал 1289. Будем называть такие числа полными парами.

Было бы интересно найти пару чисел, пусть даже не в десятичной системе счисления, которая одновременно является переворачивающейся и полной. (В случае системы счисления с основанием M, при n=M/2, в паре чисел и в произведении все «цифры» от 0 до M-1 должны встретиться по 1 разу.). Кажется, что таких пар вообще не существует. Ведь примерная вероятность оценивается в {число переворачивающихся пар} * {число полных пар} / {число потенциальных пар}2, что при M=12 (n=6) оценивается порядка 5×10–20 при условии наличия одной переворачивающейся пары (в реальности таких пар не нашлось). И вроде как эта вероятность с ростом M убывает, поэтому, возможно, таких пар вообще не существует.

Кстати, если искать пары чисел состоящих из различного числа цифр, то одну переворачивающуюся полную пару я всё-таки нашёл:

5×20341 = 143025 (система счисления с основанием M=6)

Всё выше изложенное жёстко связано с системой счисления, поэтому не представляет настолько большого интереса, как глобальные задачи теории чисел, такие как проблема Гольдбаха, гипотеза Каталана, теорема Лежандра о сумме четырёх квадратов, гипотеза о разложении в сумму трёх кубов и др. Хотя кто знает, может быть какое-то практическое применение, кроме ребусов, всё же найдётся.

P.S. Если нужно, код выложу чуть позже.

© Habrahabr.ru