The formula that plots itself


< change language

By the end of this blog post I hope that you know how to make mathematical drawings and why the number $$N \approx 4.85845063618971342358209596 \times 10^{543}$$ is so special.

Given a function $f(x, y)$, how can you use it to make a drawing? Well, we just imagine the whole plane as a white, clean grid, and then we fill with black the squares at the positions $(x,y)$ such that $f(x,y) > \frac12$. In a way, it is as if the function $f$ is telling us whether to use white or black, i.e. to leave the square empty ($0$) or filled in ($1$).

(more rigorously, we divide the plane in unit squares, and we give each square the coordinates of its lower-left corner)

If we take, for example, $f(x, y) = x + y$, then square $(0,0)$ would be white because $f(0, 0) = 0 < \frac12$ but the squares $(0, 1)$ and $(1, 0)$ would be black because $f(0, 1) = f(1, 0) = 1 > \frac12$.

As another example, take $f$ to be this function: $$f(x, y) = \left\lfloor mod\left(\left\lfloor\frac{y}{17} \right\rfloor 2^{-17\lfloor x \rfloor - mod(\lfloor y \rfloor, 17)}, 2\right) \right\rfloor$$ where $\lfloor n \rfloor$ denotes the floor function and $ mod(a, b) $ denotes the modulo operator. This function looks way more interesting, doesn't it? Yes it does! And if you look in the right place, this is what is plotted by this function:


What is going on here..? The function I just showed you, called Tupper's self-referential formula, is a formula that plots itself! But you might be suspicious, because I said if you look in the right place. What is this place then?

Quite simply, define $N=$ 4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605626529915320311182856118951164066401426579727262440270286409619368825536815027849325692956320299303330714849102058741137034502, (a 544 digit long number). Then, the image I showed you is the rectangular area with lower-left corner $(0, N)$ and upper-right corner $(105, N + 16)$ (so it is a $106 \times 17$ rectangle). Quite impressive, right? Self references are always fun!

But that is not all... If you look hard enough, you can find literally anything inside that $106\times17$ rectangle! For example, taking $N=$ 677269797063266389145771001639366162904443300634759368354244105189144417475687924080590138582401925400953401198762670070868017028632609067495842127259345485889052110555312844858658969250766978033911456684637024394115209279287448522343527514061700072005928325124098808483476326307953390156875355289624192978628506335125351370018499785193486797521350328711540234844414805471938182060305235921541912512179523099720166772353828125144439537587189530425493554812515912471900753848603802337280, you can find the image in the beginning of the post, which I replicate here because I can:


Now the really important question is... How does one find such values for $N$? Well, you can watch this Numberphile youtube video, which was where I learned it... Or I can tell you all about it. You start with a $106\times17$ grid and you colour it (with black/white) the way you want. Then you will construct a bit sequence: you start on the top-right corner, and write down a $1$ if that square is black, $0$ if that square is white. Then you go down one square, and repeat. You do this column by column, top to bottom, right to left. When you finish, you convert your bit sequence to decimal and multiply it by $17$. That gives you the right position on the plot. In the video I linked, they tell you to start at the opposite end (lower-left) but then the plot will be flipped.

Of course doing this by hand is suicidal. What I did is create a program that lets me draw in a grid and then creates the number for me. Then, I created another small program that takes a number and draws the corresponding plot. Both programs (Python code and Windows executables) can be found in this Github repo. After drawing, press S to save the number to the file numbers.txt. To draw a number, first dump it in the file number2draw.txt and then run the drawing program.

In the comments below feel free to share your favourite number $N$!

If you liked this post, consider subscribing to the Mathspp newsletter and like it on Facebook.
Quando acabarem de ler este post espero que saibam fazer desenhos matemáticos e que saibam porque é que o número $$N \approx 4.85845063618971342358209596 \times 10^{543}$$ é tão especial.

Dada uma função $f(x,y)$, como é que a podemos usar para fazer um desenho? Imaginemos o plano como uma grelha branca, limpa; depois pintamos de preto os quadrados $(x,y)$ tais que $f(x,y) > \frac12$. Assim, o papel da função $f$ é atribuir uma cor a cada um dos quadrados, deixando-os brancos (com $0$) ou pretos (com $1$).

