# Tupper’s Self-Referential Formula in Python

This is the coolest formula you’ll see today. Let’s plot it in Python!

Ever since I saw The ’Everything’ Formula (aka Tupper’s Self-Referential Formula) by Numberphile, I’ve had a plan to code and plot it myself.

…wait, the video is *four years old* now? Perhaps I've been procrastinating just a smidge.

## The formula

Tupper’s Self-Referential Formula is a ton of fun:

To turn that formula into a graph, just replace *x* and *y* with the *(x, y)* coordinates of any point on a two-dimensional plane.

Since the formula contains a less-than operator, the values that you inject will make the statement either *true* or *false*. The right-hand side of the formula will be greater than *0.5*, or it won’t.

If the statement is *true*, draw a dot on your graph at those coordinates. If the statement is *false*, leave it blank. Repeat for your entire two-dimensional plane, and congratulations! You've plotted the formula.

But what’s the point? This is the *awesome* bit.

If your two-dimensional plane is large enough, this formula plots *every possible pattern* for a *106×17* grid. If you know where to look, you can find *anything*.

Awesome, right? Let’s code it!

## The maths you need to know

### Division

The horizontal line is a *division* operator. The example above is describing “one divided by two”, or *0.5*.

In Python, we divide with the `/`

symbol:

```
1 / 2
# 0.5
```

### Multiplication

When two numbers butt-up against each other – like *17* and *y* above – we *multiply* them. We tend not to use the *×* symbol in formulae. In Python, though, we multiply with the `*`

symbol:

```
2 * 3
# 6
```

### Less-than

This “pointer” is the *less than* operator. It tells us that the statement is *true* only if the value on the left is less than the value on the right. In Python, we use the `<`

symbol.

```
1 < 2
# True
2 < 1
# False
```

### Floor and floor division

The `⌊`

and `⌋`

symbols describe the *floor* function, which rounds the inner value down to the nearest integer. Even if the value is *0.9* and you feel like it should be rounded up, the floor function *always* rounds *down*.

Python has a `math`

package with a `floor`

function to perform this:

```
import math
math.floor(0.4)
# 0
math.floor(1.9)
# 1
```

Sometimes, you need to floor the result of a division like this:

You *could* do this long-form with a division inside a call to the `math.floor`

function:

```
math.floor(4 / 5)
# 0
```

…but you can do the division and floor all in one go with the `//`

symbol, which is the *floor division* operator:

```
4 // 5
# 0
13 // 3
# 4
```

### Modulo

`mod`

is short for the *modulo* function, which finds the *remainder* after a division.

In the example above, `mod`

calculates the amount remaining after *9* has been divided by *4* as many times as possible. The answer is *1* because *9* divides into *4* twice with *1* finally left over.

We write modulo statements in Python with the `%`

symbol:

```
9 % 4
# 1
10 % 4
# 2
11 % 4
# 3
12 % 4
# 0
```

### Exponents

When a number is written superscript next to another number, that's *exponentiation*. This tells us to multiply the first number by itself a given quantity – the second number, the *exponent* – of times.

For example, the statement above tells us to multiply *2* three times, like this:

In Python, we *could* perform this with the `math`

package’s `pow`

function:

```
import math
math.pow(2, 3)
# 8.0
```

We *could*, but we won’t. We’ll use something *better*, in the `decimal`

package.

## The “decimal” package

The formula deals with *incredibly* large values of *y*. Python is quite happy to accept the scale of these numbers, but it sacrifices precision.

We’ll need to deal with this. We need precision for this formula to work.

Let’s start with an example. With this code, we can ask Python to calculate *101 ^{12}* which – you can imagine – is

*pretty big*.

^{12}:

```
import math
math.pow(101, 12)
# 1.1268250301319698e+24
```

*101 ^{12}* is

*1,126,825,030,131,969,720,661,201*, but Python gave us

*1,126,825,030,131,969,*.

**800,000,000**The nine least-significant digits have been rounded and lost. To hold such a large number, Python is keeping only the *most-significant* digits.

But perhaps Python is just rounding the result for display, and it’s safely storing the fully-precise number behind-the-scenes?

We can test that. We can ask Python if *101 ^{12}* is equal to

*101*.

^{12}+ 1```
import math
math.pow(101, 12) == math.pow(101, 12) + 1
# True
```

A human being would probably tell you this statement is *false*. The second number is *1* bigger than the first, so they *can’t* be equal.

But, Python returns *true*. As far as Python can tell, both sides of the equation are the same. Python doesn’t hold the numbers to enough precision to be able to tell that the least-significant digits are different.

