Ernie's Clockwork Calculator

Question

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!".

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

Answer 1

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

Answer 2

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:

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!

Answer 3

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.

Answer 4

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.