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

I came up with this regex before to detect potential perfect squares using last 4 decimal digits. The actual regex is gapless. I simply spaced them out to showcase how they relate to each other in alternating patterns :

---

/(^([0149]|(8|[39]6|[48]4)1|
           (6|14|32|[47]8)4|
          (19?|3|25|[56]7)6|
           (4|16|28|[57]2)9|           [26]?25)|
                            ([0-9][02]|[05]6)25|

  ([0 2 4 6 8 ][0 4 8 ]|[ 1 3 5 7 9][2 6 ])[19]|

  ([0 2 4 6 8 ][0 4 8 ]|[ 1 3 5 7 9][2 6 ])([0  68]4|[13  9]6)|
  ([ 1 3 5 7 9][ 1 5 9]|[0 2 4 6 8 ][ 3 7])([02  8]4|[ 35  ]6)|
  ([ 1 3 5 7 9][0 4 8 ]|[0 2 4 6 8 ][2 6 ])([ 24  ]4|[  57 ]6)|
  ([0 2 4 6 8 ][ 1 5 9]|[ 1 3 5 7 9][ 3 7])([  46 ]4|[1  79]6))(00)*$/'

It simply reaffirms statements others have made already - that no pair of last-2 digits both being odd exists anywhere in this regex pattern.

Here's the condensed edition. The regex flavor is ERE, compatible with just about any regex engine you could possibly imagine nowadays.

/(^([0149]|(8|[39]6|[48]4)1|(6|14|32|[47]8)4|
        ([13]|19|25|[56]7)6|(4|16|28|[57]2)9|([26]2|2)5)|
                                     ([0-9][02]|[05]6)25|
   ([02468][048]|[13579][26])[19]|
   ([02468][048]|[13579][26])([068]4|[139]6)|
   ([13579][159]|[02468][37])([028]4|[35]6)|
   ([13579][048]|[02468][26])([24]4|[57]6)|
   ([02468][159]|[13579][37])([46]4|[179]6))(00)*$/

Performance is reasonably fast because it uses a fully greedy syntax, doesn't require any sort of lookahead or lookbehind, so hardly any amount of backtracking is needed.

The first half of the regex were a special cutout optimized for numbers less than 1000. While their patterns can be inferred just as easily via last 4 rows, it was really down the matching that way since it required plenty of extra ? (matching once optionally). In fact, throughout the whole regex, ? was only used twice, * (any) once, and no + (all) at all.

(BRE is such a jurassic dinosaur it really ought to go the way of the do-do bird)

Answer 2

From what I've been reading, it is impossible to have such an occurence. Here is a yahoo answer with a proof:

So, let's look at it: Obviously, the single digits fit your observation 0^2 = 00, 1^2 = 01, 2^2 = 04, 3^2 = 09, 4^2 = 16, 5^2 = 25, 6^2 = 36, 7^2 =49, 8^2 = 64, 9^2 = 81 So, there are instances where both the last two digits are even (especially iof we count 0 as even), and beyond 10, well, 12^2 = 144 (two even digits) But NONE with 2 odd digits.

Let's think of a two digit number as 10x + y, where x and y are single digits then (10x + y)^2 = 100x^2 + 20xy + y^2 We can ignore the 100 x^2, since this would only influence the third digit. To get an odd last digit, we know that y^2 has to be an odd number If y < 4, the 20 xy must be even since 20 is ALWAYS even, and hence 20 xy must be even. Since all the single odd digits always give an even second digit, then the second digit must be even.

For three or more digits in the number, we can ignore the third digit, since this would only influence the third last digit.

So, there are no squares with two odd digits as the last two numbers.... :-)

Following that proof, you can also see that no matter the number of digits you add to the number, when squared it will always result in atleast one of the last 2 digits being even.

Answer 3

There is no such number. Let us say such a number exists. Then the last 2 digits of the square are determined by the last 2 digits of the number. Assume that the last 2 digits are x(10th place) and y(1th place). So the number can be represented as 10x+y. When we take the square of this we get 100x.x + y.y+20x.y

(10*x+y)(10*x+y) = 100*x*x + y*y + 20*x*y. 

Now the last digit is determined by y*y. This is only possible if y is odd. The last but one digit is determined by 20*x*y. Whatever be the value of x and y, this is always even. So all the squares have the 10th place even.

Answer 4

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 5

First of all, it's sufficient to check numbers from 0 to 99, because (100+N)^2 has the same last 2 digits as N^2.

Second, let your 2-digit number N be written as AB, or, in other words, let N=10*A+B, where A and B are 1-digit numbers. Then N^2=100*A^2+20*A*B+B^2. The 1st two summands are clearly even, so you only have to consider 1-digit numbers.

Third, a square of an even number is even, so you only have to check numbers 1, 3, 5, 7, and 9.

Finally, by squaring by hand each of the above five candidates you easily show that the requested number does not exist.

Answer 6

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.