A program for finding and printing the first perfect square (i * i), the last two digits of which are 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 

Perhaps I am mistaken, but I believe that for a long time it cannot be large enough to store the answer. Can someone confirm that the program is working correctly and cannot keep the number for a long time, or something is wrong that I am missing. Or something completely different that I missed.

thanks

Answer 1

My impression is that this number does not exist.

Effectively, you only need to take a look at i=50 , because i * i % 100 cyclical with a period of exactly 50. Thus, the range of numbers is not the problem you are facing.

All ideal squares that have an odd number at the end of their last position end in 6 (16, 36, 196, 256, 576, etc.), which is not odd. The problem has no solution. There is no perfect square ending with two odd numbers.

The reason for this loop 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 two final digits n^2 will be the same as for b^2 , where 0 <= b <50, in particular, b = n% 50.

In fact, you do not even need to go to 49, but only 25, like:

  ( 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 & equiv; j (mod 100), then I & sup2; & Equiv; J? (mod 100), so the last two values ​​have the same lower two digits. Therefore, you only need to check the integers in the range [0, 99], and since all their squares will be in the range [0, 9801], everything will conveniently fit into regular integers. Is there a solution now? If this does not happen, your loop will continue to run either forever or until i * i overflows, causing undefined behavior.

Answer 3

From what I read, it is impossible to have such an origin. Here is yahoo answer with proof :

So, let's look at this: it is obvious that individual numbers correspond to 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 cases where both 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 them think of a two-digit number like 10x + y, where x and y are single digits (10x + y) ^ 2 = 100x ^ 2 + 20xy + y ^ 2 We can ignore 100 x ^ 2, since this would only affect the third digit . To get the odd last digit, we know that y ^ 2 must be an odd number. If y <4, 20 xy should even be with 20 ALWAYS, and therefore 20 xy should be even. Since all single odd digits always give an even second digit, then the second digit must be even.

For three or more digits of a number, we can ignore the third digit, since this would only affect the third last digit.

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

Following this proof, you can also see that regardless of the number of digits you add to the number, squaring it will always be at least one of the last two digits.

Answer 4

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

Secondly, 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 first two terms are clearly even, so you only need to consider 1-digit numbers.

Thirdly, the square of an even number is even, so you only need to check the numbers 1, 3, 5, 7 and 9.

Finally, by quadratically checking each of the five candidates, you can easily show that the requested number does not exist.

Answer 5

There is no such number. Let's say such a number exists. Then the last 2 digits of the square are determined by the last 2 digits of the number. Suppose the last 2 digits are x (10th place) and y (1st place). Thus, a number can be represented as 10x + y. When we take the square of it, we get 100x.x + yy + 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 the value of x and y, it is always equal. Thus, all squares are in 10th place.