Почему неправильно вычисляются все числа, полученные суммой двух избыточных?

Question

[Idwln]

Решая 23 задачу Эйлера:
Совершенным числом называется число, у которого сумма его делителей равна самому числу. Например, сумма делителей числа 28 равна 1 + 2 + 4 + 7 + 14 = 28, что означает, что число 28 является совершенным числом.

Число n называется недостаточным, если сумма его делителей меньше n, и называется избыточным, если сумма его делителей больше n.

Так как число 12 является наименьшим избыточным числом (1 + 2 + 3 + 4 + 6 = 16), наименьшее число, которое может быть записано как сумма двух избыточных чисел, равно 24. Используя математический анализ, можно показать, что все целые числа больше 28123 могут быть записаны как сумма двух избыточных чисел. Эта граница не может быть уменьшена дальнейшим анализом, даже несмотря на то, что наибольшее число, которое не может быть записано как сумма двух избыточных чисел, меньше этой границы.

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

Я создал алгоритм, который сначала находит все делители чисел от 1 до 28123(хотя можно и 28123/1.5) потом складываю все эти делители, и получаю числа, которые можно записать как сумма двух избыточных. Потом же, от 1 до 28123, все числа которые нельзя записать как сумма двух избыточных, я добавляю в результат. Но вот результат, выходит неправильным, и я не могу понять почему. Подскажите в чём ошибка

import math

arr_of_redundant = []
summary = 0
for i in range(1, int(28123/1.5)):
    arr = []
    n = 2
    for j in range(1, int(math.sqrt(i))):
        if i % j == 0:
            arr.append(j)
            if i % n == 0:
                arr.append(i / n)
            n += 1
    if sum(arr) > i:
        arr_of_redundant.append(i)

set_arr = set()
for x in arr_of_redundant:
    for y in arr_of_redundant:
        set_arr.add(x + y)
for i in range(1,28123):
    if i not in set_arr:
        summary += i

print(summary)

Ответ должен быть 4179871

Comments

[Алан Гибизов]

Неправильно вычисляются все числа, полученные суммой двух избыточных?

Да. Или нет. Вам какой ответ больше нравится?

[Alexandroppolus]

у тебя в подсчете суммы делителей числа какая-то мутная логика. Нихрена не понятно, что там за число n и почему иногда происходит arr.append(i / n). На самом деле там надо arr.append(i / j), если i / j > j

для проверки: всего должно быть 6965 чисел в массиве arr_of_redundant

[Idwln]

Alexandroppolus, Да, спасибо. Уже сам понял это )

Answer 1

[mayton2019]

Тут - надо шаг за шагом. Твой вопрос заключается сначала в стардартной формулировке задачи Эйлера.

И потом с утверждения

Я создал алгоритм, который сначала находит все делители чисел от 1 до 28123(хотя можно и 28123/1.5)

Ты его проверил? Есть ли какой-то тест который может быстро проверить что ты не ошибся? Я на самом деле ничего плохого пока не хочу сказать по твоему методу решения, но надо как-то двигаться более доказательно. А то получается ты вывалил на голову бедных Python разработчикам какую-то математическую идею (кстати тегнуть надо топик) и далее задаешь вопрос именно по ошибкам Python - приложения.

Я считаю нет, дорогой товарищ. Тут до Python еще далеко. Тут надо как в математике. Пристально следить за каждым statement и подвергать его сомнениям.

P.S Здесь нижнее округление идет.
int(math.sqrt(i)
Это нормально? Может верхнее надо?

Comments

[Idwln]

P.S Здесь нижнее округление идет.
int(math.sqrt(i)
Это нормально? Может верхнее надо?

Да это нормально и на результат это не влияет. Можно просто посмотреть на функцию и что она делает

Ты его проверил? Есть ли какой-то тест который может быстро проверить что ты не ошибся?

Да, в самом коде, в последней записи я вывожу результат. Это и есть проверка. Математически, лучше проверять все делители до 28123, но если я проверю все делители, которые получаю с 28123/1.5 то результат остаётся тем же, потому что сумма какого то кол-ва последних делителей будет больше 28123 и в них попросту нет смысла)

[mayton2019]

Idwln, я говорю не о сумме всех неизбыточных. А просто о простых числах. Вот меня интересует этот шаг.
Давай сверим часы. У меня была старая функция котора считает что-то на интервале. Вот от 2 до 28123 у меня 3069 простых чисел. А от двух до 2_000_000 я нашел 148934 простых. Проверь пожалуйста. Заодно и я себя проверю. Вдруг ошибся.

[Idwln]

mayton2019, А можно вопрос, почему простых, если я ищу избыточные числа?

[mayton2019]

Idwln, твой первый шаг на это наталкивает. Делители.