10
$\begingroup$

Find a four-digit number which is equal to the four least significant (rightmost) digits of its own square.

$\endgroup$
6
  • $\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$
    – Vincent
    Apr 13, 2015 at 15:15
  • $\begingroup$ @VincentAdvocaat Exactly. $\endgroup$
    – Angkor
    Apr 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$
    – Vincent
    Apr 13, 2015 at 15:19
  • $\begingroup$ This might have been better with a [no-computers] tag $\endgroup$ Apr 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$
    – Vincent
    Apr 13, 2015 at 16:41

4 Answers 4

16
$\begingroup$

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$.

$\endgroup$
10
$\begingroup$

I think this is the only one:

9,376 * 9,376 = 87,909,376

$\endgroup$
9
  • 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$
    – Alex
    Apr 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$
    – Vincent
    Apr 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$
    – 299792458
    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
6
$\begingroup$

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;
}
$\endgroup$
6
  • $\begingroup$ Hmm, sort of unlucky that you answered late. $\endgroup$
    – user88
    Apr 14, 2015 at 4:47
  • 3
    $\begingroup$ So, this is getting downvoted while an answer with even less explanation is at +10/-0? $\endgroup$
    – xnor
    Apr 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
  • $\begingroup$ @KishanKumar Thanks for editing! :-) $\endgroup$ Apr 14, 2015 at 9:43
4
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.