Shiny cryptarithm

Question

Here's a little puzzle I made today:

$$\sqrt{\text{ILLUMINATE}^{\mathstrut}} = \text{LIGHT}$$

Most usual rules of alphametic puzzles apply here: the same letter always represents the same digit, and numbers don't start with $0$s. However, here it is possible for two different lettters to represent the same digit.

Hoping to see a solution that includes its solving steps (and doesn't use computers to brute-force the answer). I'm sure I will—there are lots of bright people here!

Answer 1

The solution is

$\sqrt{5772656484} = 75978$, and is unique.

Because different letters don't have to be different digits, the problem might as well be $\sqrt{a}= b$ where a = XYY??X??Z? and b = YX??Z

which is not much information at all. However, the prefixes are still very restrictive. We notice that the square is 10 digits long (an even number), so $b/10^4 > \sqrt{10}$.

Reduction to 89 cases:

Checking relevant prefixes $b/10^3$, we see $75^2 = 5625$ and $76^2 = 5776$ so there are feasible cases here due to the X and Y pattern. Refining, we find that $b = 75961 \to 75999$ inclusive are possible because $75961^2 = 5770073521$. There are 39 cases (...A).

Similarly, I found that $b= 99950 \to 99999$ are possible because $99950^2 = 9990002500$. There are 50 cases (...B).

There are no other candidates. I only had to do a dozen or so 2-digit squares and two square roots of 10-digit numbers with the help of a calculator.

To further narrow down to 4+3+5 = 12 cases:

I checked the squares of $50$ to $99$ and found that, besides multiples of ten, only $82^2 = 6724$ and $78^2 = 6084$ that fit the Z pattern. The non-multiples-of-ten give 2x2 = 4 cases across case A and case B. The multiples of ten give 3 cases in case A and 5 cases in case B.

Then taking the squares of the 12 candidates yielded the unique solution.

Answer 2

Early digits:

To get the right number of digits, $\overline{LIGHT} \ge \sqrt{1,000,000,000}$ so $\overline{LIGHT} \ge 31623$ and $\overline{LI} \ge 31$. Clearly we need $\overline{LI} \times \overline{LI} \approx \overline{ILLU}$. It certainly can't be more than $\overline{ILLU}$, otherwise $\overline{LI,000} \times \overline{LI,000}$ is already too large to make $\overline{I,LLU,MIN,ATE}$. A little less is okay, since we will be carrying from $\overline{LIGHT}^2 - \overline{LI000}^2 = 2 \times \overline{LI000} \times \overline{GHT} + \overline{GHT}^2$. This is at most $99,999^2 - 99,000^2 = 2 \times 99,000 \times 999 + 999^2 = 198,800,001$. So it looks like we are carrying at most $198$ onto $\overline{LI}^2$ to make $\overline{I,LLU}$, hence $1000I + 110L + U - 198 \le (10L + I)^2 \le 1000I + 110L + U$. We want $100L^2 \approx 1000I$ so $L^2 \approx 10I$. If $L^2 \ge 10(I+1)$ then $\overline{LI}^2 > 1000(I+1)$ and our leading digit is too big to be $I$ even before we consider any carrying! If $L^2 \le 10(I-2)$ then $\overline{LI}^2 \le 1000(I-2) + 20IL + I^2$ but $20IL + I^2 \le 20 \times 9 \times 9 + 9^2 = 1701$ so even if we carry an extra $198$ from $\overline{GHT} \times \overline{GHT}$ this only adds at most one onto the thousands digit, and again we cannot make $I$ there. Now $10(I-2) < L^2 < 10(I+1)$ leaves us only a few cases to check, as we already know $L \ge 3$. For example if $L=7$, then $L^2=49\approx 10 \times 5$. In the narrow range of possible $I$ values near $5$, we find $75^2 = 5625$ which is tolerably near $5770$ (check by adding $198$; a more precise check, since $198$ is the most extreme possible carry, is to calculate $\sqrt{5,770,000,000}$ and note the smallest integer producing those first three digits when squared is $\overline{LIGHT}\ge 75,961$, hence $\overline{LI}=75$ is feasible). When $L=8$ and $L^2=64$ (roughly six or seven times ten), we get a near miss with $I=7$, $\overline{LI}^2 = 87^2 = 7569$. Even adding $198$ can't quite make the first three digits $788$. When $L=9$, $I=9$ we find another possibility, $99^2 = 9801$ which is within $198$ of $9990$ (more precisely, checking $\sqrt{9,990,000,000}$ shows we need $\overline{LIGHT} \ge 99,950$). Note that the inequalities from our precise checks have revealed that $\overline{LIG}$ is either $759$ or $999$: the middle digit has to be nine to get the required first two digits as well as ensuring $\overline{LIGHT}\ge 75,961$ or $99,950$.

Eliminating over half the remaining cases:

Every value of $\overline{\color{pink}{L}\color{red}{I}GH\color{blue}{T}}$ from $75,961$ to $75,999$ and from $99,950$ to $99,999$ squares to give the first three digits $\overline{\color{red}{I}\color{pink}{LL}}$ of $\overline{\color{red}{I},\color{pink}{LL}U,M\color{red}{I}N,A\color{blue}{T}E}$, so among these 89 possibilities we need to pick out the ones which give the repeated $\color{red}{I}$ in the tens of thousands position, and the $\color{blue}{T}$ in the tens position. We can write every value of $\overline{LIGHT}$ from $99,950$ to $99,999$ in the form $100,000 - X$ where $1 \le X \le 50$. Then we have $\overline{LIGHT}^2 \equiv X^2 \pmod{100,000}$ so the final five digits of $\overline{LIGHT}^2$ are at most $50^2 = 02,500$. The tens of thousands position is always occupied by a zero (e.g. $9\color{red}{9},964^2 = \color{red}{9},992,8\color{red}{0}1,296$) rather than the necessary nine. So the "repeated I" condition can only be fulfilled by $\overline{LIGHT}$ from $75,961$ to $75,999$, and we now know $\overline{HT} \ge 61$. Unfortunately the repeated $I = 5$ doesn't give us an upper bound for $\overline{HT}$: e.g. we need $\overline{75,9HT}^2 < 5,779,960,000$ but this only gives us $\overline{75,9HT} \le 76,026$, which we knew already. We might instead hope that the final $T$ in $\overline{LIGHT}$ doesn't affect that tens of thousands of position much so, if we are lucky, we can concentrate first on finding $H$ that gives us the second $I$. Sadly this doesn't work either, e.g. $75,999^2 - 75,998^2 = 151,997$ so it's clear a one digit change to $T$ can have a big influence on the tens of thousands position. So it looks like we will have to concentrate on the final two digits.

Final two digits:

We need the last two digits of $\overline{H\color{blue}{T}}^2 = (10H + T)^2 = 100H^2 + 20HT + T^2$ to be $\overline{\color{blue}{T}E} = 10T + E$, i.e. after squaring the units digit must end up in the tens position. That $T$ in tens position must come from the final digit of $2HT$ plus (modulo ten) any carried digit from $T^2$. We already know $H \ge 6$. If $0 \le T \le 3$ there is no carry from the $T^2$ so we just need the last digit of $2HT$ to be $T$. That last digit is clearly even, so $T=0$ or $T=2$. The former guarantees $\overline{TE}=00$ so works for any $H$. We need to check $7\color{red}{5},97\color{blue}{0}^2 = \color{red}{5},771,4\color{red}{4}0,9\color{blue}{0}0$, $7\color{red}{5},98\color{blue}{0}^2 = \color{red}{5},772,9\color{red}{6}0,4\color{blue}{0}0$, and $7\color{red}{5},99\color{blue}{0}^2 = \color{red}{5},774,4\color{red}{8}0,1\color{blue}{0}0$ but none of them give the repeated $I=5$ in the tens of thousands position. If $T=2$, we need the last digit of $2HT = 4H$ to be $2$. This happens when $H = 3$ (but we know $H \ge 6$) or $H = 8$, so we need to check $7\color{red}{5},98\color{blue}{2}^2 = \color{red}{5},773,2\color{red}{6}4,3\color{blue}{2}4$ which also doesn't work. What if the square carries? If $T=4$ the carry from $T^2$ is $1$, so we need the last digit of $2HT = 8H$ to be $4-1 = 3$. This is impossible as that last digit is always even, so the tens digit of $\overline{H4}^2$ will be one plus an even number, hence always odd (e.g. $8\color{blue}{4}^2 = 70\color{blue}{5}6$). If $T=5$ the carry from $T^2$ is $2$, but the units digit of $2HT = 10H$ must be zero, hence the tens digit will be $2 \ne 5$ (e.g. $8\color{blue}{5}^2=72\color{blue}{2}5$). If $T=6$ the $T^2$ carries $3$ so we need $2HT = 12H$ to end in $6-3=3$. This can't happen, as $12H$ will be even so can't end in $3$. The tens digit of $\overline{H6}^2$ will be three plus an even number, so always odd (e.g. $8\color{blue}{6}^2=73\color{blue}{9}6$). If $T=7$ the $T^2$ carries $4$ so we need $2HT = 14H$ to end in $7-4=3$: same problem, but this time the tens digit of $\overline{H7}^2$ will be four plus an even number, so always even (e.g. $8\color{blue}{7}^2=75\color{blue}{6}9$). If $T=8$ the $T^2$ carries $6$ so we need $2HT = 16H$ to end in $8-6=2$. We only really need to look at the last digit of $6H$, which is $2$ if $H=2$ (too small) or $H=7$. We check $7\color{red}{5},97\color{blue}{8}^2 = \color{red}{5},772,6\color{red}{5}6,4\color{blue}{8}4$ (which works, note repeated $I=5$). If $T=9$ the $T^2$ carries $8$ so we need $2HT = 18H$ to end in $9-8=1$, which can't happen as it's even. The tens digit of $\overline{H9}^2$ will be eight plus an even number, so always even (e.g. $8\color{blue}{9}^2=79\color{blue}{2}1$).

Hence the only solution is

$\color{pink}{7}\color{red}{5},97\color{blue}{8} = \sqrt{\color{red}{5},\color{pink}{77}2,6\color{red}{5}6,4\color{blue}{8}4}$

An observation which, in hindsight, gives a far simpler solution:

Out of curiosity I have gone back and tested the tens of thousands digit for every square from $75,961^2$ to $75,999^2$ and the desired five turns up only twice, for $\color{pink}{7}\color{red}{5},97\color{blue}{6}^2 = \color{red}{5},\color{pink}{77}2,3\color{red}{5}2,5\color{blue}{7}6$ (fails on the T criterion) and $\color{pink}{7}\color{red}{5},97\color{blue}{8}^2 = \color{red}{5},\color{pink}{77}2,6\color{red}{5}6,4\color{blue}{8}4$ (the only solution). So if only we'd been able to identify them earlier, based on the tens of thousands digits, there'd only have been two cases to check! They're suspiciously similar values of $\overline{LIGHT}$, just two apart. In fact it turns out the tens of thousands digit alternates, originally between 7 and 2 a couple of times, then 8 and 3, then 9 and 4, then 0 and 5, then 1 and 6, and eventually gets round to 4 and 9. So it seems I was premature to give up on the tens of thousands digit: but it was by no means "obvious" that this digit would either stay the same or increment by one when $\overline{LIGHT}$ is incremented by two. For $1 \le X \le 39$, we see $(75,960 + X + 2)^2 - (75,960 + X)^2$ factors as $2(151,922 + 2X) = 303,844 + 4X$ were $X$ is too small to make much difference. The zero in the tens of thousands column explains why incrementing $X$ by two rarely changes the tens of thousands column of the square. Based on the thousands digit being three, we are going to have to perform this double increment about three times to tick the tens of thousands digit over. On the other hand, incrementing $X$ by one just gives $(75,960 + X + 1)^2 - (75,960 + X)^2 = 151,921 + 2X$; adding the five in the tens of thousands column explains the alternating behaviour I noted above. Starting from $75,960^2 = 5,769,9\color{red}{2}1,600$ the digit we want is "only just" two; in a breach of conventional notation I'll call it $2.16$ and this increments by about $0.38$ for each double-increment of $X$. Then $(5- 2.16)/0.38 \approx 7.5$ and $(6- 2.16)/0.38 \approx 10.1$ so we want eight or nine double-increments, i.e. an increment of either 16 or 18. This is exactly the $75,976$ and $75,978$ we sought! Eventually this wraps around to give five again, but $(15- 2.16)/0.38 \approx 33.8$ comes far too late. On the other hand, starting from $75,961^2 = 5,770,0\color{red}{7}3,521$ you have about $7.35$ where we want a five: that would also need to wrap right around, and $(15 - 7.35)/0.38 \approx 20.1$. This approximation isn't perfect, notably the increment of $0.38$ is actually increasing as $X$ gets bigger, but it's not too bad: twenty double-increments of $75,961$ gets us to $76,001$ which squares to $5,776,1\color{red}{5}2,001$, whereas nineteen would get to $75,999$, which squares to $5,775,8\color{red}{4}8,001$ so falls just short. Could we have spotted this method to sort out the tens of thousands digit, without having calculated a bunch of terms to spot a pattern? In retrospect, it would have been a good idea to look at the derivative of $(75,980 + X)^2$ at $X=0$ (note I have recentred $X$ to the middle of our valid range, which makes the approximation a bit more accurate) and found $151,960$. The $5$ indicates the alternating behaviour and suggests we should double to $303,920$ so our digit increments by about $0.39$ whenever $X$ increases by $2$. Moreover, the second derivative is tiny compared to the first (just two!) which explains why the linear approximation to the digit's behaviour works so well.

With this insight, can we make something more like an algorithm we can iterate through to find the solutions and near-solutions, rather than do lots of case-checking?

To see how we could try and jump between solutions or near-solutions where multiple conditions need to be fulfilled, I want to go back to the problem of the early digits. We were trying to arrange something like $\overline{AB}^2 = \overline{CDEF}$ where $A = D$ and $B = C$, at least approximately. (The choice of letters no longer bear any relation to the original problem, it's just to make it easier to keep track of what letter goes in which position.) Our valid range of $\overline{AB}$ runs from $31$ to $99$ so let's start off centred at $(31 + 99)/2 = 65$, and put $\overline{AB} = 65 + X$. Then we find the following derivatives at $X = 0$: $\frac{dA}{dX} = 0.1$ and $\frac{dB}{dX} = 1$ (both these increments will be true by definition), $\frac{d(65 + X)^2}{dX} = 2 \times 65 = 130$ and so $\frac{dC}{dX} = 0.13$ and $\frac{dD}{dX} = 1.3$ (these increments will get inaccurate as we move away from $X = 0$ i.e. $\overline{AB} = 65$ so we may need to recentre later). At $X = 0$ we have $A = 6.5$, $B = 5$, $\overline{AB}^2 = 65^2 = 4224$, $C = 4.224$, $D = 2.24$. Presently we have differences $D-A = 2.24 - 6.5 = -4.26$ and $B-C = 5 - 4.224 = 0.776$ which we'd prefer to both be near zero, but which are currently "out of synch" by a quantity I'll define as $Y = (D - A) - (B - C) = -4.26 - 0.776 = -5.036$. We also have derivatives $\frac{d(D-A)}{dX} = 1.3 - 0.1 = 1.2$ and $\frac{d(B-C)}{dX} = 1 - 0.13 = 0.87$ and so we are getting back in synch at a rate $\frac{dY}{dX} = 1.2 - 0.87 = 0.33$ per increment of $X$. Our strategy is: (1) to enable both conditions to be simultaneously satisfied, use $\frac{dY}{dX}$ to jump somewhere $Y=0$ (or some other multiple of ten) to get us back in synch; (2) to improve accuracy, recentre $X$ about this point — probably unnecessary if we didn't jump far, but if we jumped a long way we may find $Y$ is still out of synch due to error in our linear approximation, and we need to do this then repeat the first step; (3) use the differences $D-A$ and $B-C$, and their rates of change, to find solutions or near-misses near this point; (4) if when we check solutions we found, it turns out the two conditions have got out of synch again, then repeat step (1). We had $Y = -5.036$ and $\frac{dY}{dX} = 0.33$, suggesting we jump forward $5.036/0.33 \approx 15$ from $65$ to get back in synch by recentring about $80$, or backward by $(10 - 5.036)/0.33 \approx 15$ to $50$. In this answer I will only show how working forwards takes us to the solutions or near-misses identified previously, but for completeness a full answer would work backwards to. Moving forward to $80$ we find $\frac{d(80 + X)^2}{dX} = 2 \times 80 = 160$. There have been substantial changes to $\frac{d(D-A)}{dX} = 1.6 - 0.1 = 1.5$, $\frac{d(B-C)}{dX} = 1 - 0.16 = 0.84$, and $\frac{dY}{dX} = 1.5 - 0.84 = 0.66$. We have $80^2 = 6400$ so $D - A = 4-8 = -4$ and $B - C = 0 - 6.4 = -6.4$, so are still out of synch by $Y = -4 - (-6.4) = 2.4$. Since $Y$ is increasing by $0.66$ with each increment of $X$, this suggests we should jump back by $2.4/0.66 \approx 4$ places. Recentring around $76$ gives $\frac{d(76 + X)^2}{dX} = 2 \times 76 = 152$ so this time there are only small changes to $\frac{d(D-A)}{dX} = 1.52 - 0.1 = 1.42$, $\frac{d(B-C)}{dX} = 1 - 0.152 = 0.848$, and $\frac{dY}{dX} = 1.42 - 0.848 = 0.572$. We have $76^2 = 5776$ so $D - A = 7.76-7.6 = 0.16$ and $B - C = 6 - 5.776 = 0.224$ so are basically back in sync ($Y = 0.16 - 0.224 = -0.064$). We have actually landed on a near-solution; going back one to $75$ will also yield small $|D - A|$ and $|B - C|$, with other near-misses at $74$ and $77$. Where are the next nearest solutions? We could go forwards by $(10 - 0.16)/1.42 \approx 6.9$ (based on $D - A$) or by $(10 - 0.224)/0.848 \approx 11.5$ (based on $B - C$): it's clear we will be a bit out of synch again since $D - A$ and $B - C$ are incrementing at different rates, but let's split the difference and go forwards by $9$ to $85$. (There is the option of going back from here too, but it would only take us back to about the place we came from.) Recentring about $85$, we have $\frac{d(85 + X)^2}{dX} = 2 \times 85 = 170$, $\frac{d(D-A)}{dX} = 1.7 - 0.1 = 1.6$, $\frac{d(B-C)}{dX} = 1 - 0.17 = 0.83$, $\frac{dY}{dX} = 1.6 - 0.83 = 0.77$, $85^2 = 7225$, $D - A = 2.25-8.5 = -6.25$, $B - C = 5 - 7.225 = -2.225$, $Y = -6.25 - (-2.25) = -4$. To resynch, jump forward by $4/0.77 \approx 5$ to $89$: $\frac{d(89 + X)^2}{dX} = 2 \times 89 = 178$, $\frac{d(D-A)}{dX} = 1.78 - 0.1 = 1.68$, $\frac{d(B-C)}{dX} = 1 - 0.178 = 0.822$, $\frac{dY}{dX} = 1.68 - 0.822 = 0.858$, $89^2 = 7921$, $D - A = 9.21-8.9 = 0.31$, $B - C = 9 - 7.921 = 1.079$, $Y = 0.31 - (1.079) = -0.769$. Again we are near a solution, with other nearish-misses at $90$, $88$, and $87$. For the next solution, move forward by $(10 - 0.31)/1.68 \approx 5.8$ (based on $D - A$) or by $(10 - 1.079)/0.822 \approx 10.9$ (based on $B - C$). Splitting the difference we jump by $8$ to $97$: $\frac{d(97 + X)^2}{dX} = 2 \times 97= 194$, $\frac{d(D-A)}{dX} = 1.94 - 0.1 = 1.84$, $\frac{d(B-C)}{dX} = 1 - 0.194 = 0.806$, $\frac{dY}{dX} = 1.84 - 0.806 = 1.034$, $97^2 = 9409$, $D - A = 4.09-9.7 = -5.61$, $B - C = 7 - 9.409 = -2.409$, $Y = -5.61 - (-2.409) = -3.201$. To resynch, jump forward again by $3.201/1.034 \approx 3$ to $100$: here we'll find the solutions or near-misses around $99$ we saw above.