Рассказы о математике с примерами на языках Python и C (СИ) - Елисеев Дмитрий Сергеевич

Во-первых, слегка оптимизируем приведенную выше программу. Как нетрудно видеть, если число N делится нацело на P, то мы «автоматом» сразу находим и второй делитель N/P. Например, если 10 делится нацело на 2, то оно делится и на 10 / 2 = 5. Это позволяет заметно сократить число вариантов перебора. Во-вторых, используем тип чисел Decimal, позволяющий использовать большие числа. Обновленная программа выглядит так:

from decimal import *

def is_perfect(n):

    s = Decimal(1)

    p = Decimal(2)

    while p < n.sqrt()+1:

        if n % p == 0:

            s += p

            if p != n/p: s += n/p

        p += 1

    return s == n

print(is_perfect(Decimal('137438691328')))

Запускаем, программа работает — число '137438691328' действительно является совершенным. Оно делится на 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524287, 1048574, 2097148, 4194296, 8388592, 16777184, 33554368, 67108736, 134217472, 268434944, 536869888, 1073739776, 2147479552, 4294959104, 8589918208, 17179836416, 34359672832 и 68719345664, сумма этих чисел равна 137438691328. Однако, на моем компьютере проверка «совершенности» данного числа заняла… 54 секунды. Это конечно быстро по сравнению с 16-м веком, но совершенно недостаточно чтобы проверить все числа, хотя бы до миллиарда. Значит пора использовать более тяжелую артиллерию — перепишем программу на языке Си. Все-таки Python это интерпретатор, и работает заметно медленнее. Получаемый код не намного сложнее:

#include <string.h>

#include <math.h>

#include <stdbool.h>

#include <stdint.h>

bool isPerfect(unsigned long long int n)

{

  unsigned long long int sum = 1, i;

  for(i=2; i<=sqrt(n)+1; i++)

  {

    if (n%i==0) {

      sum += i;

      if (i != n/i) {

        sum += n/i;

      }

    }

  }

  return sum == n;

}

int main()

{

  unsigned long long int n = 137438691328LL;

  bool res = isPerfect(n);

  printf("%dn", res);

  return 0;

}

Компилируем программу с помощью компилятора gcc, запускаем получившийся exe-файл: время выполнения меньше секунды, уже гораздо лучше. Теперь несложно поменять функцию main для перебора всех чисел от 1 до 200000000000. В код также добавлен вывод промежуточных результатов каждые 1000000 итераций, чтобы видеть ход выполнения программы.

int main()

{

  unsigned long long int MAX = 200000000000LL;

  unsigned long long int p;

  for (p=1; p<MAX; p++) {

    if (isPerfect(p))

      printf(" %llu ", p);

        if (p % 1000000 == 0)

          printf("*%llu,%llu*", 100*p/MAX, p);

  }

}

Увы, прогноз относительно скорости расчетов оказался слишком оптимистичным. Примерно за час работы программы, было перебрано лишь 100 млн. вариантов, а для перебора всех 200 млрд. понадобился бы не один день. Желающие могут продолжить процесс самостоятельно, однако с уверенностью можно сказать что в диапазоне от 1 до 100000000 действительно нет совершенных чисел кроме 6, 28, 496, 8128 и 33550336.

Проверка числа 2 305 843 008 139 952 128 является непростой задачей даже для современного домашнего компьютера — во-первых, в языке C/C++ нет встроенных типов данных для столь большого числа, а во-вторых, число вариантов перебора весьма велико.

Разумеется, выше было приведено самое простое решение «в лоб», можно оптимизировать и саму программу, например разбить вычисление на несколько процессорных ядер, однако данная задача выходит за рамки этого материала. Немного про параллельные вычисления будет рассказано в конце книги.

7. Магический квадрат

Еще одна старинная математическая головоломка — магический квадрат. Магическим называют квадрат, заполненный неповторяющимися числами так, что суммы чисел по горизонталям, вертикалям и диагоналям одинаковы. Такие квадраты известны давно, самым старым из известных является магический квадрат Ло Шу, изображенный в Китае в 2200 г. до нашей эры. Если подсчитать количество точек, то можно перевести квадрат в современный вид, изображенный справа.

Магический квадрат 4х4 был обнаружен в индийских надписях 11 века:

И наконец, известный квадрат 4х4, изображенный на гравюре немецкого художника Дюрера «Меланхолия». Этот квадрат изображен не просто так, 2 числа 1514 указывают на дату создания гравюры.

Как можно видеть, уже математики прошлого умели строить магические квадраты разной размерности. Интересно рассмотреть их свойства.

Сумма чисел магического квадрата размера NxN зависит только от N, и определяется формулой:

Это несложно доказать, т. к. сумма всех чисел квадрата равна сумме ряда 1..N2. Действительно, для квадрата Дюрера M(4) = 34, что можно посчитать на картине. Для квадратов разной размерности суммы равны соответственно: M(3) = 15, M(4) = 34, M(5) = 65, M(6) = 111, M(7) = 175, M(8) = 260, M(9) = 369, M(10) = 505.