Иллюстрированный самоучитель по Mathematica 5

Факторизация чисел, десятичная запись которых состоит из n единиц

До сих пор мы изучали быстродействие функции FactorInteger на аргументах, близких к 2ⁿ. В двоичной системе счисления запись таких чисел содержит много нулей или единиц подряд. Число Мерсенна M_n, например, записывается n единицами, а число 2ⁿ +1 – двумя единицами, между которыми стоит n-1 нуль (рассматриваем случай n > 0). Поэтому может показаться, что функция FactorInteger столь эффективна лишь для чисел, которые имеют специальный вид в двоичной системе счисления. Поэтому давайте изучим возможности этой функции по факторизации больших чисел видов, более случайных с точки зрения теории чисел. Попытаемся разложить, например, числа, десятичная запись которых представляет собой повторение одной и той же цифры л раз. Конечно, если n =1, то эта цифра повторяется только один раз, и вопрос о разложении решается в уме.

С другой стороны, даже если n> 1, то, разделив такое число на ту цифру, которая повторяется n раз, получим число, десятичная запись которого состоит из л единиц. Так что для факторизации чисел такого вида достаточно иметь таблицу разложения чисел, десятичная запись которых состоит из n единиц. Обозначим э то число через 1_n. Как задать такое число? Как легко видеть, число, десятичная запись которого состоит из n девяток, равно 10ⁿ -1. Разделив это число на 9, получим число, десятичная запись которого состоит из л единиц: (10ⁿ -1)/9. Таким образом, мы убедились, что:

(10ⁿ -1)/9= 1_n= 111……………………….111 ("единиц).

Заметим сразу, что такие числа могут быть простыми лишь в том случае, если количество единиц n в записи такого числа – простое. Действительно, если n = m k, то такое число делится как на число, состоящее из т единиц, так и на число, состоящее из k единиц. Короче говоря, от m| n › 1_m | 1_n. (Убедиться в этом очень легко, мысленно выполнив деление "столбиком".)

Теперь несложно написать нужную нам программу.

В пределах таблицы простых чисел совсем немного, они получаются лишь при n = 2, 19 и 23. Поэтому при всех четных n число 1 имеет 11 в качестве простого множителя. Несколько сложнее увидеть, что 3^k |n › 3^k | 1_n. (Например, все числа вида 1_3m делятся на 3, это следует из школьного признака делимости на 3. Аналогично обстоит дело и с числами вида 1_9m.) Это следует из того, что 3^k |1_k. Как видим, используя таблицу факторизации чисел вида 1_n, составленную с помощью простой программы, совсем несложно подметить простейшие закономерности в разложении данных чисел.