# Lagrange's Four Square Cryptarithm

The French mathematician Lagrange proved that every natural number can be written as the sum of four squares.

This is true in the view of cryptarithms, too.

  SQUARE
SQUARE
SQUARE
+ SQUARE
--------
NUMBER


Each letter represents a unique digit.

• This should be shifted to Math.SE ... – pranav Feb 2 '15 at 16:08
• @pranav Why? What would be the purpose of the [verbal-arithmetic] tag, then? (Note that this isn't actually asking for a proof of anything; as I understand it, SQUARE and NUMBER are just six-digit strings, like any other cryptarithm.) – wchargin Feb 2 '15 at 20:45
• I think @pranav was joking. :-) – P.-S. Park Feb 3 '15 at 12:45
• @P.-S.Park , :) – pranav Feb 3 '15 at 16:16

From the last two positions, we see that $4\cdot(10R+E)\equiv 10E+R \bmod{100}$. This is equivalent to $39R\equiv6E\bmod{100}$, and further to $13R\equiv2E\bmod{100}$. Hence $R$ has to be even. Checking $R=0,2,4,6,8$, we see that only $R=8$ works.

We conclude that $R=8$ and that $E=2$, and that the carry over from the second column to the third column is $3$.

Since $4\cdot10^5\,S= 4\cdot S00000 < 4*\mbox{SQUARE} = \mbox{NUMBER} <10^6$, we conclude $4S<10$. The case $S=0$ would have zero as leading digit, and the case $S=2$ would collide with $S=E=2$.

We derive $S=1$.

We plug the detected values into the given equation and derive $4\cdot(1000+100Q+10U+A)+3=1000N+100U+10M+B$,
which simplifies to
$4003 -10M+ 4A-B = 1000N -400Q +60U.~~~ (*)$

The left hand side of equation ($*$) is at least $4003-90+0-9=3904$ and at most $4003-0+36-0=4039$. Furthermore, it is a multiple of $20$. Hence it lies between $3920$ and $4020$, which yields $196\le 50N-20Q+3U\le 201~~~ (**)$.

Now we distinguish several cases on $U$ to derive the following from $(**)$:

(1) If $U=0$, then $5N-2Q=20$. Then $N=6$ and $Q=5$.
(2) If $U=3$, then $5N-2Q=19$. Then $(N,Q)=(5,2)$ or $=(7,8)$; collisions.
(3) If $U\in\{4,5\}$, then $181<50N-20Q<189$. No solution.
(4) If $U\in\{6,7\}$, then $5N-2Q=18$. Then $(N,Q)=(4,1)$ or $=(6,6)$; collisions.
(5) If $U=9$, then $5N-2Q=17$. Then $(N,Q)=(5,4)$ which is fine, or $(N,Q)=(7,9)$ which has the collision $Q=U=9$.

All in all, this leaves us with two possible cases:

Case X: $(N,Q,U)=(6,5,0)$
Case Y: $(N,Q,U)=(5,4,9)$

In case X, equation $(*)$ boils down to $10M- 4A+B = 3$.

• If $M\ge4$, then $10M-4A+B\ge40-4\cdot9+0=4>3$; contradiction.
• If $M=3$, then $4A-B=27$ implies $(A,B)=(7,1)$ or $=(8,5)$ or $=(9,9)$; all three cases are collisions (with $B=S=1$, $B=Q=5$, $A=B=9$ respectively).
• If $M=0$, we have the collision $M=U=0$.

In case Y, equation $(*)$ boils down to $10M- 4A+B =63$.

• If $M\le5$, then $10M- 4A+B\le 50+B<63$; contradiction.
• If $M=6$, we get $B=4A+3$; this leaves $(A.B)=(7,1)$ with the collision $B=S=1$ and the good solution $(A,B)=(0,3)$.
• If $M=7$, we get $4A-B=7$. This leaves the cases $(A.B)=(2,1)$, $(3,5)$, $(4,9)$ which respectively collide with $B=S=1$, $B=N=5$, $A=Q=4$.
• If $M=9$,we get $4A-B=27$. This leaves the cases $(A.B)=(7,1)$, $(8,5)$, $(9,9)$ which respectively collide with $B=S=1$, $B=N=5$, $A=B=9$.

Summary:
Only a single branch in this analysis has led to a solution:
$R=8$ $E=2$ $S=1$; $(N,Q,U)=(5,4,9)$; $M=6$ and $(A.B)=(0,3)$.

Square has a value of 149082

Number has a value of 596328

The way I obtained my answer was, that in my python class I created a program to solver word puzzles, such as SEND+MORE==MONEY, and this was just another one of those. So I just ran my program with that puzzle.

Python3 code to solve the puzzle:

import re
import itertools

def solve(puzzle):
words = re.findall('[A-Z]+', puzzle.upper())
unique_characters = set(''.join(words))
assert len(unique_characters) <= 10, 'Too many letters'
first_letters = {word[0] for word in words}
n = len(first_letters)
sorted_characters = ''.join(first_letters) + \
''.join(unique_characters - first_letters)
characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
zero = digits[0]
for guess in itertools.permutations(digits, len(characters)):
if zero not in guess[:n]:
equation = puzzle.translate(dict(zip(characters, guess)))
if eval(equation):
return equation

if __name__ == '__main__':
import sys
for puzzle in sys.argv[1:]:
print(puzzle)
solution = solve(puzzle)
if solution:
print(solution)


This code is not the one I wrote, but does the same thing.