Совершенные числа
18.03.2021 18:21, автор DiEitch
Меня часто спрашивают, пользуюсь ли я Питоном в своей деятельности? Да. Пользуюсь часто и много. Питон - это мой "ручной зверёк" для проверки расчётов. Как правило, это простые программы для механизации вычислений в разных областях знания. Но сегодня не об этом.
Недавно я прочитал интересную статью о совершенных числах. Но самое интересное, что я ни разу о них не слышал ни в ВУЗе, ни в школе, ни даже от знакомых математиков. Разумеется, я внимательно прочитал данную статью и решил восполнить этот пробел в моих знаниях.
Главным свойством совершенных чисел является то, что они равны сумме своих собственных делителей: например, 6 = 1+2+3, а 28 = 1+2+4+7+14. Но в математике для их изучения используют в основном функцию σ (сигма), которая включает в сумму ещё и несобственный делитель (т.е. само совершенное число): σ(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56. Тогда для совершенного числа будет соблюдаться соотношение σ(x) = 2x.
Известный математик Евклид ещё более 2000 лет назад изучил и описал эти числа, а также нашёл первые четыре таких числа: 6, 28, 496 и 8128. И что самое интересное - все эти четыре числа являются чётными числами (т.е. делятся на число 2 без остатка). Позже были найдены и другие совершенные числа (тоже чётные), а также благодаря зависимости этих чисел от простых и трудам Мерсенна, каждый раз удаётся вывести очень большое чётное совершенное число M= 2k ×(2k+1 – 1), где 2k+1 – 1 вновь открытое простое число (разумеется, при k > 0). "Приложил руку" к совершенным числам и великий Эйлер, он доказал, что это единственный способ получить четные совершенные числа.
Но самое интересное, что за 2000 лет ни одного нечётного совершенного числа так и не было найдено, как и доказательства того, что оное не существует.
Итак, давайте повторим подвиг Евклида и мы, найдём первые четыре совершенных числа, а если повезёт ещё и нечётное совершенное число!!! Только пусть на этот раз считает компьютер. Составим алгоритм на Python:
Как видно, функция сигма полностью повторяет классическую функцию поиска делителей, с той лишь разницей, что полученное суммируем, начиная с единицы. Проверку на нечётность осуществляет условие if (sig % 2 > 0), если остаток от деления на 2 не равен 0, то число, разумеется, нечётное. Между прочим, проверить на чётность в двоичной системе счисления можно ещё проще - проверить младший бит числа (реализацию этого я поручаю тому, кто захочет повторить мои вычисления).
Первые четыре числа программа получает за секунды, но вот потом надо будет очень хорошо подождать.
За два часа работы программы, к сожалению, я так и не получил ни одного нового совершенного числа (тем более нечётного). Но не стоит расстраиваться. Быть может, это к лучшему? Ведь если связать получение новых совершенных чисел и криптовалюту (пусть она будет называться PerfectCoin, например), каждая новая монета требовала бы значительных затрат и высоко ценилась))).
Всем хорошего дня.