Программа использует для расчёта сумм делителей функцию делителей в сочетании с сегментированным решетом. Сложность O(NlogN).
Найденные числа печатаются, под ними сделана "бегущая строка", в которой выводится последнее проверенное число и затраченное время. "Строка" обновляется раз в десять секунд. На вход подаётся стартовое число, с которого будет вестись поиск.
import math
import time
def sigma1(n1, n2):
ss = [1] * (n2 - n1)
js = list(range(n1, n2))
p = 2
for i in range(-n1 % p, n2 - n1, p):
js[i] //= p
m = p
f = 1 + p
while js[i] % p == 0:
js[i] //= p
m *= p
f += m
ss[i] *= f
for p in range(3, math.isqrt(n2 - 1) + 1, 2):
i1 = -n1 % p
if js[i1] % p != 0:
continue
for i in range(i1, n2 - n1, p):
js[i] //= p
m = p
f = 1 + p
while js[i] % p == 0:
js[i] //= p
m *= p
f += m
ss[i] *= f
for i in range(n2 - n1):
if js[i] > 1:
ss[i] *= js[i] + 1
return ss
def main():
step = 10
start_ts = time.perf_counter()
next_ts = start_ts + step
n1 = int(input())
while True:
n2 = n1 + math.isqrt(n1)
ts = time.perf_counter()
if ts >= next_ts:
print('.', n1, f'{ts - start_ts:.1f}s', end='\r', flush=True)
next_ts = ts + step
for i, s in enumerate(sigma1(n1, n2), start=n1):
if s % i == 3:
print(i, s, flush=True)
n1 = n2
main()
$ echo 1 | python abudant-numbers-3.py
4 7
18 39
. 61937222 70.0s
За двадцать шесть часов программа проверила все числа до сорока пяти миллиардов. Других решений кроме 4 и 18 не найдено:
$ echo 1 | python abudant-numbers-3.py
4 7
18 39
. 45002156776 92292.3s
Производительность:
В самом начале программа просеивает почти миллион чисел в секунду. Где-то через пять часов будет проверено десять миллиардов чисел и темп проверки снизится в два раза, до пятисот тысяч в секунду. Он так и продолжит уменьшаться всё медленнее и медленнее. К концу года темп снизится до четырёхсот тысяч чисел в секунду. К этому времени будет проверено десять триллионов чисел. Через сто лет, после проверки одного квадриллиона чисел, темп проверки снизится до трехсот пятидесяти тысяч чисел в секунду.
Я не шучу, проверьте сами, для десяти триллионов за 15.8 секунды проверяется 6324555 чисел:
$ echo 10_000_000_000_000 | python abudant-numbers-3.py
. 10000006324555 15.8s
Получается темп 6324555 / 15.8 ≅ 400000.
Алгоритм хорошо распределяется между любым количеством компьютеров. Если у вас сто штук, вы проверите квадриллион чисел не за век, а за год. Программу надо будет доработать, чтобы она принимала диапазон, сейчас она считает бесконечно.
Ещё одна идея - перенести алгоритм на C. Оценить эффект трудно, думаю ускорение будет в 10-100 раз.
Но если браться за задачу всерьёз, надо изучить теорию глубже. Задача связана с избыточностью числа. Я не нашёл прямых утверждений, но, кажется, больших чисел с избыточностью три быть не должно. Почитайте, например, про слегка избыточные числа.
Ну и, конечно, простой перебор - не разумный способ. Надо искать способ пропускать много чисел, а проверять лишь некоторые, подозрительные. Уверен, что что-то такое должно быть.