22
$\begingroup$

I was helping Ernie clean out his shed a while back when I saw a curious old machine. "Oh yeah, that!" said Ernie, when I pointed it out to him. "A few years back, before transistors were invented, I tried to make a clockwork calculator. It worked, but was never a commercial success." The machine consisted two rows of six sockets, three buttons (labelled A, M, and E) and a short strip of paper emerging from a narrow slot on one side. "Didn't need a key-pad," said Ernie, "instead you would put a plug for each numeral into the sockets, and then press A or M to add or multiply the numbers represented on the two rows. The answer would be printed out on the paper strip. Internally it calculated the units digit of the result first, then the tens, hundreds, etc. It was a bit slow, so I got it to print out each digit as soon as it could, so the digits of the answer were printed out in reverse order."

I had a closer look, the machine had spent a bit too much time sitting under a leaking window, and the bottom row of sockets had rusted out entirely. And the box of plugs only contained one 4, one 6, two 0's, three each of 1, 5 and 7, five each of 8, and 9, and six 2's. There were no 3's left at all. "Yep, looking back I can see it would never have caught on - too easy to lose digits. That's why I never built subtraction or division into it", Ernie commented. "No chance of demonstrating it properly now, but if I swap a couple of cogs over...", Ernie delved into a back panel with a screw-driver for a few seconds, "...I should be able to get something out of it".

Ernie put plugs for 8 and 6 in the 10's 1's slots of the machine, wound the key a couple of turns and hit the button marked A. After a few seconds of humming, a length of paper strip emerged with the digits 2, 7, and 1 on it. "See," he said, "now it reads the digits of both numbers from the top row of sockets. See, 86 + 86 = 172". He added another plug to the hundreds to make 786, gave the key a few more turns and pressed the M button. After a longer pause (and more humming), the digits 6, 9, 7, 7, 1, and 6 emerged in turn on the paper strip. I made a quick calculation on the back of an envelope. "Wow!", I exclaimed, "786*786 = 617,796. It works!".

enter image description here "Have a go yourself." said Ernie. I removed the plugs from the sockets on the top row, replaced them with some more, and turned the key until it felt tight. "What does the E button do?" I asked. "Oh, Exponentiation." he said, "it used to calculate the first row to the power of the second row, so now it will calculate n^n". I pressed the button. "Can't imagine it completing that calculation before the clockwork runs out" Ernie exclaimed. "And even if it does, I'm sure the paper won't be long enough to print it out". We watched for a couple of minutes, but nothing seemed to happen - the machine hummed gently but no numbers were printed out.

After doing more tidying around the shed for a while (still no print-out), we went back to the house for coffee. When we returned, Ernie was proven right, the clockwork calculator had run down and was humming no longer. But before it stopped, it had printed out a string of digits. To my surprise, the digits, in the order they had been printed were exactly the same as the plugs (reading left to right) that I had inserted into the upper sockets.

I can't remember exactly what the number I used was, but do remember that at the time I worked out that the digits were all correct and I had chosen the largest possible number that could be entered into the calculator with that result. Can you help me remember what the number was?


In other words, we're looking for an $n$, consisting of no more than $6$ of the following digits: $\{0,0,1,1,1,2,2,2,2,2,2,4,5,5,5,6,7,7,7,8,8,8,8,8,9,9,9,9,9\}$, such that $n^n$ ends with the digits of $n$ in reverse order.

