10
$\begingroup$

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

$\endgroup$
  • $\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 '15 at 15:15
  • $\begingroup$ @VincentAdvocaat Exactly. $\endgroup$ – Angkor Apr 13 '15 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 '15 at 15:19
  • $\begingroup$ This might have been better with a [no-computers] tag $\endgroup$ – Engineer Toast Apr 13 '15 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 '15 at 16:41
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$
  • 1
    $\begingroup$ Yes, normally there would be two of them of a given length, but $0625$ fails due to the leading zero. $\endgroup$ – Ross Millikan Apr 13 '15 at 15:19
  • $\begingroup$ I'd be interested to know how you could derive this "intelligently". I wrote a program to brute force it easily, but I wonder if there is any other way? $\endgroup$ – Kik Apr 13 '15 at 15:19
  • 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 '15 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 '15 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$ – Ross Millikan Apr 13 '15 at 20:51
7
$\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$
  • $\begingroup$ Hmm, sort of unlucky that you answered late. $\endgroup$ – Joe Z. Apr 14 '15 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 '15 at 6:56
  • $\begingroup$ @xnor Well, at least the other answer showed why 9376 works. $\endgroup$ – Rand al'Thor Apr 14 '15 at 9:38
  • $\begingroup$ @randal'thor i edited and gave the solution to find it. $\endgroup$ – Kishan Kumar Apr 14 '15 at 9:41
  • $\begingroup$ @KishanKumar Thanks for editing! :-) $\endgroup$ – Rand al'Thor Apr 14 '15 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, privacy policy and cookie policy

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