(de forma rigorosa, dividimos o plano em quadrados unitários, alinhados com os eixos e com vértices inteiros; atribuímos a cada quadrado as coordenadas do vértice inferior esquerdo)

A título de exemplo, se tomarmos $f(x, y) = x + y$ então o quadrado $(0,0)$ vai ficar branco, porque $f(0, 0) = 0 < \frac12$, mas os quadrados $(0, 1)$ e $(1, 0)$ ficam pretos porque $f(0, 1) = f(1, 0) = 1 > \frac12$.

Tomemos outro exemplo mais interessante, com a função $f$ dada pela seguinte expressão: $$f(x, y) = \left\lfloor mod\left(\left\lfloor\frac{y}{17} \right\rfloor 2^{-17\lfloor x \rfloor - mod(\lfloor y \rfloor, 17)}, 2\right) \right\rfloor$$ onde $\lfloor n \rfloor$ representa a função chão e $ mod(a, b) $ representa o módulo. Esta função parece muito mais promissora, não é? E é mesmo! Se procurarmos no sítio certo, isto é o que encontramos desenhado:


O que é que se está a passar..? Basicamente, a função $f$ que eu escrevi, chamada Tupper's self-referential formula, é uma fórmula que se desenha a si mesma! Para quem está a desconfiar de eu ter dito se procurarmos no sítio certo, esse sítio está definido de seguida:

Tomamos $N=$ 4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605626529915320311182856118951164066401426579727262440270286409619368825536815027849325692956320299303330714849102058741137034502, (um número com 544 dígitos) e agora consideramos o retângulo $106\times17$ que tem canto inferior esquerdo com coordenadas $(0, N)$ e canto superior direito com coordenadas $(105, N + 16)$. Bestial, não é? Auto referências são sempre divertidas, na minha opinião!

Mas esta não é a história completa... Se procurarmos no sítio certo, conseguimos encontrar literalmente qualquer desenho num retângulo $106\times 17$! Por exemplo, com $N=$ 677269797063266389145771001639366162904443300634759368354244105189144417475687924080590138582401925400953401198762670070868017028632609067495842127259345485889052110555312844858658969250766978033911456684637024394115209279287448522343527514061700072005928325124098808483476326307953390156875355289624192978628506335125351370018499785193486797521350328711540234844414805471938182060305235921541912512179523099720166772353828125144439537587189530425493554812515912471900753848603802337280 obtemos a imagem que está no início do post e que eu incluo de novo aqui:


A questão importante que se impõe agora é "Como encontro o valor de $N$ para um dado desenho?". Ou vêem este vídeo do Numberphile no youtube, ou continuam a ler: vamos criar um número em binário. Começando no canto superior direito, escrevo um $1$ se o quadrado for preto e escrevo um $0$ se o quadrado for branco; desço um quadrado e repito; faço isto coluna a coluna, de cima para baixo, da direita para a esquerda. Quando já tiver acabado de criar o número em binário, multiplico por $17$ e escrevo em base $10$. No vídeo que mencionei eles começam no canto inferior esquerdo, mas fazendo dessa maneira a imagem aparece refletida.

Claro que fazer isto à mão é disparate. O que fiz foi criar um programa em Python que me permite desenhar numa grelha e depois gera o número por mim. Depois disto, criei um pequeno programa que recebe um número e usa a fórmula em cima para gerar o desenho apropriado. Os dois programas (código Python e executáveis para o Windows) podem ser encontrados aqui. Depois de desenharem, carreguem S para gravar o número no ficheiro numbers.txt. Para ver o desenho associado com um número, primeiro ponham-no no ficheiro number2draw.txt e depois corram o programa que faz os desenhos.

Escrevam o vosso $N$ preferido nos comentários em baixo!

Se gostaram deste post, considerem subscrever a newsletter do blog e deixem um like no Facebook.

  - RGS

Popular posts from this blog

Tutorial on programming a memory card game

Markov Decision Processes 01: the basics

The hairy ball theorem and why there is no wind (somewhere) on Earth