Simplify the problem

[aurimas13]

I have solved the problem, but would like to know how to simplify my code so it doesn't take ages to find the exact m (triangular number) and n (square) numbers.

The problem is this: The integer 36 has a peculiar property: it is a perfect square, and is also the sum of the integers from 1 through 8. The next such number is 1225 which is 352, and the sum of the integers from 1 through 49. Find the next number that is a perfect square and also the sum of a series 1...n. This next number may be greater than 32767. You may use library functions that you know of, (or mathematical formulas) to make your program run faster. It is also possible to write this program using for-loops to determine if a number is a perfect square or a sum of a series.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  for (unsigned long long int n = 1; n < 2147483647; n++) // define n integer in a loop
    for ( unsigned long long int m = 1; m < 2147483647; m++) { // define m integer in a loop
      if (pow(n,2) == m*(m+1)/2) { // find integers that are equal to one another on Pell equation
        if (n == 1 && m == 1) {continue;} // ignore the value of 1 and skip it
      cout << "The square number is " << n << " and the n-th triangular number is " << m << ends; // output
    }
  }
  return 0;
}

[dhayden]

You don't need the inner loop at all. Given n, solve for m and then see if it's an integer.

[Chervil]

You may use library functions that you know of, (or mathematical formulas) to make your program run faster.

If you're allowed to use mathematical formulae, perhaps this may help:
http://www.cut-the-knot.org/do_you_know/triSquare2.shtml

That generates all the pairs before the 64-bit int overflows in a fraction of a second.

[aurimas13]

What you mean by "Given n, solve for m and then see if it's an integer."? Thank you.

[Chervil]

"Given n, solve for m"

Take this equation (not C++ code, it's algebra here)

n * n = m*(m+1)/2

n is known (it is the for loop variable).
that gives a quadratic equation with m as the unknown.
Solve using standard techniques for a quadratic equation, to give the value of m. (only the positive root is required).
Then test to see either whether it is an integer, or possibly check that it satisfies the original equation, whichever works best. (You may need to use type double or long double here).

When I tried this it was faster than the nested loops, but still vastly slower than the other solution I suggested above.

[aurimas13]

Should I change the if statement to what you proposed here? But that still leaves me with the infinite loop. I am pretty new to C++, so all the jargon you are using is still new to me. Thank you for your help!

[Chervil]

Well, much of what I wrote in my last post was regarding high-school mathematics, not C++. So far I've not proposed any actual c++ code, my comments were more at the level of how the program might be designed.

Take this equation, n * n = m*(m+1)/2 where m is the unknown, re-arrange into the form
x = ax² + bx + c and solve using the formula
x = (-b +- sqrt(b² - 4ac)) / (2a)
https://en.wikipedia.org/wiki/Quadratic_formula

That gives the result (this is C++ code):

m = (sqrt(1+8*n*n)-1)/2;

and that can be used in your program. Get rid of the inner for-loop, and instead find the value of m corresponding to the current value of n. Then verify that this is an integer solution, if so print out m and n.

Note: you may want to work through the algebra on your own, to verify my solution for yourself.

[aurimas13]

Thank you. I will try to use it and look what I get. Last question the inner loop is the nested loop for m integer, right? Thanks.

[Chervil]

Yes, that's right.

By the way, I tried this myself, various ways. The calculation which I suggested uses floating-point values (type double). But when verifying the result, I too used the 64-bit integer type unsigned long long, in order to avoid approximations and loss of precision which can occur with floating-point calculations. Hence you may need different types of variables at different stages.

[aurimas13]

I am trying to do what you said, but unfortunately I get something wrong. I am completely lost as to what I need to write to find the integers n and m without doing the inner loop. I don't understand how one can find m number when I don't initialise or I don't put it in the loop. Currently, I have this code, but it is completely wrong as it doesn't output anything:

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  unsigned long long int m = 36;
  for (unsigned long long int n = 1; n < 2147483647; n++) {// define n integer in a loop
//    for ( unsigned long long int m = 1; m < 2147483647; m++) { // define m integer in a loop
//      if (pow(n,2) == m*(m+1)/2) { // find integers that are equal to one another on Pell equation
//        if (n == 1 && m == 1) {continue;} // ignore the value of 1 and skip it
    if (m == (sqrt(1+8*n*n)-1)/2) { cout << "The square number is " << n << " and the n-th triangular number is " << m << endl; }
  }
  return 0;
}

