Art with primes

• 

  app window

I worked this a couple of years back, a prime ASCII-art generator. It transforms any image into a unique, colossal prime number that visually represents the original picture as ASCII art.

But beyond the visual novelty it is actually quite a fascinating number theory problem. The core of this generator is its relentless, yet guaranteed, quest for a prime.

Image to Number Conversion

The first step is to convert a visual image into a single, massive integer. The process begins by taking a standard digital image and resizing it to a more manageable dimension, say 100x100 pixels, to keep the resulting number within a computable range. The image is then converted to grayscale. This simplifies our data, as each pixel is no longer represented by three color channel values (Red, Green, and Blue), but by a single value indicating its brightness, typically from 0 (black) to 255 (white).

Once we have this grid of grayscale values, we can think of it as a matrix of numbers. To transform this matrix into a single integer, we concatenate the pixel values. For example, if we have a simple 2x2 grayscale image with the following pixel values:

123	45
67	89

We can form a number by reading the pixel values row by row: 123045067089. To ensure each pixel's value is distinct, we pad each value with leading zeros to make them all three digits long (since the maximum value is 255). So, our example becomes:

123	045
067	089

Concatenating these gives us the number 123045067089. For an image of size w x h, where P_ij is the padded grayscale value of the pixel at row i and column j, the resulting number N can be represented as:

N = concatenate(P₁₁, P₁₂, ..., P_1w, P₂₁, ..., P_hw)

This single, large integer is the numerical fingerprint of our image, the starting point for our prime number quest.

Testing for Primality with Miller-Rabin

Now that we have our colossal number, the next challenge is to determine if it's prime. For small numbers, we could try dividing by all integers up to its square root. But for a number with hundreds or even thousands of digits, this is computationally impossible. This is where the Miller-Rabin primality test comes in—a powerful and efficient probabilistic algorithm.

The Miller-Rabin test doesn't definitively prove a number is prime in the way trial division does. Instead, it declares a number as either "composite" or "probably prime." By running the test multiple times with different random bases, we can reduce the probability of a composite number being mistakenly identified as prime to an infinitesimally small value. For practical purposes, it's a highly reliable method.

Here's how the algorithm works, roughly

1. Preparation: For a given number n to be tested, we first find integers r and d such that n - 1 = 2^r * d, where d is odd. This is always possible for any even number n-1.

2. Witness Selection: We pick a random integer a (called a "witness") such that 2 ≤ a ≤ n - 2.

3. The Test: We compute x = a^d mod n.

4. Checking Conditions:

   • If x = 1 or x = n - 1, then n passes the test for this witness and is considered "probably prime."
   • If not, we repeatedly square x (i.e., x = x² mod n) for r-1 times. If at any point x becomes n - 1, n passes the test.
   • If we complete the loop without x becoming n - 1, then n is definitively composite.

The beauty of the Miller-Rabin test lies in its speed and the fact that if a number is composite, at least 75% of the possible witnesses will prove it. So, after a few successful rounds, our confidence that the number is prime becomes incredibly high.

Our generator takes the initial number from the image, runs the Miller-Rabin test, and if it's not prime, it slightly "mutates" the number (e.g., by adding a small integer) and tests again. This process repeats until a "probably prime" number is found.

The cool part is, the mutation step can even be 1 digit somewhere within the >1000 digit integer.

Proof that the algorithm stops

This brings us to the most crucial question: can we be sure that this process of mutating and testing will eventually find a prime? because with a number on the size of 10^10000. it is important to know that the algorithm stops at some point in the future.

Bertrand's Postulate

First conjectured by Joseph Bertrand in 1845 and later proven by Pafnuty Chebyshev, Bertrand's Postulate states that for any integer n > 3, there is always at least one prime number p such that n < p < 2*n*.

This elegant theorem is the bedrock of our generator's success. When we start with our image-derived number n, Bertrand's Postulate guarantees that a prime number exists somewhere in the interval between n and 2*n*. Since our mutation process systematically checks numbers, it is mathematically certain to stumble upon a prime within this range. The search, therefore, is always finite.

Number of trials

While Bertrand's Postulate guarantees we'll find a prime, the Prime Number Theorem gives us an idea of how long we'll have to search. This theorem, proven independently by Jacques Hadamard and Charles de la Vallée Poussin in 1896, describes the distribution of prime numbers. It states that the number of primes less than or equal to n, denoted by π(n), is approximately:

π(n) ≈ n / ln(n)

From this, we can infer the "density" of primes around a number n. The probability of a randomly chosen integer near n being prime is roughly 1 / ln(n). This means, on average, we would expect to test about ln(n) numbers before finding a prime.

Let's put this into perspective. If our image generates a 100-digit number (n ≈ 10⁹⁹), then ln(n) ≈ 99 * ln(10) ≈ 228. So, we'd expect to perform a few hundred trials on average—a remarkably small number for such a colossal search space. The average gap between primes around a number n grows as the natural logarithm of n.

Art x Math

When I started out with programming I spent a couple of weekends on this. The idea that, images are just numbers was quite shocking to grasp. Even more exciting was the idea that, they can be converted into an integer. Best feeling of all was that it can be a prime number.

Quite a unique solvable only by programming.

You can find the JS implementation with react and background workers here

If you're serious about this and want to run it over big numbers the browser might not be the best place. You can try running the python script I have here.

Built With

• number-theory