Program to find and print the first perfect square (i*i) whose last two digits are both odd

Question

#include <iostream>
#include <cmath>

int main(int argc, const char * argv[])
{    
    for (long i = 1; i > 0; i++) {
        long n = i*i;
        long x = n % 10; 
        long y = n / 10 % 10;

        if (x % 2 != 0 && y % 2 != 0) {
            std::cout << i << std::endl;
            std::cout << n << " " << n % 100 << " " << y << " " << x << std::endl;
            std::cout << "Number Found: " << n << std::endl;
            break;
        }
    }

}

-- RESULT --
3037000501
-9223372030635300615 -15 -1 -5
Number Found: -9223372030635300615

I may be wrong, but I believe that long may not be large enough to store the answer. Can someone confirm that the program is working properly and long cannot store the number, or is there something wrong that I am missing. Or something completely different that I missed.

Thanks

Answer 1

My impression is that that number does not exist.

Effectively, you only need to look up to i=50 because i * i % 100 is cyclical with a period of precisely 50. So, range of numbers is not the problem you are experiencing.

All the perfect squares that have an odd digit in its next to last position end in 6 (16, 36, 196, 256, 576 and so on), which is not odd. The problem has no solution. There is no perfect square ending in two odd digits.

The reason of this cycle is that any number can be expressed as

    n = a * 50 + b  ,  with 0 <= b < 50.  In fact, by definition b = n % 50

And then,

    n^2 % 100 =
    ( a*50 + b )^2 % 100 =
    ( (a*50)^2 + 2*b*a*50 + b^2 ) % 100 =
    ( a*a*2500 + b*a*100 + b^2 ) % 100 =
    b^2 % 100 =
    ( n % 50 )^2 % 100

In other words, the 2 final digits of n^2 will be the same as of b^2, where 0 <= b < 50, specifically, b = n % 50.

In fact, you don't even need to go as far as 49, but just 25, as:

    ( 50 - i )^2 % 100 =
    ( 50^2 - 2*50*i + i^2 ) % 100 =
    ( 2500 - 100*i + i^2 ) % 100 =
    i^2 % 100

In other words

    50^2 %100 = (50- 0)^2 %100 =  0^2 %100 =  0
    49^2 %100 = (50- 1)^2 %100 =  1^2 %100 =  1
    48^2 %100 = (50- 2)^2 %100 =  2^2 %100 =  4
        ...
    27^2 %100 = (50-23)^2 %100 = 23^2 %100 = 29
    26^2 %100 = (50-24)^2 %100 = 24^2 %100 = 76
    25^2 %100 = (50-25)^2 %100 = 25^2 %100 = 25

Answer 2

If i ≡ j (mod 100), then i² ≡ j² (mod 100), hence the latter two values have the same bottom two digits. You therefore only need to check integers in the range [0, 99] and, as all their squares will be in the range [0, 9801], everything will fit comfortably into ordinary integers. Now, is there actually a solution? If there isn't, your loop will keep running either forever or until i * i overflows, triggering undefined behavior.