[TheIdeasMan]

Hi,

sqrt returns a double, so you would need to cast that back to an integral type before comparing it to m

Rather than unsigned long long int, I find it easier to use std::size_t

[Chervil]

At line 11,

    if (m == (sqrt(1+8*n*n)-1)/2)

m has the value 36 (assigned at line 6).
Hence you are comparing every result to see whether it is 36. That will never be true, the possible values of m are 8, 49, 288 ... but in any case to test against the known result isn't what you need to do.

Let's go back to the post made by dhayden above,

You don't need the inner loop at all. Given n, solve for m and then see if it's an integer.

This means simply do the calculation, and test whether or not the result is an exact whole number such as 49, rather than some none-integer such as 47.585860 or 50.414143.

In order to do that, use floating-point variables in the calculation. Actually I'd recommend type long double here as it gives slightly better precision than double.

You should make both m and n of type long double.
Instead of this:

    if (m == (sqrt(1+8*n*n)-1)/2)

try something like this:

    long double m = (sqrt(1 + 8 * n * n) - 1) / 2;

So long as n is of type long double too, that should give a floating-point result, which is what you want. (strictly speaking, you might us 1.0L, 8.0L and 2.0L so that all the values are of the same type).

Then, after you've calculated the value of m, you might do this:

    if (std::round(m) == m)

which might be adequate.

What does round() do? It converts the value to the nearest integer.
47.585860 would become 48
49 would become 49
50.414143 would become 50
Then the if statement compares those two values, to see whether they are the same.
49 is indeed equal to 49, so that is a required result.
47.585860 is definitely not equal to 48, so that is not a result.

http://www.cplusplus.com/reference/cmath/round/

Note, I tried this using just an ordinary double, but because of a lack of precision it gave both the correct results, as well as a lot of incorrect result. I think the extra precision of long double should be sufficient here - otherwise you may need to verify the result another way. I've said more than enough for one post, so I'll leave it there for now.

[JLBorges]

Simplified version:

#include <iostream>

int main() {

    unsigned long long sum_till = 1 ;
    unsigned long long series_sum = 1 ;

    for( unsigned long long n = 2 ; n < 1'000'000'000 ; ++n ) {

        const unsigned long long square = n*n ;
        while( square > series_sum ) series_sum += ++sum_till ;
        if( square == series_sum )
            std::cout << square << " == " << n << '*' << n << " == " << " 1 + ... + " << sum_till << '\n' ;
    }
} 

36 == 6*6 ==  1 + ... + 8
1225 == 35*35 ==  1 + ... + 49
41616 == 204*204 ==  1 + ... + 288
1413721 == 1189*1189 ==  1 + ... + 1681
48024900 == 6930*6930 ==  1 + ... + 9800
1631432881 == 40391*40391 ==  1 + ... + 57121
55420693056 == 235416*235416 ==  1 + ... + 332928
1882672131025 == 1372105*1372105 ==  1 + ... + 1940449
63955431761796 == 7997214*7997214 ==  1 + ... + 11309768
2172602007770041 == 46611179*46611179 ==  1 + ... + 65918161
73804512832419600 == 271669860*271669860 ==  1 + ... + 384199200

http://coliru.stacked-crooked.com/a/3ef1da5889af37a5

[JLBorges]

Not as simple as above, but much, much faster: use the recurrence relation for Pell numbers to generate square triangular numbers https://en.wikipedia.org/wiki/Pell_number#Square_triangular_numbers

#include <iostream>

