Tupper's self-referential formula
- Introduction
Jeff Tupper, in his 2001 paper "Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables", shows a set of methods to graph equations and inequalities with two variables in the cartesian plane.
One of the examples of the paper, refers to the inequality:
That inequality, once plotted in the range 0 ≤ x ≤ 106 and k ≤ y ≤ k + 17 for k = 960, 939, 379, 918, 958, 884, 971, 672, 962, 127, 852, 754, 715, 004, 339, 660, 129, 306, 651, 505, 519, 271, 702, 802, 395, 266, 424, 689, 642, 842, 174, 350, 718, 121, 267, 153, 782, 770, 623, 355, 993, 237, 280, 874, 144, 307, 891, 325, 963, 941, 337, 723, 487, 857, 735, 749, 823, 926, 629, 715, 517, 173, 716, 995, 165, 232, 890, 538, 221, 612, 403, 238, 855, 866, 184, 013, 235, 585, 136, 048, 828, 693, 337, 902, 491, 454, 229, 288, 667, 081, 096, 184, 496, 091, 705, 183, 454, 067, 827, 731, 551, 705, 405, 381, 627, 380, 967, 602, 565, 625, 016, 981, 482, 083, 418, 783, 163, 849, 115, 590, 225, 610, 003, 652, 351, 370, 343, 874, 461, 848, 378, 737, 238, 198, 224, 849, 863, 465, 033, 159, 410, 054, 974, 700, 593, 138, 339, 226, 497, 249, 461, 751, 545, 728, 366, 702, 369, 745, 461, 014, 655, 997, 933, 798, 537, 483, 143, 786, 841, 806, 593, 422, 227, 898, 388, 722, 980, 000, 748, 404, 719 produces a drawing that visually mimics the inequality itself, hence it is called self-referential.
Although the inequality is intended to be drawn on the continuum of the cartesian plane, the drawing can be performed iterating over the integer values of both the horizontal and vertical ranges.
- Task
Make a drawing of the Tupper's formula, either using text, a matrix or creating an image.
This task requires arbitrary precision integer operations. If your language does not intrinsecally support that, you can use a library.
- Epilogue
The value of k is an encoding of the bitmap of the image, therefore any 17-width bitmap can be produced, using its associated encoded value as k.
- References
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
First, let us make the definition of k:
Tupper uses the notation mod(a, b) for the modulo operation, while Fōrmulæ uses the notation a Mod b. If we want to use the Tupper's formula exactly as it is, we can use the trick:
Now we can use a formula that looks exactly as Tupper's:
Visualization as a matrix. The following creates a 17×107 matrix. Values for which inequality is true are shown as an opaque black color, otherwise they are shown as an transparent color.
Visualization as an image. In the following script, a function to draw the Tupper's formula is used to generate the image with different sizes, because the standard 1x1 pixel per unit results to be too small in order to be appreciated:
Julia
import Images: colorview, Gray
import Plots: plot
setprecision(BigFloat, 8000)
""" get logical inverse of Tupper function values for black on while graphic """
function tupper_mat(k)
tmatrix = trues(17, 106)
for (i, x) in enumerate(0.0:1:105), (j, y) in enumerate(k:k+16)
tmatrix[j, 107 - i] = 1/2 >= floor(mod(floor(y / 17) * 2^(-17 * floor(x) - mod(floor(y), 17)), 2))
end
return tmatrix
end
const k = big"""960_939_379_918_958_884_971_672_962_127_852_754_715_004_339_660_129_306_651_505
519_271_702_802_395_266_424_689_642_842_174_350_718_121_267_153_782_770_623_355
993_237_280_874_144_307_891_325_963_941_337_723_487_857_735_749_823_926_629_715
517_173_716_995_165_232_890_538_221_612_403_238_855_866_184_013_235_585_136_048
828_693_337_902_491_454_229_288_667_081_096_184_496_091_705_183_454_067_827_731
551_705_405_381_627_380_967_602_565_625_016_981_482_083_418_783_163_849_115_590
225_610_003_652_351_370_343_874_461_848_378_737_238_198_224_849_863_465_033_159
410_054_974_700_593_138_339_226_497_249_461_751_545_728_366_702_369_745_461_014
655_997_933_798_537_483_143_786_841_806_593_422_227_898_388_722_980_000_748_404_719"""
function test_tupper()
bmap = tupper_mat(k)
display(plot(colorview(Gray, bmap), ylims = [1,17]))
savefig("tupper.png")
end
test_tupper()
- Output:
Wren
This works albeit rather slowly, taking almost 1.5 minutes to calculate the points to be plotted.
The culprit here is BigRat which is written entirely in Wren and always uses maximum precision. Unfortunately, we can't use GMP in a DOME application which would be much faster than this.
import "dome" for Window
import "graphics" for Canvas, Color
import "./plot" for Axes
import "./big" for BigRat
import "./iterate" for Stepped
var s = """
960 939 379 918 958 884 971 672 962 127 852 754 715 004 339 660 129 306 651 505
519 271 702 802 395 266 424 689 642 842 174 350 718 121 267 153 782 770 623 355
993 237 280 874 144 307 891 325 963 941 337 723 487 857 735 749 823 926 629 715
517 173 716 995 165 232 890 538 221 612 403 238 855 866 184 013 235 585 136 048
828 693 337 902 491 454 229 288 667 081 096 184 496 091 705 183 454 067 827 731
551 705 405 381 627 380 967 602 565 625 016 981 482 083 418 783 163 849 115 590
225 610 003 652 351 370 343 874 461 848 378 737 238 198 224 849 863 465 033 159
410 054 974 700 593 138 339 226 497 249 461 751 545 728 366 702 369 745 461 014
655 997 933 798 537 483 143 786 841 806 593 422 227 898 388 722 980 000 748 404
719
"""
s = s.replace(" ", "").replace("\n", "")
var k = BigRat.new(s)
var Pts = []
for (j in 0..16) {
var y = k + j
var t1 = (y/17).floor
var t2 = (y % 17).toInt
for (x in 0..106) {
var t3 = BigRat.two.pow(-17 * x - t2)
if (BigRat.half < ((t1 * t3) % 2).floor) {
Pts.add([106-x, 16-j])
System.print([j, x]) // to show progress on terminal
}
}
}
class Main {
construct new() {
Window.title = "Tupper's self-referential formula"
Canvas.resize(840, 260)
Window.resize(840, 260)
Canvas.cls(Color.white)
var axes = Axes.new(100, 200, 660, 180, -10..110, -1..17)
axes.draw(Color.black, 2)
var xMarks = Stepped.new(-10..110, 10)
var yMarks = Stepped.new(-1..17, 2)
axes.mark(xMarks, yMarks, Color.black, 2)
axes.label(xMarks, yMarks, Color.black, 2, Color.black)
axes.plot(Pts, Color.black, "■") // uses character 0x25A0
}
init() {}
update() {}
draw(alpha) {}
}
var Game = Main.new()