Functional Prime Number Sieve

In a post a few years ago I discussed primality testing. For some reason I thought I described the basic prime number sieve (I’m pretty sure there is only one) there, but apparently I didn’t. No worries. The prime number sieve solves a different problem; that of generating a list of the first $N$ primes. One could use a primality testing method to do this as well; namely filter a list of numbers with the primality test as a predicate; but sieve based methods are faster and conceptually much easier.

The prime number sieve iteratively filters out all the composite numbers, with the caveat that the leading number in the input is a prime. For , we put aside $2$, the smallest number, and filter out all multiples of $2$; then put aside $3$ and filter out multiples of $3$, and so on. This process, shown below as a decreasing sequence, terminates with a set of primes.

At each stage we have a list of some primes and a residual set, which if it is nonempty must be filtered; this process terminates when the residual set is empty. Filtering and subsequent residuals sort of defines the set of all primes; however it is an infinite process.

When $n$ primes have been filtered the state looks like . Here we denote the residual set $A_{p_i}$ where $p_i$ is the leading/smallest number of the residual set. Consecutive residuals are related by

Anyone schooled in imperative programming ( which I guess is most of the world ;)) would go about implementing a function which returns the first $N$ primes by iteratively filtering and collecting primes in a loop. I should emphasize that when I write iteratively, I mean that the instructions for filtering and collecting primes are done eagerly.

Putting aside the computation for the first $N$ primes, all primes ( which is an infinite set ) can be expressed as a mathematical set, without really specifying how to compute the next prime.

Okay, the second set from above is practically a tautology…but I digress. The point here is that in mathematical notation we are free to declare an expression for the set all primes, even if there is no set notation for it. Generally in mathematics it’s common to express and manipulate infinite sequences and series. Being somewhat aware of Haskell’s declarative nature, I wondered at the outset if I could create an expression for all primes and subsequently generate finite lists of primes as needed. As you might guess the answer is Yes :)

For the uninitiated, referencing Haskell may seem like a non sequitur. Haskell codes are composed of expressions, which are meant to be true statements, as opposed to instructions for the computer to execute in sequence. Expressions in a Haskell program ( or any pure functional language for that matter) are executed as needed, lazily. As opposed to eagerly. Computing the set of all primes via the iterative/imperative prime number sieve implementation would be an infinite loop. Which would never end… And that’s the key difference: declaring/expressing the set of all primes versus computing all primes.

We can easily adapt the sieve described earlier. Haskell is nothing if not functional, so we define the following function,

I first tried to explicitly iterate through a finite list of consecutive numbers; as I was developing I was trying to get a feel for haskell. But I couldn’t see how to generate the whole collection; and doing an infinite loop seemed wrong somehow–the idea of finding the analog of generators in haskell hadn’t occurred to me. Also, probably not idiomatic haskell anyway.

The proper way to express all primes is to recurse, by calling $f$, within its definition, on the residual set. This elegant solution is actually shown ( at the time of this post was written ) on the upper right of the haskell.org landing page. Let , then

When $S$ is infinite, the $RHS$ is also infinite. However the infinite recursion is never realized because of lazy evaluation. In particular the set of all primes is expressed by . To me this recursive definition is a sort of set builder notation. The listing below is the Haskell implementation of $f$, declaration of all primes, and a request for a finite subset of $primes$.

Prelude> filterPrime (p:xs) = p : filterPrime [x | x <- xs, (mod x p) /= 0]
Prelude> primes = filterPrime [2..]
Prelude> take 30 primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]

Losing My Orientation

While trying to grok $SO(3) \cong \mathbb{RP}^3$ and understand various parametrizations of $SO(3)$, I wandered a bit (okay maybe more that litte:) ) and started to think about projective space itself. It is well know that real projective spaces alternate between being orientable and non-orientable, as dimension increases. Specifically odd dimensional projective spaces are orientable but even ones are not. For example, $\mathbb{RP}^1$ and $\mathbb{RP}^3$ are orientable but $\mathbb{RP}^2$ is not.

Jeffery Week’s Space of Space gives a Flatland inspired explanation of orientations on the projective plane and projective 3-space. It’s a fantastic book and a wonderful example of storytelling as a teaching method. In this note, I want to invoke Week’s style and describe orientations on real projective spaces of any dimension.

