Find a four-digit number which is equal to the four least significant (rightmost) digits of its own square.
-
$\begingroup$ If i understand this correctly you want us to give a number like 1111 and square it (which would make: 1234321) then the 4 right most digits (4321) should be 1111 again? (obviously 1111 doesn't work but it's a simple example) $\endgroup$– VincentApr 13, 2015 at 15:15
-
$\begingroup$ @VincentAdvocaat Exactly. $\endgroup$– AngkorApr 13, 2015 at 15:17
-
$\begingroup$ So if i'm not a total fool the last number must always be 5 or 6 (xxx5 or xxx6) since those 2 are the only once to produce their same number onces squared (5^2 = 25 and 6^2 = 36). hmm interesting. O great whilst typing this JLee came up with an answer, too bad. $\endgroup$– VincentApr 13, 2015 at 15:19
-
$\begingroup$ This might have been better with a [no-computers] tag $\endgroup$– Engineer ToastApr 13, 2015 at 15:29
-
$\begingroup$ except brute forcing is the only answer (so it seems) so that makes it a bit impossible with no computer.. $\endgroup$– VincentApr 13, 2015 at 16:41
4 Answers
The equation
$$x^2 = x \bmod 10^4$$
is true exactly if $10^4$ is a divisor of $x (x -1)$. This requires that the prime factorizations of $x$ and $x-1$ jointly contain $2^4$ and $5^4$. Since they are relatively prime, each of $2^4$ and $5^4$ must be divisor of one of them. A factor of both would be a multiple of $10^4$ and thus not 4 digits, so each number must be a multiple of one factor:
- $2^4 \mid x $ and $5^4 \mid x-1$, or
- $5^4 \mid x $ and $2^4 \mid x-1$
We can use the Chinese remainder theorem algorithm to find the corresponding residue classes
- $x = 9376 \mod 10000$
- $x = 625 \mod 10000$
The second doesn't correspond to any four-digit numbers, so the only solution is $9376$.
I think this is the only one:
9,376 * 9,376 = 87,909,376
-
1$\begingroup$ Yes, normally there would be two of them of a given length, but $0625$ fails due to the leading zero. $\endgroup$ Apr 13, 2015 at 15:19
-
$\begingroup$ I am curious in what Kik was asking as well. A program can easily get it but is there like a general formula / strategry that's associate with? $\endgroup$– AlexApr 13, 2015 at 15:22
-
3$\begingroup$ it's an: automorphic number, wikipedia has an article about it and it has an algorithm for finding out how many of those numbers there are in the given number space. though i don't know of something to make it easyer to find them $\endgroup$– VincentApr 13, 2015 at 15:29
-
1$\begingroup$ @VincentAdvocaat - Thanks for the link. Maybe I am a nerd, but I was expecting an ideal answer to incorporate how this is realized (i.e. the algorithm). $\endgroup$ Apr 13, 2015 at 17:02
-
1$\begingroup$ @Snowbody: no, it is not a coincidence. When there are two $n$ digit automorphic numbers they sum to $10^n+`1$. For example $25^2=625, 76^2=5776, 25+76=101$. $\endgroup$ Apr 13, 2015 at 20:51
Its 9376. I ran a brute force and calculated it using below program.
#include<cmath>
#include<iostream>
using namespace std;
int last4digit(int n)
{
int x = n / 10000;
n -= x * 10000;
return n;
}
int main()
{
for (int i = 1000; i < 10000; i++)
{
if (i == last4digit(pow(i, 2)))
cout << i;
}
system("pause");
return 0;
}
-
$\begingroup$ Hmm, sort of unlucky that you answered late. $\endgroup$– user88Apr 14, 2015 at 4:47
-
3$\begingroup$ So, this is getting downvoted while an answer with even less explanation is at +10/-0? $\endgroup$– xnorApr 14, 2015 at 6:56
-
$\begingroup$ @xnor Well, at least the other answer showed why 9376 works. $\endgroup$ Apr 14, 2015 at 9:38
-
$\begingroup$ @randal'thor i edited and gave the solution to find it. $\endgroup$ Apr 14, 2015 at 9:41
-
My solution with no knowledge of the Chinese remainder theorem and no sophisticated thinking! It must end in 5 or 6 (0² and 1² are of course equal to 0 and 1 but the 'tens' digit always fails) Choose 5 or 6 and and let the first, second and third digits be a,b,c. I'll use 6. Treat it as if abc6 were a proper decimal number and square it by long multipication, spacing the columns wide enough, though we only need the four rightmost columns (bc in the 'thousands' column will mean b×c thousands etc) I'll put in more steps than I suspect are needed, for clarity:
a b c 6
~~~~~~~~~~~~~~~~~~~~~~~~~
6a 6b 6c 36
bc c² 6c
bc 6b
6a
___________________________
12a+2bc 12b+c² 12c 36 then tidy a bit
2a+2bc+b 2b+c²+c 2c+3 6
Using ≡ to mean is equivalent to, mod 10;
and working columns right to left
2c+3 ≡ c
c+3 ≡ 0
c = 7 2c+3 = 17 so add 1 to next column
2b+c²+c+1 ≡ b
b+57≡0
b=3 2b+c²+c+1 = 63 so add 6 to next column
12a+2bc+b+6 ≡ a
11a+42+3+6 ≡ 0
11a+51 ≡ 0
a+1 ≡ 0
a=9
So answer = 9376
It is even easier for the other solution leading to 30 ≡ a at the end. With a little care this technique can of course be used in other bases than 10, and any number of final digits.
Update: This was a dangerous question for me; I tried it in base 60,
like the Sumerians used. Here's the six results
complete with squares, and translations into base 10.
With the sums at the bottom:
44,45,56,16 33,23,57,41,44,45,56,16 966 9376 9349683222 9376
50,22,13,21 42,17,10,28,50,22,13,21 1088 0001 11837442176 0001
24,51,50,25 10,18,13,07,24,51,50,25 537 0625 2884361289 0625
35,08,09,36 20,34,32,18,35,08,09,36 758 9376 5759862806 9376
09,37,46,40 01,32,43,47,09,37,46,40 208 0000 432640000 0000
15,14,03,45 03,52,05,10,15,14,03,45 329 0625 1082821289 0625
03,00,00,00,03 01,51,58,42,34,00,00,00,03
Notice that pairs add up to 01,00,00,00,00,01 as we might expect,
but also look at the last four digits of the translations.
I didn't expect that. Time for more thinking.