Calculating Tupper’s Self-Referential Formula With SQL

A really geeky way to start a Monday morning is to be nerd-sniped by the cool Fermat’s Library twitter account…

… reading up on the cool Tupper’s Self-Referential Formula thinking “Can This be Done in SQL?™”

As we all know from a previous article, SQL is turing complete, so the answer must be yes. And in fact, as it turns out, this is actually super easy, compared to some other problems I’ve been solving with SQL on this blog in the past.

The Formula

The formula is really simple:

Or, in a more programmer-y way:

1/2 < floor(mod(floor(y/17)*2^(-17*floor(x)-mod(floor(y), 17)),2))

Luckily, this syntax also happens to be SQL syntax, so we’re almost done. So, let’s try plotting this formula for the area of x BETWEEN 0 AND 105 and y BETWEEN k AND k + 16, where k is just some random large number, let’s say

96093937991895888497167296212785275471500433966012930665
15055192717028023952664246896428421743507181212671537827
70623355993237280874144307891325963941337723487857735749
82392662971551717371699516523289053822161240323885586618
40132355851360488286933379024914542292886670810961844960
91705183454067827731551705405381627380967602565625016981
48208341878316384911559022561000365235137034387446184837
87372381982248498634650331594100549747005931383392264972
49461751545728366702369745461014655997933798537483143786
841806593422227898388722980000748404719

Unfortunately, most SQL databases cannot handle such large numbers without any additional libraries, except for the awesome PostgreSQL, whose decimal / numeric types can handle up to 131072 digits before the decimal point and up to 16383 digits after the decimal point.

Yet again, unfortunately, even PostgreSQL by default can’t handle such precisions / scales, so we’re using a trick to expand the precision beyond what’s available by default (for a better workaround, see Torsten Grust’s comment in the comments section). Here’s the SQL query:

WITH 
  t1(k, z) AS (
    SELECT 
      ('96093937991895888497167296212785275471500433966012930665'
    || '15055192717028023952664246896428421743507181212671537827'
    || '70623355993237280874144307891325963941337723487857735749'
    || '82392662971551717371699516523289053822161240323885586618'
    || '40132355851360488286933379024914542292886670810961844960'
    || '91705183454067827731551705405381627380967602565625016981'
    || '48208341878316384911559022561000365235137034387446184837'
    || '87372381982248498634650331594100549747005931383392264972'
    || '49461751545728366702369745461014655997933798537483143786'
    || '841806593422227898388722980000748404719')::numeric,
      (repeat('0', 2000) || '.' 
    || repeat('0', 1000) || '1')::numeric
  ),
  tupper(x, y, b) AS (
    SELECT 
      x, y,
      0.5 < floor(mod(floor(y / 17) 
              * 2 ^ (-17 * x - mod(y, 17)), 2))
    FROM 
      t1, 
      LATERAL (
        SELECT z + x AS x 
        FROM generate_series(0, 105) t2(x)) t2,
      LATERAL (
        SELECT z + k + y AS y 
        FROM generate_series(0, 16) t3(y)) t3
  )
SELECT string_agg(
  CASE WHEN b THEN '@@' ELSE '  ' END, '' 
  ORDER BY x DESC)
FROM tupper
GROUP BY y
ORDER BY y ASC;

What’s the result of the above?

string_agg                                                                                                                                                                                                           |
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
                @@                                      @@                                @@  @@@@  @@          @@                                @@    @@  @@          @@        @@  @@@@  @@            @@         |
                @@                                      @@  @@            @@              @@    @@  @@          @@                                @@    @@  @@          @@        @@    @@  @@            @@      @@ |
@@@@            @@                                    @@    @@            @@        @@@@  @@    @@  @@  @@  @@  @@  @@@@  @@@@@@@@    @@@@@@  @@@@@@  @@    @@  @@  @@  @@        @@    @@    @@            @@    @@ |
  @@            @@                                    @@    @@    @@  @@  @@              @@  @@    @@    @@    @@        @@  @@  @@  @@  @@  @@  @@  @@    @@  @@  @@  @@        @@  @@      @@            @@    @@ |
  @@            @@                                    @@    @@    @@  @@  @@              @@  @@    @@  @@  @@  @@        @@  @@  @@  @@@@@@  @@@@@@  @@    @@    @@    @@        @@  @@      @@            @@    @@ |
  @@            @@                              @@  @@      @@      @@    @@    @@@@                @@          @@                                    @@    @@  @@      @@    @@              @@      @@@@    @@  @@ |
@@@@@@      @@  @@                              @@  @@      @@    @@      @@  @@    @@              @@          @@                                      @@  @@          @@    @@            @@      @@    @@  @@  @@ |
          @@    @@  @@@@  @@      @@@@      @@@@@@  @@      @@            @@      @@                @@@@@@  @@@@@@                                      @@  @@@@@@  @@@@@@  @@              @@          @@    @@  @@ |
