I need a formula for the thing in the description

Question

1.00/5 (1 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 24-Aug-19 1:57am

Member 14549814

Updated 26-Aug-19 5:32am

Add a Solution

Comments

[no name] 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?

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Stefan_Lang · Answer 1 · 2019-08-26T05:32:00

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:

C++

#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

RickZeeland · Answer 2 · 2019-08-24T02:48:00

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[^]

Posted 24-Aug-19 2:48am

RickZeeland

Updated 25-Aug-19 1:44am

v3

k5054 · Answer 3 · 2019-08-24T03:20:00

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.

Rick York · Answer 4 · 2019-08-24T10:31:00

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.

C++

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;
}

I need a formula for the thing in the description

4 solutions

Solution 4

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0