-1

So i've been attempting this problem for the last few days and have no luck. I am tasked to find square pairs from 1 to x.

Num1 + Num2 = a perfect square (i.e. 2 + 2 = 4. 16 + 20 = 36)

Num2 - Num1 = a perfect square. (i.e. 2 - 2 = 0. 20 - 16 = 4)

I've been getting closer to a result, but for the life of me can not figure out whats going wrong in my loops. for example: this is my latest approach:

Function to test if a number is a perfect square:

bool isSquare(int num){
    if(num < 0)
        return false;
    int root = round(sqrt(num));
    return num == root * root;
}

main:

int num1 = 1; num2 = 2;
int tempP, tempM;
for(int i = 1; i <= number; i++){
    for(int j = 1; j <= num1; j++){
        tempP = num1 + num2;
        tempM = num2 - num1;
        if(isSquare(tempP) && isSquare(tempM)){

            cout << num1 << "\t" << num2 << "\t" << tempP << "\t" << tempM << endl;
        }
        num2++;

    }
    num1++;
}

for some reason my output (regardless of how big 'int number' is) is limited to one row. My other tests(such as having the second loop go until j <= number) end with my num1s repeating themselves, num2s going past number, and printing every number until it stops.

I have no idea where to go next, any pointers would be helpful.

Thank you all

EDIT: expected output of 12:

N P N + P P – N

2 2 4 0
4 5 9 1
6 10 16 4
8 8 16 0
8 17 25 9
10 26 36 16
12 13 25 1
12 37 49 25

Actual output of 12:

N P N + P P – N

2 2 4 0

Cœur
  • 37,241
  • 25
  • 195
  • 267
King Twix
  • 52
  • 8
  • Can you add your output, and what you expect the output to be? – Jay Oct 17 '17 at 01:36
  • Why are you using separate values, num1 and num2, instead of using the index variables? Also, did you know that [floating point math is broken](https://stackoverflow.com/questions/588004/is-floating-point-math-broken), and because of that, you cannot use `sqrt` and `round`, for this? – Sam Varshavchik Oct 17 '17 at 01:38
  • Do it the other way. Generate squares, for each square generate pairs whose sum and diff are that square. – Cheers and hth. - Alf Oct 17 '17 at 01:41
  • @SamVarshavchik I actually had no idea about floating point math being weird. interesting! the code for that boolean function still seems to work, should it be updated to fix that, however? Also, i updated my post to kinda explain the two values. I can't think of a better way to do it, since the two values are independent, and only add up to a square pair – King Twix Oct 17 '17 at 01:50
  • A different approach:For integers `a` and `b`, `a+b=s^2` and `a-b=r^2`. Therefore `2a = s^2 + r^2` Use the following theorem from number theory: https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem – MFisherKDX Oct 17 '17 at 02:05
  • "seems to work" isn't always good enough. Technically, this looks wrong to me, but it looks like like using `round()` compensates for the rounding errors introduce by `sqrt()`, so the combination of the two may turn out to be good enough. – Sam Varshavchik Oct 17 '17 at 03:08

4 Answers4

0

num2 is always increasing. You need to reset num2 to an appropriate value at the start of your i loop (before starting the j loop).

1201ProgramAlarm
  • 32,384
  • 7
  • 42
  • 56
  • This helped a ton! However when using 12, it skips repeating pairs (8 and 12 repeat twice, yet don't get shown). but when i use large values (for example 100) 8 and 12 got repeated there. – King Twix Oct 17 '17 at 02:24
0

The problem is your double loop is incrementing incorrectly. And 1201ProgramAlarm beat me to the punch... num2 never gets reset to 2, so it just keeps growing.

Instead try using the variable from your second loop instead of num2 and see what happens.

Also, comment out or remove num2++;

Flexo
  • 87,323
  • 22
  • 191
  • 272
Chris Hatch
  • 1
  • 2
0

To avoid brute-force exhaustive searching and checking of squareness, you could use reverse math logic to generate only appropriate pairs. Let

a=num2
b=num1
a >= b > 0

It is known that

a + b = k^2
a - b = m^2

Subtract these equations:

2 * b = k^2 - m^2 = (k-m) * (k+m)

We can see that k and m must have the same oddity - both even or both odd (and b is always even).

So we can enumerate k = 2, 3, 4..., for every k get possible m = k-2, k-4, k-6... and get all (a,b) pairs.

b = (k^2 - m^2) / 2
a = k^2 - b

k   m   b   a
2   0   2   2
3   1   4   5
4   0   8   8
4   2   6   10
5   1   12  13
5   3   8   17
6   0   18  18
6   2   16  20
6   4   10  26
...

One more approach: enumerate even b's, for every b generate all factorizations of b/2 into 2 multipliers p and q (b/2 = p * q, p >= q) and calculate possible variants of k=p+q and a = k^2-b

Example for b=24: 

b/2 = 12
p   q   k   a
12  1   13  145 
6   2   8   40
4   3   7   25
MBo
  • 77,366
  • 5
  • 53
  • 86
0

Your code looks convoluted since i and j increases along with num1 and num2 anyways, so why not combine them?

for (int N = 1; N <= number; N++)
    {
        for (int P = 0; P <= number; P++)
        {
            if (ceilf(sqrtf(N+P)) == sqrtf(N+P) && ceilf(sqrtf(P-N)) == sqrtf(P-N))
            {
                cout << left << setw(10) << N << setw(10) << P << setw(10) << P + N << setw(10) << P - N << endl;
            }
        }
    }

include the cmath library

Duy Nguyen
  • 1