@@@@@@  @@      @@  @@  @@  @@  @@    @@  @@    @@  @@      @@  @@@@@@@@  @@    @@                                                                                                                    @@      @@  @@ |
          @@    @@  @@  @@  @@  @@    @@  @@    @@  @@      @@            @@  @@                                                                                                                    @@        @@  @@ |
@@@@        @@  @@  @@  @@  @@    @@@@      @@@@@@  @@      @@  @@  @@@@  @@  @@@@@@@@                                                                                                              @@@@@@@@  @@  @@ |
    @@          @@                                  @@      @@  @@    @@  @@                                                                                                                    @@            @@  @@ |
  @@            @@                                    @@    @@  @@    @@  @@                                                                                                                    @@          @@    @@ |
@@              @@                                    @@    @@  @@  @@    @@                                                                                                                  @@            @@    @@ |
@@@@@@          @@                                    @@    @@  @@  @@    @@                                                                                                                                @@    @@ |
                @@                                      @@  @@            @@                                                                                                                              @@      @@ |
                @@@@@@                                  @@  @@@@@@    @@@@@@                                                                                                                              @@  @@@@@@ |

It is a formula that can plot itself on a 17-bit wide bitmap. Cool, eh?

Play around with this formula yourself:
https://www.tuppers-formula.tk

