How a beautiful method of building wheels leads to the fastest known prime number sieve

[paulpritchard]

About the author

I'm a retired computer scientist and software engineer, and now a visual artist.

Quick Summary

In 1979 I discovered a very simple algorithm for finding the prime numbers up to some limit N. It is still the (asymptotically) fastest known, taking O(N/log log N) additions. It has a beautiful geometric model involving wheels within wheels. I'd like to help create a video that explains how the algorithm naturally arises from a very simple way to build these wheels.

Target medium

The target medium is a video, which would be freely available on YouTube, and linked to from the recently created Wikipedia article Sieve of Pritchard. I'd like a collaborator who has a good voice (since mine is dreadful) and is skilled at putting an explanatory video together. I have my own ideas, but it would be great to bounce them around with someone else, and I'd like to help create something that is as good as possible. Note that the math used is very simple number theory (though some deeper results would be referenced for the analysis of running time).

More details

The Wikipedia article Sieve of Pritchard is a good starting point. I created all the content for it. I've also created a Youtube video Generating the prime numbers by building successive wheels which might be the starting point for the full video. I did this with Processing.

The story told in the video might start with the wheels animation, then explain the simple number theoretic facts that underlie it, then move to the abstract set-theoretic algorithm given in the Wikipedia article, then discuss how to implement it with an array-based doubly-linked list (which is itself suited to visualization).

The first two references from the Wikipedia article (my papers from 1981 and 1982) contain virtually all of the content. Some preliminary code is available at my github repositories.

Note that the video could be given an initial (Math-) Lord of the Rings theme because the starting point is a simple ring. Perhaps the script on the ring could be pretend-translated to the algorithm for building the next ring (i.e. wheel). Another idea I've had is to give the wheels animations a steampunk flavor (but that is probably beyond my skill set).

Contact details

My email address is oluckyman@gmail.com

Additional context

I'm capable of doing the work myself (storyboarding, scripting, math animations), and could just get someone else to do the voice over. But I'm a perfectionist, and feel that the right collaborator could help deliver a very popular result, suitable for classroom use. (One reason is that I'm no doubt too familiar with the material.) Just look at how many expositions (mostly bad) there are of the Sieve of Eratosthenes!

This post is CC-BY.)

[aaronlearns]

Hi there! VERY interested in collaborating, let me know if you did not receive my email.

[paulpritchard]

Welcome to the team Aaron!