Факторизация чисел, десятичная запись которых состоит из n единиц
До сих пор мы изучали быстродействие функции FactorInteger на аргументах, близких к 2n. В двоичной системе счисления запись таких чисел содержит много нулей или единиц подряд. Число Мерсенна Mn, например, записывается n единицами, а число 2n +1 – двумя единицами, между которыми стоит n-1 нуль (рассматриваем случай n > 0). Поэтому может показаться, что функция FactorInteger столь эффективна лишь для чисел, которые имеют специальный вид в двоичной системе счисления. Поэтому давайте изучим возможности этой функции по факторизации больших чисел видов, более случайных с точки зрения теории чисел. Попытаемся разложить, например, числа, десятичная запись которых представляет собой повторение одной и той же цифры л раз. Конечно, если n =1, то эта цифра повторяется только один раз, и вопрос о разложении решается в уме.
С другой стороны, даже если n> 1, то, разделив такое число на ту цифру, которая повторяется n раз, получим число, десятичная запись которого состоит из л единиц. Так что для факторизации чисел такого вида достаточно иметь таблицу разложения чисел, десятичная запись которых состоит из n единиц. Обозначим э то число через 1n. Как задать такое число? Как легко видеть, число, десятичная запись которого состоит из n девяток, равно 10n -1. Разделив это число на 9, получим число, десятичная запись которого состоит из л единиц: (10n -1)/9. Таким образом, мы убедились, что:
(10n -1)/9= 1n= 111……………………….111 ("единиц).
Заметим сразу, что такие числа могут быть простыми лишь в том случае, если количество единиц n в записи такого числа – простое. Действительно, если n = m k, то такое число делится как на число, состоящее из т единиц, так и на число, состоящее из k единиц. Короче говоря, от m| n › 1m | 1n. (Убедиться в этом очень легко, мысленно выполнив деление "столбиком".)
Теперь несложно написать нужную нам программу.
Do[Print[n, ":", FactorInteger[(10 ^ n - 1) / 9]], {n, 70}]В пределах таблицы простых чисел совсем немного, они получаются лишь при n = 2, 19 и 23. Поэтому при всех четных n число 1 имеет 11 в качестве простого множителя. Несколько сложнее увидеть, что 3k |n › 3k | 1n. (Например, все числа вида 13m делятся на 3, это следует из школьного признака делимости на 3. Аналогично обстоит дело и с числами вида 19m.) Это следует из того, что 3k |1k. Как видим, используя таблицу факторизации чисел вида 1n, составленную с помощью простой программы, совсем несложно подметить простейшие закономерности в разложении данных чисел.