Prime Portraits

Year: 2016 Authors: Zachary Abel

Core claim

By combining image dithering, small random perturbations, and primality testing, one can find large prime numbers whose digit patterns depict intended portraits.

Topics

prime numbers, visual patterns, digit grids, portrait encoding, computational search

Domains

number theory, prime number theorem, Gaussian integers, probabilistic primality testing, data art, digital portraiture, generative art, pattern visualization

Methods

Floyd-Steinberg dithering, random pixel perturbation, Miller-Rabin test, grid-based digit mapping

Media

decimal digits, base 9 digits, grayscale shading, Fermat spiral layout

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges Finland Conference Proceedings

Prime Portraits

Zachary Abel

Department of Applied Mathematics, MIT

77 Massachusetts Avenue, Cambridge, MA 02138, USA

Abstract

We introduce a versatile method for finding prime numbers that display surprisingly intricate visual patterns—hypothetically, any desired pattern is possible, with only mild distortion. We use this method to locate several examples of large prime numbers that are, in and of themselves, self-referential works of art.

Prime Portrait Examples

The 16,129-digit number $P_{\mathrm{mer}}$ whose first few digits are shown in Figure 1 is a special prime number. It doesn’t qualify as a Mersenne prime, since it definitely isn’t one less than a power of two, but it is a “Mersenne” prime when looked at the right way. Indeed, looking is key! Imagine laying out its digits in a $127\times 127$ grid in order and coloring them by value as in Figure 2: all 9s are colored white, all 0s black, and so on. The result is shown in Figure 3—yes, this prime number shows the face of Marin Mersenne! No wonder the Great Internet Mersenne Prime Search didn’t find it.

$P_{\mathrm{mer}}=8887888787878787787787777777777777777777777777777777777777777777777777777777777777777777777777777$ 1 2 3 4

Figure 1: The first thousand digits of the 16,129-digit prime number $P_{\mathrm{mer}}$ . Figure 2: Digits are colored by value.

Let’s look at a few more examples to begin to explore the range of possibilities for these prime portraits—and as an excuse for more (inexcusable) prime puns.

“Optimus” Prime. Figure 4 shows a 12,800-digit prime that transforms(!) into a recognizable figure when written in base 9, arranged in order in a $128\times 100$ grid, and colored with the palette shown. (Why these colors? Why base 9? Simply because we can.)

Sophie Germain Prime. Mathematically, Sophie Germain primes (named after French mathematician Marie-Sophie Germain for her work relating to Fermat’s Last Theorem) are those prime numbers $p$ for which $2p+1$ is also prime, such as 53 (because $2\cdot 53+1=107$ is also prime). The $53\times 107$ -digit prime number $P_{\mathrm{sg}}$ in Figure 5 is not merely a punny “Sophie Germain” prime by virtue of depicting her; this number $P_{\mathrm{sg}}$ is actually a Sophie Germain prime! In other words, $2P_{\mathrm{sg}}+1$ is also prime!

Gaussian Prime. Gaussian integers are the complex numbers $a+bi$ where $a$ and $b$ are integers, and those that can’t be factored (excluding $\pm 1$ and $\pm i$ as factors) are called Gaussian primes. So 7 and $2+3i$ are Gaussian primes (try to factor them!), but $5=(2+i)(2-i)$ and $5+i=(1+i)(3-2i)$ are not. If the left half of Figure 6 is read as a single 10,440-digit number $A_{\mathrm{g}}$ , and the right half likewise read as an integer $B_{\mathrm{g}}$ , then $A_{\mathrm{g}}+i{B}_{\mathrm{g}}$ is, visually and mathematically, a Gaussian prime.

Abel

Figure 3: When gridded and shaded as in Figure 2, prime $P_{\mathrm{mer}}$ shows an image of Mersenne himself! Left: the full prime. Right: a closeup showing digits.

Twin Prime. A prime $p$ is a twin prime if either $p+2$ or $p-2$ is also prime. The 1,271-digit primes $P_{\mathrm{jack}}$ and $P_{\mathrm{inn}}$ from Figure 7 are twin primes ( $P_{\mathrm{jack}}+2$ and $P_{\mathrm{inn}}+2$ are both prime) showing images of Jack and Finn Harries of YouTube fame. In fact, more is true: primes that are 6 apart are called sexy primes (deriving from the Latin for 6), and since $P_{\mathrm{jack}}+6$ and $P_{\mathrm{inn}}+6$ are also prime, the numbers $P_{\mathrm{jack}}$ and $P_{\mathrm{inn}}$ are sexy twin primes…

“Fermat” Prime. Our last example goes off-grid. The digits of the 5000-digit prime number $P_{\mathrm{fer}}$ have been positioned in order along the Fermat spiral (Figure 8), starting from the center and each rotated by an angle of $\approx 137.508^{\circ }$ from the previous to form an idealized phyllotaxis pattern. As Fibonacci numbers pervade this pattern, a portrait of Leonardo Bonacci (a.k.a., Fibonacci) would also have been appropriate.

