## Ramanujan, Z3 and the number 1729

There’s this anecdote about **Ramanujan**, one of the brightest mathemacian who lived shortly between 1887 and 1920:

```
I remember once going to see him when he was ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavourable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways."
```

So apparently:

- $1729 = a^3 + b^3 = c^3 + d^3$, with $(a, b) \neq (c, d)$
- it is the smallest number to have this property

We can verify this by hand, and it’s only a matter of time before you reach the same result.

We can also write some code, or… we can throw the heavy machine and use a solver for this. Z3 is great at this, and the book SAT/SMT by example is a great introduction on the topic of theorem proving. It comes with complete examples, so it’s great if maths

Given **a description of the problem**, Z3 can minimize the solution for us. That’s the awesome part: all you have to do is proprerly describe the problem, and z3 will solve it.

Let’s take an example with a system of equations:

```
from z3 import *
# This program solves the following system of equation
# 3x + 2y - z = 1
# 2x - 2y + 4z = -2
# -x + 0.5y - z = 0
# example from https://yurichev.com/writings/SAT_SMT_by_example.pdf
x, y, z = Reals('x y z')
s = Solver()
s.add(3*x + 2*y - z == 1)
s.add(2*x - 2*y + 4*z == -2)
s.add(-x + 0.5*y -z == 0)
print(s.check())
print(s.model())
```

We only said that our problem involves `x`

, `y`

and `z`

, we said there are 3 equations linking them, but we never implemented an algorithm to solve that. And in a few seconds, it will display the solution

```
[z = -2, y = -2, x = 1]
```

So, we can do the same thing to

```
from z3 import *
a, b, c, d = Ints('a b c d')
cube_sum = Int('cube_sum')
s = Optimize()
s.add(a > 0)
s.add(b > 0)
s.add(c > 0)
s.add(d > 0)
s.add(a < 20)
s.add(b < 20)
s.add(c < 20)
s.add(d < 20)
s.add(And(cube_sum == (a * a * a) + (b * b * b)))
s.add(And(cube_sum == (c * c * c) + (d * d * d)))
s.add(And(a != c, a != d, b != c, b != d))
s.minimize(cube_sum)
s.check()
m = s.model()
print(m)
def debug(u, v):
print("{}^3 + {}^3 = {}".format(m[u].as_long(), m[v].as_long(), m[u].as_long() ** 3 + m[v].as_long() ** 3))
debug(a, b)
debug(c, d)
```

And again, it finds the solution.

```
$ python cube_sum.py
[d = 12, c = 1, b = 10, a = 9, cube_sum = 1729]
9^3 + 10^3 = 1729
1^3 + 12^3 = 1729
```

Here it is, $1729 = 9^3 + 10^3 = 1^3 + 12^3$.

Interestingly, you need to setup some upper bounds to the problem:

```
s.add(a < 20)
s.add(b < 20)
s.add(c < 20)
s.add(d < 20)
```

Without those bounds, the search space is way to big and you won’t find a solution in a reasonnable time. That’s an issue because it means you have to know beforehand some elements about the search space, which you may not always have.

See a typo ? You can suggest a modification on Github.