A few months ago, a discussion with about the Sieve of Eratosthenese inspired me to understand prime numbers more. I caught a glimpse of understanding and have spent much of my pub time discussing my ideas since then with anyone who will participate. Fortunately, I have several mathematician friends who are smarter than me, so the information mostly flowed into my head. However, I did come up with some interesting approaches to understanding the prime number distribution, and I’m going to try to document them in a useful way in this blog.
I have found that thinking about Primes fits nicely in my head and doesn’t require any writing; so it’s nice mental fodder to ponder when I go to sleep. This page is mostly background on Primes and also a survey of my efforts and thoughts up to this point. Later posts will expand on some of the most fruitful.
Basics of Number Theory and Prime Numbers
Many of the tools necessary to play with Primes have been learned in elementary school with the concepts of Natural Numbers, Multiplication, and Divisibility.
A Geometric Understanding of Primality
Instead of looking at a number $n$ as a product of factors, and then asking whether the only factors are $1$ and $n$ to determine primality, there is an intuitive geometric analogy that we will find ties deeply into category theory and other fun things.
Imagine that you have $n$ boards, each of which is $1" \times 1"$ square in cross section, and maybe a foot in length (the length does not matter). Suppose I ask you to stack these boards such that they are parallel and their cross section is a rectangle. Clearly, you can lay the boards out next to each other on the floor, and they will form a $1 \times n$ rectangle. Similarly, you will be able to stack the boards into a $1 \times n$ stack. Let’s call both $1 \times n$ and $n \times 1$ configurations cheating.
Usually, you will be able to create a non-trivial rectangle; for example, with $6$ boards, you can form a $2 \times 3$ or a $3 \times 2$ and even an $6 \times 1$ stack (all the boards stacked up on top of one board touching the floor).
If you can stack the boards in such a way that you don’t have a single row or column (the trivial cases $1 \times n$ and $n \times 1$), then $n$ is a composite number and its factors are $f_1$ and $f_2$ if it can be stacked with cross section $f_1 \times f_2$. Otherwise, $n$ is prime.
A Story
At a local lumberyard, they have workers whose job it is to stack boards into rectangles that can be wrapped or strapped (two methods of binding wood products for shipping). Imagine one such worker, Beatrice, whose job it is to rectangularize a quantity of boards. For the sake of our analogy, these boards are always square in their cross-section (e.g., 1-by-1 or 2-by-2 or 4-by-4).
One day, Beatrice’s boss Cathy tells her that she needs to build a bundle of $6$ boards, and that they must be in a non-trivial rectangular block (i.e., not laid flat in a $6 \times 1$ or stacked into a $1 \times 6$ configuration). Beatrice quickly realizes she has two choices:
“0”+/r2em/*++{4} \frm{=}, +/d2em/++{5} \frm{=}, +/d2em/++{6} *\frm{=},
“0”+/r10em/*++{1} \frm{=}, +/d2em/++{2} *\frm{=},
“0”+/r12em/*++{3} \frm{=}, +/d2em/++{4} *\frm{=},
“0”+/r14em/*++{5} \frm{=}, +/d2em/++{6} *\frm{=},
\end{xy}
Beatrice chooses one of these, stacks her boards, and awaits the next task.
Next, Cathy assigns Beatrice the job of stacking $7$ boards. Beatrice considers her options and determines that you cannot stack $7$ boards into a non-trivial rectangle. $7$ is a prime number and has no factors that can be used to rectangularize the boards. At this point, Beatrice can draw two conclusions:
-
She has one more board than necessary to complete a valid stack. This excess is called the remainder or modulus. Mathematically, she has $1 = 7 \bmod 2$ and $1 = 7 \bmod 3$ excess boards.
-
If she had more boards, she could do her job. With $1$ additional board, she could create a $2 \times 4$ stack. With two more boards, she could create a $3 \times 3$ stack. This deficit is called the gap, and represents how many boards are necessary to complete a stack of a given dimension.
The removal solution, based on the modulus or *remainder is identical to the $n = 6$ problem:
“0”+/r2em/*++{4} \frm{=}, +/d2em/++{5} \frm{=}, +/d2em/++{6} *\frm{=},
“0”+/r10em/*++{1} \frm{=}, +/d2em/++{2} *\frm{=},
“0”+/r12em/*++{3} \frm{=}, +/d2em/++{4} *\frm{=},
“0”+/r14em/*++{5} \frm{=}, +/d2em/++{6} *\frm{=},
\end{xy}
Beatrice suggests that by adding a few boards, alternative solutions present themselves. There are actually many classic puzzles based upon the idea of supplementing a deficit to simplify partitioning. For example, Shepherd and Sheep Problems.
A Prime Generator Experiment
When we break down a number into its prime factors, we perform divisibility tests and record the prime factors. However, there’s a bunch of information discovered during the divisibility tests that we throw away. I wanted to see if we can retain and use this information to determine subsequent primes and composites.
The machine below is designed to visualize the output of a traditional divisibility test, as well as the intermediate values computed during this test. Each row displays an integer $N$ and each cell within a row displays the residue when $N$ is divided by that cell’s column $D$. When Show Remainders is selected, this residue is simply the remainder $N \bmod D$; otherwise, it is the value $N - (N \bmod D)$, which reflects the jump distance to the next multiple of $D$. In the board-stacking metaphor above, this jump distance is the number of additional boards required to rectangularize a stack of $N$ boards partioned into $D$ layers.
The Pumping Algorithm
I’m not trying to compete with high-performance prime generators with this algorithm, but I do want to see how far I can get without using multiplication or division to discover primes. The idea is that we have a dynamic programming algorithm that efficiently manages its computation so that nothing is wasted. Contrast this with a brute force divisibility algorithm which divides every candidate number $N$ by at least $\lfloor{\sqrt{N}}\rfloor$ divisors.
Disclaimer: I may be just reinventing the Sieve of Eratosthenes, perhaps with some space/time tradeoffs.
The approach I’m trying is to have a divisibility matrix that is built through addition and logic, but no multiplication. I’m expecting that the limitations of this approach will reveal something useful; alternatively, I’ll have developed some new kind of prime number algorithm (probably already invented, I haven’t done much research on competitive algorithms).
The basic pumping algorithm begins with the generation of the $N = 2$ row. This can be performed without any actual division, since we know that $2 \bmod D$ is obtainable via the recurrence:
- Base Case: $2 \bmod 2 = 0$
- Inductive Case: $2 \bmod D = 2$ if $D > 2$
So as long as we compute the $N = 2$ divisibility row from left to right, we don’t need any math. And really, we know it’s a constant $0, 2, 2, 2, \dots$.
Thinking out loud, let’s suppose we have a divisibility matrix $D(n,d)$, where $n$ is a number to be factored and $d$ is the remainder $n \bmod d$. Now suppose we want to determine the next row for $D(n+1,d)$. This comes down to being able to evaluate $(n + 1) \bmod d$, without using division. Let’s try it with the next row $n = 3$, which we can base on the seeded initial $n=2$ row:
$$ 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 $$
which reflects the remainders of the number $2$ when divided by any divisors other than $2$.
How can we compute $3 \bmod 2$ given the above matrix? We do know that $2 \bmod 2 = 0$ and that $2 \bmod 3 = 2$ from the above matrix, as well as a bunch of other seemingly irrelevant facts like $2 \bmod 9 = 2$.
Let’s go back to our board-stacking scenario and consider that our friend Beatrice the Board Stacker starts to think not in terms of modulus (stack excess) but in terms of gap (stack deficit). Now we can look at a directive to “Productize 7 boards into layers of 3 boards” as requiring 2 additional boards to make a “9-stack”, rather than losing 1 board to make a “6-stack”. Hmmm, we know that $3 \bmod 2 = 1$, but that’s cheating. How can we deduce it? Well, the equation can be rephrased as $3 = 2 * m + 1$, where $m$ is some multiplier. So we can rephrase some of our prior knowledge as $2 = 2 * 1 + 0$ and $2 = 3 * 0 + 2$. Does that help? Can we deduce an $m$ that satisfies $3 = 2 * m + 1$ from these? We know that $m = 1$, but that’s cheating.
Using some basic algebra, it is easy to solve for a set of candidate $m$, but we are using multiplication and division, which I’m trying to avoid.
But we cheated and performed a divisibility test. Let’s see what we can conjure otherwise. We can use substitution and logic and addition/subtraction, but no multiplication or division. Substitution is legal, however.
Doing it over and simplifying with the above restrictions:
How do we solve for $m$ without doing a division? Can we use our prior divisibility knowledge? Let’s take the last equation above and combine it with the $2 = 2 * 1 + 0$ we rewrote $2 \bmod 2 = 0$ as:
So we deduced $m = 1$ using the prior divisibility matrix. I’m going to try to code this now.
Latest news
The pumping algorithm works. The prime predictor works.
label { font-size:0.7em; height:14px; }
.gridtable { background-color:black; display:table; margin:0; padding:0; width:100%; border:2px solid gray; }
.gridrow { display:table-row; width:100%; margin:0; padding:0; }
.gridcell { display:table-cell; text-align:center; vertical-align:text-top; width:50px; height:14px; float:left; font-size:0.5em; font-family:“Ubuntu Mono”, monospace; background-color: #EEEEEE; //border:1px solid darkgray; } .gridcell.bigpicture { width:4px; }
.gridcellp { margin:0; padding:0; display:table-cell; text-align:center; vertical-align:text-top; width:60px; height:14px; float:left; font-size:0.5em; font-family:“Ubuntu Mono”, monospace; background-color: #EEEEEE; //border:1px solid darkgray; }
.gridcell2 { margin:0; padding:0; display:table-cell; text-align:center; vertical-align:text-top; width:14px; height:14px; font-size:0.5em; line-height:0.5em; font-family:“Ubuntu Mono”, monospace; font-weight: bold; float:left; background-color: aliceblue; }
.gridcell2.bigpicture { width:4px; }
Show Remainders Show Colors Use Pump Algorithm Use Big Picture
The source for the above is: