Hello, primes!

Over the years, I’ve had to learn quite a few programming languages (those tend to come and go). There’s a tradition, going back at least to C, to start with a so-called hello, world program. Eventually, I grew tired of saying hello to a world that never said hello back, and made my first foray into any new language a program that computes a list of prime numbers. Conceptually, it’s a little more interesting than hello, world because it requires conditionals, arithmetic and a form of iteration (or recursion).

I won’t bore the reader with examples from mainstream languages. The focus of this page is programming primes numbers in PostScript, a language that was designed for graphics. Still, I have to mention one of my favorite prime numbers program, written for the dc unix command (arguably, not a programming language):

2p3p[dl!d2+s!%0=@l!l^!<#]s#[s/0ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x

Feed this line to dc and it will start spewing prime numbers. Using !, @ and # as variable names makes the program adequately unreadable and I used it for a long time as my email signature line. I had to stop because it confused readers too much (I’m referring to human beings, not email software).

Programming in PostScript

Before pdf, there was PostScript, developed by the same people, Adobe. In contrast to pdf, however, PostScript is a full-fledged programming language. Because it is stack-based (like dc), it allows for recursion, and of course, it has all the arithmetic needed for graphics. So, one can write a PostScript program to compute prime numbers. Here is one that calculates all primes between 2 and 9973. Just a plain table of prime numbers. The fun part is that it is the printer that computes it.

Ulam’s spiral

PostScript being a language for graphics, it can be used for more than just a table of numbers. In the world of completely useless stuff, there is something called Ulam’s spiral. It’s obtained from writing positive integers in a (squarish) spiral and crossing out all the non-primes:

 x -x-99-98-97-96-95-94-93-92-91             @-----------@-----------------|   
 |                             |             |                             |   
 x 65-64-63-62-61-60-59-58-57 90             |  |-----------@-----@-----|  |   
 |  |                       |  |             |  |                       |  |   
 x 66 37-36-35-34-33-32-31 56 89             @  |  @-----------------@  |  @   
 |  |  |                 |  |  |             |  |  |                 |  |  |   
 x 67 38 17-16-15-14-13 30 55 88             |  @  |  @-----------@  |  |  |   
 |  |  |  |           |  |  |  |             |  |  |  |           |  |  |  |   
 x 68 39 18  5--4--3 12 29 54 87             |  |  |  |  @-----@  |  @  |  |   
 |  |  |  |  |     |  |  |  |  |             |  |  |  |  |     |  |  |  |  |   
 x 69 40 19  6  1--2 11 28 53 86             |  |  |  @  |   --@  @  |  @  |   
 |  |  |  |  |        |  |  |  |             |  |  |  |  |        |  |  |  |   
 x 70 41 20  7--8--9-10 27 52 85             @  |  @  |  @--------|  |  |  |   
 |  |  |  |              |  |  |             |  |  |  |              |  |  |   
 x 71 42 21-22-23-24-25-26 51 84             |  @  |  |-----@--------|  |  |   
 |  |  |                    |  |             |  |  |                    |  |   
 x 72 43-44-45-46-47-48-49-50 83             @  |  @-----------@--------|  @   
 |  |                          |             |  |                          |   
 x 73-74-75-76-77-78-79-80-81-82             |  @-----------------@--------|   
 |                                           |                                 
 x--x--x--x--x--x--x--x--x--x--x...          |-----@------------------------...

What (some) people find interesting is that, on a large enough spiral, patterns seem to start emerging. This is a snapshot taken from a larger spiral, where one can see diagonal lines (sort of):

This picture was generated from rendering a PostScript program (here). The program actually draws round discs for the prime numbers and has the option of drawing the spiral and printing the numbers inside the discs as well. If you use a PostScript renderer to zoom in a large spiral, you can see this:

zoom in spiral

Note that each number must be tested for primality, using a naive and inefficient algorithm. This makes the rendering of a spiral somewhat computationally expensive. It’s not too bad when using a renderer like ghostscript on a desktop computer, but when the printer has to do all the work… It gets even worse with some printers that translate PostScript into something else (like PCL) and don’t necessarily expect that the file they’re printing is actually computing prime numbers!