Since precision is essential for this formula, we’ll abandon Python’s `maths`

package for very-large numbers, and use the `decimal`

package instead.

This is *slightly* more complicated – there's *one* additional line of code to write – but the pay-off is precision.

So, let’s reproduce our test, but use the `decimal`

package’s `power()`

function instead of the `maths`

package’s `pow()`

:

```
from decimal import getcontext
ctx = getcontext()
ctx.power(101, 12) == ctx.power(101, 12) + 1
# False
```

The biggest difference here is the addition of a call to `getcontext()`

. A *context* is a set of rules about maximum, minimum, precision and rounding, and we don’t need to worry about it right now. Just know and accept that you need a context.

And yes, this example returns *false*! The precision of the `decimal`

calculation allows Python to see that we added *1*, and so the two sides of the equality check aren’t… well, *equal*.

The default `decimal`

context has a precision of 28 digits, which is significantly greater than the `math`

package. If we wanted to, we could reduce the precision of our context and replicate the previous result:

```
from decimal import getcontext
ctx = getcontext()
ctx.prec = 17
ctx.power(101, 12) == ctx.power(101, 12) + 1
# True
```

Great! So when we come to code the formula, we’ll use the `decimal`

package for our large numbers, and create a context with generous precision.

## The formula in Python

To recap, here’s the original formula:

In Python, I created a `Solver`

class and wrote the calculation out long-form for readability. Hopefully, you can see how the code and the formula line up.

```
from decimal import getcontext
class Solver:
def __init__(self):
self.ctx = getcontext()
self.ctx.prec = 1000
def solve(self, x, y):
fx = math.floor(x)
fy = math.floor(y)
exponent = (-17 * fx) - (fy % 17)
raised = self.ctx.power(2, exponent)
inner_rhs = (y // 17) * raised
mod_rhs = inner_rhs % 2
floor_rhs = math.floor(mod_rhs)
return 0.5 < frhs
```

Okay! Let’s run it!

## Plotting the formula to the console

Now that we can solve any *(x, y)* pair, plotting to the console is easy-squeezy.

```
solver = Solver()
for y in range(k, k+17):
for x in range(105, -1, -1):
if solver.solve(x, y):
print(u"\u2588\u2588", end='')
else:
print(" ", end='')
print()
```

Remember, the formula plots *106×17* grids, so we need a couple of loops to take us through *17* rows and *106* columns. There’s an outer loop that takes `y`

from *k* to *k+16* inclusive, and an inner loop that reverses the x-axis from 105 to 0 inclusive.

Then, for each *(x, y)* point, we ask the `Solver`

class to tell us whether or not that point should be marked or left clear, then do the deed with a `print`

statement. The `end=''`

argument just makes sure the `print`

doesn’t start a new line after each point, because we only want to do that at the end of each row.

`u"\u2588"`

is the Unicode code for a full block, and I’ve put two into each plot to make it square-r and easier to read.

But, wait. What’s *k*? *k* is the offset up the y-axis where we want to start plotting. If we started at 0, then the graph wouldn’t be interesting at all.

The *k* we’re excited by is this 543-digit beast:

```
960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719
```

Now you see why we need to care about the precision of large numbers!

Well, if we plug that *k* into our plotter, what do we get?

We get a copy of the formula! It plots itself! Fan-bloody-tastic!

```
██ ██ ██ ████ ██ ██ ██ ██ ██ ██ ██ ████ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██
████ ██ ██ ██ ██ ████ ██ ██ ██ ██ ██ ██ ████ ████████ ██████ ██████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██████ ██████ ██ ██ ██ ██ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ████ ██ ██ ██ ██ ██ ██ ██ ██ ████ ██ ██
██████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██
██ ██ ████ ██ ████ ██████ ██ ██ ██ ██ ██████ ██████ ██ ██████ ██████ ██ ██ ██ ██ ██
██████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ████████ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██
████ ██ ██ ██ ██ ██ ████ ██████ ██ ██ ██ ████ ██ ████████ ████████ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██ ██ ██ ██ ██
██████ ██ ██ ██ ██ ██ ██ ██ ██
██ ██ ██ ██ ██ ██
██████ ██ ██████ ██████ ██ ██████
```

## Try it yourself

If you’ve got Python 3 installed then you can install my `tupper`

package and plot your own graphs with just two commands:

```
pip3 install tupper --user
python3 -m tupper
```

Have a look at `python3 -m tupper --help`

to see options for changing *k* and the characters to plot. All the source code is on GitHub under cariad/py-tupper, too.

Have fun!