$\endgroup$
  • 4
    $\begingroup$ How many 6s do we have? $\endgroup$ – d'alar'cop Oct 15 '14 at 4:48
  • 2
    $\begingroup$ "Internally it calculated the units digit of the result first, then the tens, hundreds, etc." If they are printed in that order the way the image suggests, the result is not reversed. So it seems internally it calculated the most significant digit first (that is weird, but if Ernie made it work, it's fine). $\endgroup$ – oerkelens Oct 15 '14 at 7:04
  • $\begingroup$ +1 to oerkelens. Perhaps the creator of this puzzle think of "print" like "print" to the console, which is left to right. The background story is rather long, but it's interesting, and I'm liking it, so it's ok =) $\endgroup$ – justhalf Oct 15 '14 at 7:07
  • $\begingroup$ @Oerkelens: if you make a hand calculation for a large sum or product, you start at the right aswell, no? $\endgroup$ – Tim Couwelier Oct 15 '14 at 7:38
  • 1
    $\begingroup$ So we need to construct n, containing 1-6 digits out of {0,0,1,1,1,2,2,2,2,2,2,4,5,5,5,7,7,7,8,8,8,8,8,9,9,9,9,9}, such that the most significant digits of n^n are those of n in reverse. $\endgroup$ – SQB Oct 15 '14 at 13:19
6
$\begingroup$

I wrote a little program to compute $N^N$ $mod$ $1000000$. And checked whether the last digits of the result match the digits of $N$ reversed.

I got the following solutions:

$999999^{999999}$ $mod$ $1000000$ $=$ $999999$
$100001^{100001}$ $mod$ $1000000$ $=$ $100001$
$90789^{90789}$ $mod$ $100000$ $=$ $98709$
$10001^{10001}$ $mod$ $100000$ $=$ $10001$
$1001^{1001}$ $mod$ $10000$ $=$ $1001$
$1^{1}$ $mod$ $10$ $=$ $1$

$999999$ is not possible, we only have 5 $9$'s (I'll assume the $6$ won't do).

$100001$ is not possible, we only have 2 $0$'s.

$\mathbf{90789}$ is the largest working number

$\endgroup$
  • $\begingroup$ Your little program gives exactly the same choices as my one, so I will accept your answer. $\endgroup$ – Penguino Oct 15 '14 at 22:34
7
$\begingroup$

I think the answer is 890625.

I started to look at the powers of 5 and noticed there is a lovely pattern!

                   5
                  25
                 125
                 625
                3125
              1 5625
              7 8125
            3 9 0625
          1 9 5 3125
          9 7 6 5625
         48 8 2 8125
        244 1 4 0625
       1220 7 0 3125
       6103 5 1 5625
      30517 5 7 8125
     152587 8 9 0625
     762939 4 5 3125
    3814697 2 6 5625
   19073486 3 2 8125
   95367431 6 4 0625
  476837158 2 0 3125
 2384185791 0 1 5625
11920928955 0 7 8125

At first I thought that it was just 0625,3125,5625 and 8125 repeated at the end, but then I noticed that

  • a number ending in 0625 is always preceded by either a 9 or a 4
  • a number ending in 90625 is always preceded by 3 or 8.

And it goes on...

The preceding pairs always add up to 5, but I haven't noticed a pattern for how you predict which pair it will be.

Here are all the combinations for the last 6 digits of a power of 5:

ClockworkCalculator

The number at the top is the smallest unit.

Where there is a 3 in the sequence, I have made the circles red (as the problem states there are no 3's)

From the bottom upwards, I searched for the largest number and highlighted the number in green.

I used this calculator to check some of predictions: http://www.calculatorpro.com/calculator/exponent-calculator/

Unfortunately it cannot handle 890625 itself (it timed out!) so I cannot confirm that 890625^890625 ends in 890625, but I believe it does!

$\endgroup$
  • $\begingroup$ I applied the technique described here: 890625^890625 does indeed end in 890625. There are other numbers that have powers whose last digits are their roots, though ... see the powers of 7. There may be a larger number. Also, there aren't any 6s in that box, are there? Although Ernie did pull a 6 out of thin air. $\endgroup$ – Otaia Oct 15 '14 at 19:33
  • $\begingroup$ It shouldn't end in 890625, it should start with 526098. $\endgroup$ – SQB Oct 15 '14 at 19:39
  • $\begingroup$ @Otaia Thanks for checking it. :) Will have to check some more (prime?) numbers out... $\endgroup$ – Ali Oct 15 '14 at 19:43
  • $\begingroup$ @SQB The problem states that the numbers come out in reverse order, beginning with the last digit. $\endgroup$ – Otaia Oct 15 '14 at 19:56
  • 1
    $\begingroup$ Given the picture change by OP, I now believe this to be the correct answer. $\endgroup$ – Joel Rondeau Oct 15 '14 at 20:53
3
$\begingroup$

I did a little research on this problem and found that the least significant digits of a large exponent can be found fairly easily through the use of modular exponentiation. So I wrote a quick Python script to find the largest numbers:

def modular_pow(base, exp, mod):
    result = 1
    base = base % mod
    while (exp > 0):
        if (exp % 2 == 1):
           result = (result * base) % mod
        exp = exp >> 1
        base = (base * base) % mod
    return result

# find the largest 5 numbers < 1000000, n, where n^n mod 1000000 = n        
a = 1000000
b = 0
count = 0
while (a > 1 and count < 5):
    a = a - 1
    b = modular_pow(a, a, 1000000)
    if (a == b):
        count = count + 1
        print(a)

Output:

999999
999001
998751
998001
997376

The second number, 999001, matches the constraints.

$\endgroup$
  • $\begingroup$ I like this solution. I think there must be a way to reverse b for your if statement test to find the "reverse" outputs too... $\endgroup$ – Ali Oct 15 '14 at 21:07
  • $\begingroup$ @Ali I don't think so - there's no easy way to find the most significant digits of those numbers. They must have millions of digits, and you can't drop any digits between multiplications. $\endgroup$ – Otaia Oct 15 '14 at 21:49
  • $\begingroup$ We are still after the least significant digits, but they have to be the reverse of the numbers input, so instead of testing 999001 == 999001, it would test if 100999 == 999001 etc. $\endgroup$ – Ali Oct 15 '14 at 22:16
1
$\begingroup$

I just brute forced it, and it seems to me that "1" may be the answer.

$\max\ n.\ (first6digits(n^n).reverse = n)\ .0<n<999998. = 1$.

Just for the record:

$first6digits(n^n) = \lfloor10^{((n\ log_{10}n) \mod 1)+5}\rfloor$

It's computationally quite cheap, one just needs a data type with enough precision. And it turns out that $1$ was correct given a particular (outdated) interpretation of the question.

$\endgroup$
  • $\begingroup$ While that's a sensible answer, I can't imagine the calculation taking as long as described... On the other hand, I fail to see how anything of the form n^n could give the an output that's just a mirrored version of the original, as length would increase. Hence me asking in the comments whether we were looking for a repeting form of those numbers.. $\endgroup$ – Tim Couwelier Oct 15 '14 at 8:45
  • $\begingroup$ @TimCouwelier Well, what I understood is that - 1) We put a 6-digit number. 2) 6 digits were printed by the time we got back. The 2 numbers form a palindrome. Yes, I know, I thought about the issue of taking too short a time to calculate; we are making assumptions about the power of the device $\endgroup$ – d'alar'cop Oct 15 '14 at 8:50
  • 1
    $\begingroup$ It seems the picture is wrong after all. Too bad. I bruteforced it also and found that 43331^43331 = 13334724..., 4239^4239 = 93244415..., 3033^3033 = 33038511... and 1^1 = 1. Since '3' was excluded, the 1 would have been the only solution. $\endgroup$ – Florian F Oct 15 '14 at 21:40
  • $\begingroup$ Yep - the picture was wrong (but you can always trust Ernie's words), sorry about that. $\endgroup$ – Penguino Oct 15 '14 at 22:36
  • 1
    $\begingroup$ @FlorianF Just out of interest, by what means did you brute-force it? $\endgroup$ – d'alar'cop Oct 16 '14 at 2:05

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.