Lets start with a low dimensional example, $\mathbb{RP}^2$. There are a few ways to describe the real projective plane: affine plane with points at infinity, as a sphere with antipodes identified, or a disc with boundary antipodes identified. We can’t embed $\mathbb{RP}^2$ in 3-dimensional space so we’re forced to work with patches. So, the disc model will serve our purposes best.

Suppose Pac-Man lives on the real projective plane. He’s hungry and sees food down the road. The boundary of the disc is identified, albeit in a reverse oriented way (note the arrows), so Pac-Man sees no obstruction.

Pac-Man normal

What does Pac-Man look like when he crosses the disc boundary?

Antipodal identification means that as Pac-Man crosses the boundary of the disc, he is flipped about his midline. As he emerges from the left side he appears flipped with his left side in view. Of course in 2-dimensional space there is no sidedness, but we can excise the road with Pac-Man ( after all it is just a Möbius Band! ) and embed it in 3-dimensional space to help us visualize Pac-Man’s journey. Another way to think about it without appealing to a 3-dimensional embedding is to imagine Pac-Man passing through the boundary one vertical strip at a time. Each time a strip hits the boundary it is up-down reversed and then sent to the opposite side. I imagine him emerging from the left side like a image being printed by a dot matrix printer. Each passage of the print head depositing a up-down reversed strip of Pac-Man.

Pac-Man mirror reversed

The question remains: Is Pac-Man differently oriented? Imagine an arrow curving the clockwise direction on Pac-Man’s face prior to his passage through the boundary of the disc. That curving arrow is in the counterclockwise direction when he appears from the left; which, to me is a succinct demonstration that Pac-Man’s orientation is reversed.

…So then what is orientation? Well, we’ve seen that Pac-Man is reverse oriented because he’s flipped, once. That could be a definition: one flip. What about two or three, etc.? The boundary identification induces a motion on Pac-Man that leaves his form and shape unchanged. These motions are described by orthogonal groups for continuous objects, like Pac-Man. Though for a more concrete explanation imagine a polygon in 2-dimensions and we only care about how it is rearranged by the topology of the space. These symmetries are described exactly by Dihedral groups; which are composed of flips (reflections) and rotations. It should be clear that rotations are orientation preserving – a clockwise motion rotated remains clockwise. A flip followed by another flip is always a rotation, and rotations form a group. So, we have an answer: an even # of flips preserves orientation, while an odd # of flips reverses orientation.

Lets apply this definition to determine the orientation of $\mathbb{RP}^n$ where $n$ is $3$ or more. We can model $\mathbb{RP}^n$ as a $n$-ball with the boundary antipodally identified. Imagine a boxy Pac-Man floating over a road in $B^n$. Again he sees no boundary because of the identification, nonetheless as he passes through he will be altered somehow.

3D Pac-Man

Lets consider $n-1$ dimensional slices of Pac-Man, since the boundary of the ball is a $n-1$-sphere and we can think of Pac-Man passing through the boundary slice by slice. We can imagine the boundary, when viewed heuristically from a $n-1$-dimensional slice, drawn below, as the inside of a sphere. The horizontal axis representing $n-2$ directions and the vertical axis one direction.

slice view

Each slice is flipped $1 + # { flips in n-2 directions}$ times; a recursive relation–for simplicity let $n$ replace $n-1$; $n$ matches the dimension of the real projective space of interest.

Orientation is the parity of $f$, so $n-1 \mod 2$ represents orientation. So 3D Pac-Man’s orientation in $\mathbb{RP}^3$ is preserved! And in general

Sum of the First $N$ Natural Numbers

Lately I’ve been thinking about the content of my high school mathematics courses. In Runyun’s college algebra and trigonmetry class we were introduced to proofs by induction–of all things–somewhere towards the end of my junior year. An important proof technique, for sure. However, the combinatorial expressions they were applied to, like the sum of first $N$ natural numbers, seemed miraculous. Proof by induction is fairly straight forward. But how does one even guess at a closed formula for such expressions? I remember Runyun saying something to the effect “you need to be smart”. I suppose so, but we can actually construct the closed form of the sum of the first $N$ natural numbers.

First recall the closed formula:

Rearranging the sum doesn’t change the value of the expression so $ 2 \times f(N)$ can also be written

Above $f(N)$ is added to itself, however the second instance of $f(N)$ is written as a sum in reverse order. The $N$ intermediate (or column) sums are all $N+1$. Therefore,