Необходимо эффективно вычислять суммы типа: Сумма/по i от 1 до N/{i^p}, т. е. 1^p + 2^p + 3^p + ... + N^P.
Например, для p = 2 нужно вычислить: 1^2 + 2^2 + 3^2 + ... + N^2. Дело в том, что для таких сумм существуют хитрые формулы. Приведенный пример равен N(N+1)(2N+1)/6. Для p = 1 вообще имеем арифметическую прогрессию. Знаю формулы до p = 8. А вот хотелось бы для p, эдак, 100.
Может между ними существует некая рекурентная связь. Хотя, глядя, на формулы (до p = 8) не вижу такой.

Очень надо.

P. S. Интересно: (1 + 2 + 3 + ... + N )^2 = 1^3 + 2^3 + 3^3 + ... + N^3. Дальше так уже не катит

или я что то не догоняю или ...... но это же вроди простой цикл .....

Remiznik тут все дело в слове

Цитата(Cr @ 6.5.2005, 23:25)

эффективно

Cr@$h посмотри здесь
а вообще в Гугле попробуй поискать.
Начни с изучения этого:

Цитата

Швейцарский математик Якоб Бернулли (1654-1705) изучал свойства последовательности чисел, возникающей при суммировании степеней последовательных натуральных чисел. А именно, для любого натурального k существует — и это будет доказано на лекции — такой многочлен Sk(n), что для любого натурального n сумма k-х степеней первых n натуральных чисел равна Sk(n). Числами Бернулли Bk называют коэффициент при первой степени переменной n многочлена Sk(n). Оказывается, B1 = 1/2, а все остальные числа Бернулли с нечётными номерами равны 0. Мы выведем рекуррентное соотношение, выражающее очередное число Бернулли через предыдущие, а также формулу, выражающую коэффициенты многочлена Sk(n) через числа Бернулли. И разные другие интересные формулы.

Цитата с http://mmmf.math.msu.su/lect/lect5.html (Найдено при помощи великого Гугля)

аааа я всё понял тут ешё практакуется ручной труд ))))

Спасибо за ссылки, Illuminaty. За мной не заржавеет

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

Цитата(Illuminaty @ 7.5.2005, 00:18)

Remiznik тут все дело в слове Цитата(Cr @ 6.5.2005, ) эффективно

Можно и так попробывать одновремменно с двух сторон цикл (while) побегать.
А можно и еще круче с двух сторон бежим к середине и из середины бежим к концам. На много меньше итераций получается чем в обычном цикле который тупо бежит вперед!
Illuminaty спасибо классный метод!

Это сообщение отредактировал(а) AISIN - 11.5.2005, 19:47

Цитата(Illuminaty @ 7.5.2005, 14:35)

А зачем тебе такие суммы?

В численном анализе очень надо было. Разобрался, круто. А уже через эти формулы конечных сумм вывел собственно нужные формулы для
Сумма(i<j){i*j}, Сумма(i<j<k){i*j*k}, ... и
Сумма(i<j){i^2*j^2}, Сумма(i<j<k){i^2*j^2*k^2}, ...
AISIN, понимаешь в чем дело: начиная с некоторого момента накопленная сумма перестанет чувствовать очередное слагаемое!

Сумма i^p по i от 1 до N вычисляется полиномом степени (p+1) от N - лет 20 назад где-то видел аж с доказательством. Счас уже и не упомню где - в какой-то познавательной книжуле типа "Занимательной математики"...
Добавлено @ 15:59

Цитата(Cr @ 14.5.2005, 16:04)

начиная с некоторого момента накопленная сумма перестанет чувствовать очередное слагаемое!

Видимо, упираешься в точность...

Сумма для большого числа слагаемых находится межуд двумя интегралами

Интеграл( x^p,0,n)<=S(X)<=Интеграл( x^p,0,n+1)

то есть

x^[n+1]/[n+1]<=S(X)<x^[n+2]/[n+2]

У меня была такая задача на acm контесте
Я её решал динамически, т.е. пусть нам известна формула для p (отметим, что это полином), тогда для p+1 она получается следующим образом:
1) интегрируется наш полином для p и умножаем его на (p+1)
2) нормализуем полином, т.е. делим все члены на его старший член
3) получаем полином, и в нем считаем сумму слагаемых s (она должна быть меньше 1)
4) затем к нашему полиному прибавляем (1 - s)x (там сумма всех слагаемых должна быть равна 1)
И таким образом получаем формулу для p+1, там правда такие числа получаются, что не влазит в __int64 уже при p порядка 20
Если надо кому-то реализовывать, то полином должен храниться как массив его коэф-тов в целом типе, т.е. не нормализованный, иначе траблы будут из-за маленькой точности double или float