Click here to Skip to main content
14,325,629 members
Rate this:
Please Sign up or sign in to vote.
See more:
The problem is more complicatele, but after all this is what i got:
n*1^3+(n-1)*(2^3)+(n-2)*(3^3)+...+n^3
I need a formula because n can be 500.000.000

What I have tried:

Because of using big numbers, doing the calculation one by one will exceed the TLE
Posted
Updated 26-Aug-19 5:32am
Comments
0x01AA 24-Aug-19 9:30am
   
My feeling is like Math. Induction can help here (to create the formula): Mathematical induction - Wikipedia[^]
Patrice T 24-Aug-19 10:40am
   
Show your work
Patrice T 24-Aug-19 21:10pm
   
There is not much calculations to save in this formula.
Can you give reference to complete problem?
Rate this:
Please Sign up or sign in to vote.

Solution 4

The sum can be expressed as
result = Sum{k=1..n} (n+1-i) * k^3
= (n+1) * Sum{k=1..n} k^3 - Sum{k=1..n} k^4

(Sorry, no idea how to use mathematica symbols in HTML)

There are closed solutions for the two sums of k^a for any positive integral number a. You can find the solution for Sum(k^3) and a simple algorithm to derive the solution for Sum(k^4) at Sum of n, n², or n³ | Brilliant Math & Science Wiki[^]

The formula for k^3 as offered right at the top of that web site is:
Sum{k=1..n} (k^3) = n^2*(n+1)^2 / 4

and the sum for k^4 is given at the very bottom as:
Sum{k=1..n} (k^4) = n*(n+1)*(2*n+1)*(3*n^2+3*n-1) / 30

Now all you have to do is calculate both, multiply the former by (n+1). and subtract the latter.

P.S.: Here's a little program to prove the formulas are working as intended:
#include <iostream>

using namespace std;
double sum_of_power3(int n)
{
    double dn = (double)n;
    return dn*dn*(dn+1)*(dn+1)/4;
}
double sum_of_power4(int n)
{
    double dn = (double)n;
    return dn*(dn+1)*(2*dn+1)*(3*dn*dn+3*dn-1)/30;
}
int main()
{
    double sn3 = 0;
    double sn4 = 0;
    for (int n = 1; n < 5; ++n)
    {
        sn3 += n*n*n;
        sn4 += n*n*n*n;
        cout << "sum of " << n << "^3 " << sn3 << " " << sum_of_power3(n) << endl;
        cout << "sum of " << n << "^4 " << sn4 << " " << sum_of_power4(n) << endl;
    }

    return 0;
}
Output:
sum of 1^3 1 1                                                                                                                               
sum of 1^4 1 1                                                                                                                               
sum of 2^3 9 9                                                                                                                               
sum of 2^4 17 17                                                                                                                             
sum of 3^3 36 36                                                                                                                             
sum of 3^4 98 98                                                                                                                             
sum of 4^3 100 100                                                                                                                           
sum of 4^4 354 354                                                                                                                           
   
v3
Rate this:
Please Sign up or sign in to vote.

Solution 1

Take a look at this CodeProject article: A BigNumber Class Done in C#[^]

If you are using C++ take a look at: Boost Multiprecision library[^]
And here is a nice video: How to use the Boost C++ Libraries in Visual Studio - YouTube[^]
   
v3
Rate this:
Please Sign up or sign in to vote.

Solution 2

If you're using Linux, then GMP is probably the way to go. There's instructions for compiling on windows, too, but that seems to require Cygwin[^], a Unix like environment for windows. Maybe today you could do it with WSL.

If you're in the .NET world, then RickZeelan's suggestion will probably work for you. Otherwise, take a look here: List of arbitrary-precision arithmetic software - Wikipedia[^] and see if any of the libraries fit your needs. If you intend to distribute the finished product, don't forget to make sure the license for the library is compatible with your distribution plans.
   
Rate this:
Please Sign up or sign in to vote.

Solution 3

Using floating point values :
calculating value for 500,000,000 : result was 1.563E+42 - time was 5.812 seconds
in debug mode on a laptop.
template< typename T > T Cube( T a )    // calculates the cube of a value
{
    return a * a * a;
}

double CalculateSeries( UINT64 size )
{
    double sum = 0;
    for( UINT64 n = 0; n < size; ++n )
       sum += ( size - n ) * Cube( (double)n + 1.0 );
    return sum;
}
   
Comments
Rick York 24-Aug-19 16:40pm
   
In release mode it takes 0.634 seconds.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100