Алгебра и пакет 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, составленную с помощью простой программы, совсем несложно подметить простейшие закономерности в разложении данных чисел.