Cariad's Code Blog

Tupper’s Self-Referential Formula in Python

by Cariad EcclestonSunday January 12, 2020 • 9 minute read

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:

\begin{align} { 1 \over 2 } < \left \lfloor \mathrm{mod} \left ( \left \lfloor {y \over 17} \right \rfloor 2 ^ { -17 \lfloor x \rfloor - \mathrm{mod}( \lfloor y \rfloor, 17)}, 2 \right ) \right \rfloor \end{align}

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

\begin{align} { 1 \over 2 } \end{align}

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

\begin{align} 17y \end{align}

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

\begin{align} < \end{align}

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

\begin{align} \left \lfloor x \right \rfloor \end{align}

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:

\begin{align} \left \lfloor {x \over y} \right \rfloor \end{align}

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

Floor:
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:

Floor division:
4 // 5
# 0

13 // 3
# 4

Modulo

\begin{align} \mathrm{mod} \left ( 9, 4 \right ) \end{align}

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

\begin{align} 2 ^ 3 \end{align}

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:

\begin{align} 2 × 2 × 2 \end{align}

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 10112 which – you can imagine – is pretty big.

Calculating 10112:
import math
math.pow(101, 12)
# 1.1268250301319698e+24

10112 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 10112 is equal to 10112 + 1.

Testing equality with low-precision numbers:
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():

Testing equality with high-precision numbers:
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:

Precision reduced to 17 digits:
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:

\begin{align} { 1 \over 2 } < \left \lfloor \mathrm{mod} \left ( \left \lfloor {y \over 17} \right \rfloor 2 ^ { -17 \lfloor x \rfloor - \mathrm{mod}( \lfloor y \rfloor, 17)}, 2 \right ) \right \rfloor \end{align}

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:

A very special k:
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!

Plotted Tupper’s Self-Referential Formula (scroll right):
\begin{align} { 1 \over 2 } < \left \lfloor \mathrm{mod} \left ( \left \lfloor {y \over 17} \right \rfloor 2 ^ { -17 \lfloor x \rfloor - \mathrm{mod}( \lfloor y \rfloor, 17)}, 2 \right ) \right \rfloor \end{align}
                ██                                      ██                                ██  ████  ██          ██                                ██    ██  ██          ██        ██  ████  ██            ██      ██
                ██                                      ██  ██            ██              ██    ██  ██          ██                                ██    ██  ██          ██        ██    ██  ██            ██      ██
████            ██                                    ██    ██            ██        ████  ██    ██  ██  ██  ██  ██  ████  ████████    ██████  ██████  ██    ██  ██  ██  ██        ██    ██    ██            ██    ██
  ██            ██                                    ██    ██    ██  ██  ██              ██  ██    ██    ██    ██        ██  ██  ██  ██  ██  ██  ██  ██    ██  ██  ██  ██        ██  ██      ██            ██    ██
  ██            ██                                    ██    ██    ██  ██  ██              ██  ██    ██  ██  ██  ██        ██  ██  ██  ██████  ██████  ██    ██    ██    ██        ██  ██      ██            ██    ██
  ██            ██                              ██  ██      ██      ██    ██    ████                ██          ██                                    ██    ██  ██      ██    ██              ██      ████    ██  ██
██████      ██  ██                              ██  ██      ██    ██      ██  ██    ██              ██          ██                                      ██  ██          ██    ██            ██      ██    ██  ██  ██
          ██    ██  ████  ██      ████      ██████  ██      ██            ██      ██                ██████  ██████                                      ██  ██████  ██████  ██              ██          ██    ██  ██
██████  ██      ██  ██  ██  ██  ██    ██  ██    ██  ██      ██  ████████  ██    ██                                                                                                                    ██      ██  ██
          ██    ██  ██  ██  ██  ██    ██  ██    ██  ██      ██            ██  ██                                                                                                                    ██        ██  ██
████        ██  ██  ██  ██  ██    ████      ██████  ██      ██  ██  ████  ██  ████████                                                                                                              ████████  ██  ██
    ██          ██                                  ██      ██  ██    ██  ██                                                                                                                    ██            ██  ██
  ██            ██                                    ██    ██  ██    ██  ██                                                                                                                    ██          ██    ██
██              ██                                    ██    ██  ██  ██    ██                                                                                                                  ██            ██    ██
██████          ██                                    ██    ██  ██  ██    ██                                                                                                                                ██    ██
                ██                                      ██  ██            ██                                                                                                                              ██      ██
                ██████                                  ██  ██████    ██████                                                                                                                              ██  ██████

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!