How it Works

We still find the existence of these primes surprising—indeed, it’s fun to consider that these primes existed long before their subjects were born! But mathematically, there are two simple principles driving all of the above examples: “Primes are everywhere,” and “Primes are easy to spot (with a computer).”

Primes are Everywhere. A common strategy for locating large primes (e.g., for use in cryptographic schemes like RSA or Diffie Hellman) is to just choose randomly: to locate a prime with $n$ digits, write down a random $n$ -digit number, check if it’s prime, and repeat until success. This strategy owes its effectiveness to the Prime Number Theorem, which ensures that each random sample has about a $1/(n\cdot \ln 10)\approx 1/(2.3n)$ chance of being prime, so we can expect to stumble into a prime after only about $2.3n$ trials. For a 16,129-digit prime like $P_{\mathrm{mer}}$ , only about 37,138 samples are required. (Note that this strategy relies on the ubiquity of primes, not just their infinitude—there are infinitely many powers of 2, for example, but they’re far too spread out for a random search to reliably find them.)

We modified this strategy only slightly: instead of generating truly random numbers, we created candidate numbers that all resembled Mersenne. Specifically, we started with a proper image of Mersenne,

Prime Portraits

Figure 4: The 12,800-digit prime number $P_{\mathrm{opt}}$ has been written in base 9, arranged in a $128\times 100$ grid, and colored with the palette shown in the top right.

Figure 5: The 5,671-digit prime $P_{\mathrm{sg}}$ has been drawn in a $107\times 53$ grid. $2P_{\mathrm{sg}}+1$ is also prime.

used a dithering algorithm (Floyd-Steinberg dithering [1]) to approximate the image using only the allowed 10 shades of gray, and then checked the resulting number for primality. By adding subtle noise to the portrait (randomly changing each pixel value by an imperceptible $\pm 1\%$ ) before dithering, we generated many different pixelations of the same image—enough that one of them happened to be prime. Thankfully, it appears that the properties of “looking like Mersenne” and “being prime” are independent enough for the Prime Number Theorem’s probabilities to still apply. In principle, this same strategy can work for any target image.

Primes are Easy to Spot (with a Computer). In the procedure above, how do we test whether a given number is prime? Fast algorithms for primality testing do exist, but they require surprising subtlety. The widely used RSA cryptosystem relies on the infeasibility of factoring numbers with just a few hundred digits ${}^5$ , even with today’s best hardware and most advanced algorithms. In particular, the naive method of trial division ${}^6$ is woefully outmatched by the 1,271 digits of $P_{\mathrm{jack}}$ or $P_{\mathrm{inn}}$ , to say nothing of the 16-thousand digits of $P_{\mathrm{mer}}$ . By contrast, software packages like the Gnu Multiple Precision Library (which we used) or Mathematica can test whether numbers of these sizes are prime in mere minutes, with clever techniques that test for primality without relying on factoring.

Furthermore, for numbers this large, the best general purpose algorithms are probabilistic, meaning they have a small (but tunable) chance of error. We ran 100 rounds of the Miller-Rabin test [3] on each of the above examples, making the chance of error less than $4^{-100}$ (smaller than the chance of winning the Powerball jackpot 7 times in a row!), discounting the possibility of hardware failure (which is more likely).

Acknowledgments

We are grateful to Jon Dobres, Scott Kominers, and Andrea Hawksley for helpful comments regarding this paper’s presentation, and to Will Schwartz for suggesting many amusing prime puns, including the above

Abel

twin primes example.

References

[1] Robert W. Floyd and Louis Steinberg. An adaptive algorithm for spatial grey scale. Proceedings of the Society of Information Display, 17:75-77, 1976. [2] Sophia Money-Coutts. The ultimate twinset: Jack and Finn Harries! Tatler, 2013. [3] Michael O. Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12:128-138, 1980.

Figure 6: The numbers $A_{\mathrm{g}}$ and $B_{\mathrm{g}}$ , forming a Gaussian prime $A_{\mathrm{g}}+i\cdot B_{\mathrm{g}}$ , have each been drawn in $72\times 145$ grids and tinted red and blue, respectively.

Figure 7: The 1,271-digit number $P_{\mathrm{jack}}$ (left), drawn here in a $41\times 31$ grid, is such that $P_{\mathrm{jack}}$ , $P_{\mathrm{jack}}+2$ , and $P_{\mathrm{jack}}+6$ are all prime, making $P_{\mathrm{jack}}$ a “sexy twin prime.” The same is true for $P_{\mathrm{finn}}$ (right).

Figure 8: The 5,000 digits of prime $P_{\mathrm{fer}}$ have been strung along the Fermat spiral.