Алгебра и пакет Mathematica 5
Факторизация чисел, десятичная запись которых состоит из n единиц
До сих пор мы изучали быстродействие функции FactorInteger на аргументах, близких к 2n. В двоичной системе счисления запись таких чисел содержит много нулей или единиц подряд. Число Мерсенна
Mn, например, записывается п единицами, а число 2n+1 — двумя единицами, между которыми стоит л-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, составленную с помощью простой программы, совсем несложно подметить простейшие закономерности в разложении данных чисел.