int main() {

    unsigned long long hp = 1 ; // previous half companion Pell number
    unsigned long long pp = 0 ; // previous Pell number

    unsigned long long s = 0 ; // square root of the square triangular number
    for( int n = 1 ; s < 1'000'000'000 ; ++n )
    {
        const unsigned long long h = hp + 2 * pp ; // next half companion Pell number
        const unsigned long long p = hp + pp ; // next Pell number
        s = h * p ; // square root of the next square triangular number
        const unsigned long long t = n%2 ? h*h : 2*p*p ; // sum +ve integers up to t

        std::cout << s*s << " == square of " << s << " == sum of positive integers up to " << t << '\n' ;

        hp = h ;
        pp = p ;
    }
} 

1 == square of 1 == sum of positive integers up to 1
36 == square of 6 == sum of positive integers up to 8
1225 == square of 35 == sum of positive integers up to 49
41616 == square of 204 == sum of positive integers up to 288
1413721 == square of 1189 == sum of positive integers up to 1681
48024900 == square of 6930 == sum of positive integers up to 9800
1631432881 == square of 40391 == sum of positive integers up to 57121
55420693056 == square of 235416 == sum of positive integers up to 332928
1882672131025 == square of 1372105 == sum of positive integers up to 1940449
63955431761796 == square of 7997214 == sum of positive integers up to 11309768
2172602007770041 == square of 46611179 == sum of positive integers up to 65918161
73804512832419600 == square of 271669860 == sum of positive integers up to 384199200
2507180834294496361 == square of 1583407981 == sum of positive integers up to 2239277041

http://coliru.stacked-crooked.com/a/442b1889561294d4

[aurimas13]

Thank you guys!

[Chervil]

As previously mentioned, another fast method http://www.cut-the-knot.org/do_you_know/triSquare2.shtml

#include <iostream>

int main()
{
    unsigned long long x = 0, x2 = 1;
    unsigned long long y = 0, y2 = 1;
    
    while (x < x2 && y < y2)
    {
        x = x2;
        y = y2;
        std::cout << "square of " << y << " == sum of integers up to "<< x << '\n';
        x2 = 3 * x + 4 * y + 1;
        y2 = 2 * x + 3 * y + 1;
    }
}

square of 1 == sum of integers up to 1
square of 6 == sum of integers up to 8
square of 35 == sum of integers up to 49
square of 204 == sum of integers up to 288
square of 1189 == sum of integers up to 1681
square of 6930 == sum of integers up to 9800
square of 40391 == sum of integers up to 57121
square of 235416 == sum of integers up to 332928
square of 1372105 == sum of integers up to 1940449
square of 7997214 == sum of integers up to 11309768
square of 46611179 == sum of integers up to 65918161
square of 271669860 == sum of integers up to 384199200
square of 1583407981 == sum of integers up to 2239277041
square of 9228778026 == sum of integers up to 13051463048
square of 53789260175 == sum of integers up to 76069501249
square of 313506783024 == sum of integers up to 443365544448
square of 1827251437969 == sum of integers up to 2584123765441
square of 10650001844790 == sum of integers up to 15061377048200
square of 62072759630771 == sum of integers up to 87784138523761
square of 361786555939836 == sum of integers up to 511643454094368
square of 2108646576008245 == sum of integers up to 2982076586042449
square of 12290092900109634 == sum of integers up to 17380816062160328
square of 71631910824649559 == sum of integers up to 101302819786919521
square of 417501372047787720 == sum of integers up to 590436102659356800
square of 2433376321462076761 == sum of integers up to 3441313796169221281

Or the same algorithm more briefly:

#include <iostream>
int main() {
    for (unsigned long long x=1, y=1, n=0, x2, y2; n<25; x=x2, y=y2, ++n) {
        std::cout << "square of " << y << " == sum of integers up to "<< x << '\n';
        x2 = 3 * x + 4 * y + 1;
        y2 = 2 * x + 3 * y + 1;
    }
}