# Demystifying Tupper’s formulation – Eli Bendersky’s web site

*by*Phil Tadros

A book I was recently reading talked about a

mathematical curiosity I have not seen earlier than – Tupper’s self-referential

formula.

There are some sources about it on-line, however this submit is *my* try to

clarify the way it works – together with an interactive implementation you may strive

within the browser.

## Tupper’s formulation

Right here is the formulation:

We wish to plot this formulation, however how?

For this goal, it is extra helpful to consider Tupper’s formulation not as a

operate however as a *relation*, within the mathematical sense. In Tupper’s paper

it is a relation on , which means that it is a set of pairs

in that fulfill the inequality.

For our job we’ll use discrete indices for *x* and *y*, so the relation is

on . We’ll plot the relation by utilizing a darkish pixel (or

sq.) for a `x,y` coordinate the place the inequality holds and a light-weight pixel

for a coordinate the place it would not maintain.

The “mind-blowing” truth about Tupper’s formulation is that when plotted for

a sure vary of *x* and *y*, it produces this:

Word that whereas *x* runs within the inclusive vary of 0-105 on the plot, *y* begins

at a mysterious *Ok* and ends at *Ok+16*. For the plot above, *Ok* must be:

```
4858450636189713423582095962494202044581400587983244549483
0930850619347047088099284506447698655243648499972470249151
1911041160573917740785691975432657185544205721044573588368
1829823754139634338225199452191651284348332905131193199953
5024137587652392648746133949068701305622958132194811136853
3953556529085002387509285689269455597428154638651073004910
6723058933586052544096664351265349363643957125565695936815
1843348576052669401612512669514215505395545191537854575257
5659074054015792900176596796548006442782913148854825991472
1248506352686630476300
```

The amazement subsides barely after we uncover that for a special *Ok* ,

we get a special plot:

And, in truth, this formulation can produce any 2D grid of 106×17 pixels, given the

proper coordinates. Because the formulation itself is so easy, it’s fairly obvious

that the worth of *Ok* is the important thing right here; these are enormous numbers with tons of of

digits, so clearly they encode the picture data one way or the other. Learn on to see

how this truly works.

## A JavaScript demo

I’ve carried out a easy on-line demo of plotting the Tupper formulation – obtainable

at https://eliben.github.io/tupperformula/ (with source code on GitHub). It was used to supply the pictures

proven above. The code is pretty simple, so I am going to simply give attention to the

fascinating half.

The core of the code is a 2D grid that is plotted for *x* operating from 0 to

105 and *y* from *Ok* to *Ok+16* (each ranges inclusive). The grid is populated

each time the quantity adjustments:

```
const GridWidth = 106;
const GridHeight = 17;
let Ok = BigInt(Knum.worth);
for (let x = 0; x < GridWidth; x++) {
for (let y = 0; y < GridHeight; y++) {
Grid.setCell(x, y, tupperFormula(BigInt(x), Ok + BigInt(y)));
}
}
```

Word using JavaScript’s `BigInt` varieties right here – very helpful when dealing

with such enormous numbers. Right here is `tupperFormula`:

```
operate tupperFormula(x, y) {
let d = (y / 17n) >> (17n * x + y % 17n);
return d % 2n == 1n;
}
```

It appears to be like fairly completely different from the mathematical formulation on the prime of this submit;

why? As a result of – as talked about earlier than – whereas Tupper’s unique formulation works on

actual numbers, our program solely wants the discrete integer vary of

`x in [0, 105]` and `y in [K, K+16]`. Once we cope with discrete numbers,

the formulation might be simplified tremendously.

Let’s begin with the unique formulation and simplify it step-by-step:

Initially, since *x* and *y* are pure numbers, the ground operations on

them do not do something, so we will drop them (together with on the division by

17, if we simply assume integer division that rounds down by default):

Subsequent, since the results of the operation for a pure *N* is

both 0 or 1, the comparability to half is only a fancy means of claiming “equals 1”;

we will exchange the inequality by:

Word the destructive energy of two; multiplying by it’s the identical as dividing by its

constructive counterpart. One other strategy to categorical division by for pure

numbers is a bit shift proper by *p* bits. So we get the code of the

`tupperFormula` operate proven above:

```
let d = (y / 17n) >> (17n * x + y % 17n);
return d % 2n == 1n;
```

## How the Tupper formulation works

The distillation of the Tupper to JS code already peels off a number of layers of

