14,325,629 members
Rate this:
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
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

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:

## 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:

## 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:

## 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:

## 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;
}```
Rick York 24-Aug-19 16:40pm

In release mode it takes 0.634 seconds.