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

Сверхсоставные числа

Натуральное число и называется сверхсоставным, если у всех натуральных чисел, меньших n, количество делителей меньше, чем у я. Первым сверхсоставным числом является 1 просто потому, что у него нет предшественников. (Парадокс терминологии: 1 является сверхсоставным числом, но не относится к составным. Вторым, конечно, идет 2, третьим – 4, четвертым – 6, пятым – сразу аж 12. Ну а как найти n-е сверхсоставное число? Вот нужная нам функция.

Вот как с помощью этой функции можно составить таблицу первых m сверхсоставных чисел.

Однако у этой программы есть существенный недостаток: поиск в ней организован весьма неэффективно. Ведь программа для поиска очередного сверхсоставного числа повторяет все вычисления, выполненные для поиска всех предшествующих сверхсоставных чисел. Поэтому она ищет очередное сверхсоставное число слишком медленно. Для составления списка сверхсоставных чисел лучше использовать другую программу.

В составленной по результатам выполнения программы таблице для каждого сверхсоставного числа указано количество и сумма делителей, а также его каноническое разложение.

Заметьте, что в каноническом разложении сверхсоставных чисел простые числа следуют без пропусков (т.е. за Prime [i] в каноническом разложении следует Prime [i+1], а не большее простое число), а показатели степеней – в невозрастающем порядке. Все сверхсоставные числа, за исключением 1, четные. Начиная с четвертого все они делятся еще и на 3 и потому кратны 6. Начиная с пятого все они делятся не только на 2, но и на квадрат двойки, т.е. на 4, и потому кратны 12. Но не думайте, что если n-е сверхсоставное число делится на простое число р, то и все последующие сверхсоставные числа будут делиться на это простое число р. 25-е сверхсоставное число делится на простое число 11, а 26 – и 27-е сверхсоставные числа на 11 не делятся. Потом, правда, 11 опять появляется в каноническом разложении. Так что вы, возможно, склонны считать это исключением или аномалией. Но в таком случае придется признать, что это исключение (или аномалия – как вам больше нравится?) не единичное. Ведь 53-е сверхсоставное число делится на простое число 17, а 54-е сверхсоставное число на 17 не делится. В данном случае, правда, аномалия еще короче: 17 появляется в каноническом разложении уже 55-го числа.

Как вы думаете, для всякой ли степени данного простого числа найдется такое сверхсоставное число, что все последующие за ним сверхсоставные числа делятся на эту степень данного простого числа? Если вам это очевидно, то заметьте, что из этого немедленно следует, что все сверхсоставные числа, начиная с некоторого, номер которого, конечно, зависит от заданного натурального числа, делятся на это заданное натуральное число. Действительно уж, сверх-составные – антиподы простых! Впрочем, все эти свойства в нашей программе не учитываются. (В программе не учитывается даже, что сверхсоставных чисел бесконечно много.) Зато эту программу легко модифицировать так, чтобы поиск сверхсоставного числа можно было продолжить начиная с любого ранее найденного. Вот как, например, можно продолжить поиск сверхсоставных чисел после 64-го.

Тем не менее, нужно заметить, что гораздо более эффективно поиск сверхсоставных чисел можно было бы организовать по их каноническому представлению или же с применением решета, основанного на нахождении чисел, имеющих заданное число делителей. Методы решета позволили бы сразу вычеркнуть из таблицы большинство чисел, поскольку, как мы видели на графике, большинство чисел имеют совсем немного делителей. Ведь при больших n на долю каждого из первых n натуральных чисел в среднем приходится лишь Inn делителей.