Комментарии 5
К сожалению, использовать формулу Эйлера для разложения чисел на множители так просто не получится.
В общем случае, для вычисления σ(n) для произвольного n вам понадобятся все предыдущие значения σ, поскольку в начале рекурсивной формулы стоят σ(n-1) и σ(n-2). Даже если предположить, что какую-то часть из предыдущих значений σ можно вычислить более эффективно за счёт частичной факторизации, итоговая сложность O(n) не изменится.
Если я не ошибаюсь, есть алгоритм для подсчёта σ(n) за O(n^(2/3) (log log n)^(1/3)). (Такой точно есть для Φ(n), суммы φ(i) для 1<=i<=n, и для некоторых других мультипликативных функций). Но даже этот метод сложнее, чем простой перебор всех делителей до n^(1/2).
Пока что для нахождения x и y, таких что x^2=y^2 (mod n) и x!=y, ничего лучше общего метода решета числового поля не придумали.
Можете ли вы использовать ваши наработки для разложения, например, вот этого числа?
В общем случае, для вычисления σ(n) для произвольного n вам понадобятся все предыдущие значения σ, поскольку в начале рекурсивной формулы стоят σ(n-1) и σ(n-2). Даже если предположить, что какую-то часть из предыдущих значений σ можно вычислить более эффективно за счёт частичной факторизации, итоговая сложность O(n) не изменится.
Если я не ошибаюсь, есть алгоритм для подсчёта σ(n) за O(n^(2/3) (log log n)^(1/3)). (Такой точно есть для Φ(n), суммы φ(i) для 1<=i<=n, и для некоторых других мультипликативных функций). Но даже этот метод сложнее, чем простой перебор всех делителей до n^(1/2).
Пока что для нахождения x и y, таких что x^2=y^2 (mod n) и x!=y, ничего лучше общего метода решета числового поля не придумали.
Можете ли вы использовать ваши наработки для разложения, например, вот этого числа?
148 знаков
4811 212877 230137 338118 472961 390734 625505 372375 353711 331528 724028 741504 298492 768327 086476 531373 819245 127728 370303 225632 267266 215407 069359 264078 966689
Так в Г2± – модели НРЧ в клетке () всегда лежит сумма делителей N, если само число N помещено в клетке ().
Смотрим клетку с числом 21. Ищем сумму делителей (3+7=10). Не находим.
Вопрос — «в [соседней] клетке всегда лежит сумма делителей» — это к чему было сказано?
Сумма делителей числа 21 равна 1+21+3+7 =32. В клетке соседней (снизу) как раз лежит это число 32. Сумму собственных делителей легко получить из 32 — 1 -21 = 10 =3+7.
В статье приведен пример 3 поясняющий это для числа 147 = 21.7. Сумма равна не 21+7 =28, а 21+7 +1 +147 = 176.
В статье приведен пример 3 поясняющий это для числа 147 = 21.7. Сумма равна не 21+7 =28, а 21+7 +1 +147 = 176.
Да, с единицей и самим числом похоже на правду. Осталось найти быстрый алгоритм представления числа в виде разности квадратов (что пока никому не удалось). А без такого алгоритма быстрее получить делители методом перебора. При наличии же такого алгоритма теряет смысл нахождение суммы делителей, покольку делители есть первичная цель, а алгоритм напрямую дал бы нам делители, без необходимости в промежуточном результате в виде суммы.
Но тем не менее, закономерность интересная и может быть в совокупности с другими даже найдёт какое-то применение. Хотя пока применений не видно.
Но тем не менее, закономерность интересная и может быть в совокупности с другими даже найдёт какое-то применение. Хотя пока применений не видно.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Факторизация чисел и сумма неизвестных делителей. Часть IV