Информационный сервер для программистов: Исходники со всего света. Паскальные исходники со всего света
  Powered by Поисковый сервер Яndex: Найдется ВСЁ!
На Главную Pascal Форум Информер Страны мира
   Статьи о Паскале    >>    Совершенные числа
   
 
 Совершенная красота и совершенная бесполезность
 совершенных чисел
   Евгений Скляревский 15.08.2001


О совершенных и дружественных натуральных числах, формуле Евклида и реализации алгоритма на Паскале...


16k 
 

Совершенная красота и совершенная бесполезность совершенных чисел

Евгений Скляревский
Компьютерра №30, 15.08.2001


  Перестаньте отыскивать интересные числа!
Оставьте для интереса хотя бы одно
неинтересное число!
Из письма читателя Мартину Гарднеру

Среди всех интересных натуральных чисел, издавна изучаемых математиками, особое место занимают совершенные и близко связанные с ними дружественные числа.

Совершенным называется число, равное сумме всех своих делителей (включая 1, но исключая само число). Наименьшее из совершенных чисел 6 равно сумме трех своих делителей 1, 2 и 3. Следующее совершенное число 28=1+2+4+7+14. Ранние комментаторы Ветхого завета, пишет в своей книге «Математические новеллы» Мартин Гарднер, усматривали в совершенстве чисел 6 и 28 особый смысл. Разве не за 6 дней был сотворен мир, восклицали они, и разве Луна обновляется не за 28 суток?

Первым крупным достижением теории совершенных чисел была теорема Евклида о том, что число 2n-1(2n-1) - четное и совершенное, если число 2n-1 - простое 1. Лишь две тысячи лет спустя Эйлер доказал, что формула Евклида содержит все четные совершенные числа. Поскольку не известно ни одного нечетного совершенного числа (у читателей есть шанс найти его и прославить свое имя), то обычно, говоря о совершенных числах, имеют в виду четное совершенное число.

Приглядевшись к формуле Евклида, мы увидим связь совершенных чисел с членами геометрической прогрессии 1, 2, 4, 8, 16, … Эту связь лучше проследить на примере древней легенды, согласно которой Раджа обещал изобретателю шахмат любую награду. Изобретатель попросил положить на первую клетку шахматной доски одно зерно пшеницы, на вторую клетку - два зерна, на третью - четыре, на четвертую - восемь и так далее. На последнюю, 64-ю клетку, должно быть насыпано 263 зерен, а всего на шахматной доске окажется «кучка» из 264-1 зерен пшеницы. Это больше, чем собрано во всех урожаях за историю человечества.

Если на каждой клетке шахматной доски мы напишем, сколько зерен пшеницы причиталось бы за нее изобретателю шахмат, а затем снимем с каждой клетки по одному зерну, то число оставшихся зерен будет точно соответствовать выражению, стоящему в скобках в формуле Евклида. Если это число простое, то, умножив его на число зерен на предыдущей клетке (то есть на 2n-1), мы получим совершенное число! Простые числа вида 2n-1 называются числами Мерсенна в честь французского математика XVII века. На шахматной доске со снятыми по одному зерну с каждой клетки есть девять чисел Мерсенна, соответствующих девяти простым числам, меньших 64, а именно: 2, 3, 5, 7, 13, 17, 19, 31 и 61. Умножив их на число зерен на предыдущих клетках, мы получим девять первых совершенных чисел. (Числа n=29, 37, 41, 43, 47, 53, и 59 не дают числа Мерсенна, т.е. соответствующие им числа 2n-1 составные.)

Формула Евклида позволяет без труда доказывать многочисленные свойства совершенных чисел. Например, все совершенные числа треугольные. Это значит, что, взяв совершенное число шаров, мы всегда сможем сложить из них равносторонний треугольник. Из той же формулы Евклида следует другое любопытное свойство совершенных чисел: все совершенные числа, кроме 6, можно представить в виде частичных сумм ряда кубов последовательных нечетных чисел 13+33+53+… Еще более удивительно, что сумма величин, обратных всем делителям совершенного числа, включая его самого, всегда равна 2. Например, взяв делители совершенного числа 28, получим:

Кроме того, интересны представление совершенных чисел в двоичной форме, чередование последних цифр совершенных чисел и другие любопытные вопросы, которые можно найти в литературе по занимательной математике. Главные из них - наличие нечетного совершенного числа и существование наибольшего совершенного числа - до сих пор не решены.

От совершенных чисел повествование непременно перетекает к дружественным числам. Это такие два числа, каждое из которых равно сумме делителей второго дружественного числа. Наименьшие из дружественных чисел 220 и 284 были известны еще пифагорейцам, которые считали их символом дружбы. Следующая пара дружественных чисел 17296 и 18416 была открыта французским юристом и математиком Пьером Ферма лишь в 1636 году, а последующие числа находили Декарт, Эйлер и Лежандр. Шестнадцатилетний итальянец Никколо Паганини (тезка знаменитого скрипача) в 1867 году потряс математический мир сообщением о том, что числа 1184 и 1210 дружественные! Эту пару, ближайшую к 220 и 284, проглядели все знаменитые математики, изучавшие дружественные числа.

Определенный интерес для любителей представляет программа поиска совершенных чисел. Ее схема проста: в цикле для каждого числа проверять сумму его делителей и сравнивать ее с самим числом, - если они равны, то это число совершенное.

VAR
  I,N,Summa: LONGINT;
  Delitel: INTEGER;
begin
  FOR I:=3 TO 34000000 DO BEGIN
    Summa:=1;
    FOR Delitel:=2 TO SQRT(I) DO BEGIN
      N:=(I DIV Delitel);
      IF N*Delitel=I THEN
        Summa:=Summa + Delitel + (I DIV Delitel);
    END;
    IF INT(SQRT(I))=SQRT(I) THEN
      Summa:=Summa-INT(SQRT(I));
    IF I=Summa THEN WRITELN(I,' - ',Summa);
  END;
END.

Обратите внимание, что количество проверяемых делителей каждого числа растет до квадратного корня из числа. Подумайте о том, почему это так. И о том, что истинная красота - это нечто, в хозяйстве совершенно бесполезное, но бесконечно дорогое для настоящих ценителей.

[i40741]


1 (обратно к тексту) - Число 2n-1 может быть простым лишь в том случае, если прост показатель степени n. Обратное утверждение неверно: если показатель степени n прост, то число 2n-1 не обязательно должно быть простым.