thriller. Let’s now take away the remainder of the curtain on its inside workings.

I am going to begin by explaining the right way to take a picture we would like the formulation

to supply and encode it into *Ok*. Listed here are the primary three columns of the

Tupper formulation plot:

Every pixel within the plot is transformed to a bit (0 for mild, 1 for darkish). We

begin on the backside left nook (*x=0* and *y=Ok*), which is the LSB

(least-significant bit) and transfer up by means of the primary column; after we attain the

prime (*x=0* and *y=Ok+16*), we proceed from the underside of the subsequent column

(*x=1* and *y=Ok*). Within the instance above, the primary bits (from lowest to highest)

of the quantity are:

```
00110010101000100 00101010101111100 ...
```

As soon as we’re finished with the entire quantity (106×17 = 1802 bits), we convert it to

decimal – let’s name this quantity *IMG*, and multiply by 17. The result’s *Ok*.

Now again to `tupperFormula`, the way it decodes the picture again from

*x* and *y* (recall that *y* runs from *Ok* to *Ok+16*). Let’s work by means of

the primary coordinate intimately:

For *x=0* and *y=Ok*, in `tupperFormula` we get:

```
d = (y/17) >> (17x + ypercent17)
...
substitute x=0, y=Ok (and recall that Ok = IMG * 17)
...
d = IMG >> 0
```

In different phrases, *d* is the bottom little bit of *IMG* – the bottom little bit of our picture!

We will proceed for *x=0* and *y=Ok+1*:

```
d = (y/17) >> (17x + ypercent17)
...
substitute x=0, y=Ok+1 (and recall that Ok = IMG * 17)
...
d = IMG >> 1
```

Right here *d* is the second lowest little bit of *IMG*. The sample ought to be clear by now.

```
d = (y/17) >> (17x + ypercent17)
...
x=0 y=Ok+2: IMG >> (0 + 2)
x=0 y=Ok+3: IMG >> (0 + 3)
...
x=0 y=Ok+16 IMG >> (0 + 16)
x=1 y=Ok: IMG >> (17 + 0)
x=1 y=Ok+1: IMG >> (17 + 1)
x=1 y=Ok+2: IMG >> (17 + 2)
```

The formulation merely calculates the proper little bit of *IMG* given *x* and *y*, utilizing

a modular arithmetic trick to “fold” the 2D *x* and *y* right into a 1D

sequence (that is simply customary column-major layout).

Because of this the formulation can plot any 106×17 grid, given the appropriate *Ok*. Within the

formulation, 17 shouldn’t be some piece of magic – it is simply the peak of the grid. As an

train, you may modify the formulation and code to plot bigger or smaller grids.

As a bonus, the JavaScript demo can even encode a grid again to its

consultant *Ok*; this is the code for it:

```
// Calculate Ok worth from the grid.
operate encodeGridToK() {
let kval = BigInt(0);
// Construct up Ok from MSB to LSB, scanning from the top-right nook down and
// then transferring left by column.
for (let x = GridWidth - 1; x >= 0; x--) {
for (let y = GridHeight - 1; y >= 0; y--) {
kval = 2n * kval + BigInt(Grid.getCell(x, y));
}
}
return kval * 17n;
}
```

It constructs *Ok* beginning with the MSB, however in any other case the code is

simple to observe.

## Background

The formulation was first describe by Jeff Tupper in a 2001 paper titled

“Dependable Two-Dimensional Graphing Strategies for Mathematical Formulae with Two

Free Variables”. The paper itself focuses on strategies of exactly graphing

relations and presents a number of algorithms to take action. This formulation is described

in passing in part 12, and introduced as follows:

And Determine 13 is:

Curiously, the *Ok* supplied by Tupper’s paper renders the formulation flipped

on each the *x* and *y* axes utilizing the usual grid used on this submit .

Because of this my JavaScript demo has flip toggles that allow you to flip the axes of any

plot.

```
1445202489708975828479425373371945674812777822151507024797
1881396854908873568298734888825132090576643817888323197692
3440016667764749242125128995265907053708020473915320841631
7920255490054180047686572016997304663833949016013743197155
2099618114524978194501906835950051065780432564080119786755
6863142280259694206254096081665642417367403946384170774537
4273196064438999230103793989386750257869294552344763192918
6095761834543224800492172803334941981620674985447203819393
9738513848960476759782673313437697051994580681869819330446
336774047268864
```