9 thoughts on “Calculating Tupper’s Self-Referential Formula With SQL

  1. Hi,

    you can avoid the “trick” if you write the formula as

    0.5 < floor(mod(floor(y / 17.0) / 2^(-(-17 * floor(x) – mod(floor(y), 17))) :: numeric, 2))

    (since y * 2^(-x) = y / 2^x).

    Cheers,
    β€”Torsten

    • Are you sure? The trick was about getting beyond the default precision limit of 1000 in PostgreSQL… If you’re sure, would you mind explaining why this helps getting beyond that limit?

      • Yes, I am pretty sure. This is code I have written a few months ago (let me know if the cut & paste doesn’t work out properly).

        -- Tupper's self-referential formula
        --
        -- Plot points x ∈ [0,106), y ∈ [k, k+17) for which
        -- Β½ < ⌊mod(⌊y/17βŒ‹ Γ— 2^(-17 Γ— ⌊xβŒ‹ - mod(⌊yβŒ‹, 17), 2)βŒ‹
        -- holds.
        --
        -- The plotted image contains a representation of the formula itself:
        --
        --          β–ˆ                   β–ˆ                β–ˆ β–ˆβ–ˆ β–ˆ     β–ˆ                β–ˆ  β–ˆ β–ˆ     β–ˆ    β–ˆ β–ˆβ–ˆ β–ˆ      β–ˆ   β–ˆ
        --          β–ˆ                   β–ˆ β–ˆ      β–ˆ       β–ˆ  β–ˆ β–ˆ     β–ˆ                β–ˆ  β–ˆ β–ˆ     β–ˆ    β–ˆ  β–ˆ β–ˆ      β–ˆ   β–ˆ
        --  β–ˆβ–ˆ      β–ˆ                  β–ˆ  β–ˆ      β–ˆ    β–ˆβ–ˆ β–ˆ  β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ β–ˆβ–ˆ β–ˆβ–ˆβ–ˆβ–ˆ  β–ˆβ–ˆβ–ˆ β–ˆβ–ˆβ–ˆ β–ˆ  β–ˆ β–ˆ β–ˆ β–ˆ    β–ˆ  β–ˆ  β–ˆ      β–ˆ  β–ˆ
        --   β–ˆ      β–ˆ                  β–ˆ  β–ˆ  β–ˆ β–ˆ β–ˆ       β–ˆ β–ˆ  β–ˆ  β–ˆ  β–ˆ    β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ  β–ˆ β–ˆ β–ˆ β–ˆ    β–ˆ β–ˆ   β–ˆ      β–ˆ  β–ˆ
        --   β–ˆ      β–ˆ                  β–ˆ  β–ˆ  β–ˆ β–ˆ β–ˆ       β–ˆ β–ˆ  β–ˆ β–ˆ β–ˆ β–ˆ    β–ˆ β–ˆ β–ˆ β–ˆβ–ˆβ–ˆ β–ˆβ–ˆβ–ˆ β–ˆ  β–ˆ  β–ˆ  β–ˆ    β–ˆ β–ˆ   β–ˆ      β–ˆ  β–ˆ
        --   β–ˆ      β–ˆ               β–ˆ β–ˆ   β–ˆ   β–ˆ  β–ˆ  β–ˆβ–ˆ        β–ˆ     β–ˆ                  β–ˆ  β–ˆ β–ˆ   β–ˆ  β–ˆ       β–ˆ   β–ˆβ–ˆ  β–ˆ β–ˆ
        --  β–ˆβ–ˆβ–ˆ   β–ˆ β–ˆ               β–ˆ β–ˆ   β–ˆ  β–ˆ   β–ˆ β–ˆ  β–ˆ       β–ˆ     β–ˆ                   β–ˆ β–ˆ     β–ˆ  β–ˆ      β–ˆ   β–ˆ  β–ˆ β–ˆ β–ˆ
        --       β–ˆ  β–ˆ β–ˆβ–ˆ β–ˆ   β–ˆβ–ˆ   β–ˆβ–ˆβ–ˆ β–ˆ   β–ˆ      β–ˆ   β–ˆ        β–ˆβ–ˆβ–ˆ β–ˆβ–ˆβ–ˆ                   β–ˆ β–ˆβ–ˆβ–ˆ β–ˆβ–ˆβ–ˆ β–ˆ       β–ˆ     β–ˆ  β–ˆ β–ˆ
        --  β–ˆβ–ˆβ–ˆ β–ˆ   β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ  β–ˆ β–ˆ  β–ˆ β–ˆ   β–ˆ β–ˆβ–ˆβ–ˆβ–ˆ β–ˆ  β–ˆ                                                          β–ˆ   β–ˆ β–ˆ
        --       β–ˆ  β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ  β–ˆ β–ˆ  β–ˆ β–ˆ   β–ˆ      β–ˆ β–ˆ                                                          β–ˆ    β–ˆ β–ˆ
        --  β–ˆβ–ˆ    β–ˆ β–ˆ β–ˆ β–ˆ β–ˆ  β–ˆβ–ˆ   β–ˆβ–ˆβ–ˆ β–ˆ   β–ˆ β–ˆ β–ˆβ–ˆ β–ˆ β–ˆβ–ˆβ–ˆβ–ˆ                                                       β–ˆβ–ˆβ–ˆβ–ˆ β–ˆ β–ˆ
        --    β–ˆ     β–ˆ                 β–ˆ   β–ˆ β–ˆ  β–ˆ β–ˆ                                                          β–ˆ      β–ˆ β–ˆ
        --   β–ˆ      β–ˆ                  β–ˆ  β–ˆ β–ˆ  β–ˆ β–ˆ                                                          β–ˆ     β–ˆ  β–ˆ
        --  β–ˆ       β–ˆ                  β–ˆ  β–ˆ β–ˆ β–ˆ  β–ˆ                                                         β–ˆ      β–ˆ  β–ˆ
        --  β–ˆβ–ˆβ–ˆ     β–ˆ                  β–ˆ  β–ˆ β–ˆ β–ˆ  β–ˆ                                                                β–ˆ  β–ˆ
        --          β–ˆ                   β–ˆ β–ˆ      β–ˆ                                                               β–ˆ   β–ˆ
        --          β–ˆβ–ˆβ–ˆ                 β–ˆ β–ˆβ–ˆβ–ˆ  β–ˆβ–ˆβ–ˆ                                                               β–ˆ β–ˆβ–ˆβ–ˆ
        --
        --
        -- Can encode *any* 106x17 pixel image in terms of a single value of type numeric
        -- (see pixel image editor at http://tuppers-formula.tk): the following encodes the
        -- text "Advanced SQL":
        --
        -- \set k 52286934557658048028425956698007592392599530361873363333609880711749360515697214536719655759234958981559142573143695142261512175715575262178445160479745224050413186652132299326608682173356922986884858803658784114284120559745186144099152093031123509671116955442905501004550625844483047202158923745405732677551008895706387756563881115671352441965257523184483317832915333353792671679709434918092340808285147480120213896185154950991291329376438314822230636406240307557327442470102492396220365764965812928512
        
        \set k 960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719
        
        WITH
        tupper(x, y, pixel) AS (
          SELECT x, y - :k AS y,
                 --   Β½ < ⌊mod(⌊y/17βŒ‹ Γ— 2^(-17 Γ— ⌊xβŒ‹ - mod(⌊yβŒ‹, 17), 2)βŒ‹  (NB: replaced β‹― Γ— 2⁻ˣ by β‹― / 2Λ£)
                 0.5 < floor(mod(floor(y / 17.0) / 2^(-(-17 * floor(x) - mod(floor(y), 17))) :: numeric, 2)) AS pixel
          FROM   generate_series(0 , 105)   AS x,  -- x ∈ [0,106)
                 generate_series(:k, :k+16) AS y   -- y ∈ [k,k+17)
        )
        -- Plot pixels
        SELECT string_agg(CASE WHEN t.pixel THEN 'β–ˆ' ELSE ' ' END, NULL ORDER BY t.x DESC) AS "Tupper's Formula"
        FROM   tupper AS t
        GROUP BY t.y
        ORDER BY t.y;
        

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s