A Beautiful Algorithm for the Primes

What's the fastest algorithm for generating the prime sequence? Watch a frat bro hunch over a notebook and find out!
.
.
.
Walkthrough (pause, then use “,” and “.” keys to step):

Computing the primes up to 40,000 (also pause and use "," and "." to step):

Wheel generation (with inspirational quotes):

Wikipedia page:

What is a Primorial (really)?

0:00 Intro
0:28 Context
1:23 Prime "Fingerprints"
2:01 Relative Primes
2:27 Primorials
2:47 Bro-terlude
4:12 Primes and Primorials
5:15 Wheels
5:37 Generating wheels
6:59 Ranges of wheels
7:52 The Algorithm
8:24 Dreams of a Bro
8:38 Outro

#SoME2

[danielcarroll]

Boy does this bring me back to my college days in the days beyond recall. The first task in the Fortran lab was to write a program to print all the primes that would fit in a 16-bit signed integer, i.e. up to 32, 767. The grad student lab assistant's program ran faster than everyone else's because he had written an interrupt driven driver for the printer. This allowed the IBM 1130 to calculate while waiting for the printer. But mine ran faster because I knew that if a number was composite at least one of its factors was less than or equal to the square root. Pretty fundamental fact, but the look on his face was priceless as he tried to figure out how this short little program was so fast (relatively speaking).

[johnchessant]

Definitely was not expecting Pritchard to be still alive, what a twist! This feels like something that could've been discovered centuries ago but wasn't; it means even though math has gotten so specialized nowadays there are still plenty of "elementary" gems still waiting to be found!

[avatar]

This is one of those videos I’ll have to rewatch over and over and really work through it 😭

[kyrylosovailo]

Bro, I was thinking exactly about the same algorithm! However I didn't imagine it like wheels, rather repeated sequences.

[j.r.]

I love how you spend an hour explaining what prime numbers are but just zoom through the parts that actually needed explanation.
Maybe skip the comedy and sketches to make up room for more explanation.

[JM-usfr]

Wow I didn't know about Pritchard's sieve. This was really interesting. I thought the sieve of Atkin was the only sieve which could theoretically run faster than the sieve of Eratosthenes, but I guess I was wrong!

[sharpiemcsharp]

Ah I'm pleased to have found a name for this. I'd worked out a similar method, but considering it as sliding windows on the number line rather than wheels. Window starts at the last found prime as is of primorial width.

[BryanLevenson]

Love this idea about prime DNA - never thought about it that way!

[clairecelestin]

I noticed this pattern independently several years ago, but couldn't explain it so clearly. Something else that's interesting about these patterns is that, unless I'm mistaken, every wheel must always contain at least some twin primes, since at each iteration we're eliminating things which have P as a factor and P must always span at least one set of twin primes. This falls a little short of proving that there's an infinite number of twin primes, because as mentioned in the video, the wheels grow very quickly and only a small section of each wheel will appear in the final prime sequence... However, I can't see a way to prevent that small visible section from periodically containing some of the twin primes that remain in the wheel.

[aleksandervadla]

Queen(Queen(Queen(natural science)))=prime numbers

[fabiorota]

This could have been explained much more clearly honestly, when you have been working with something for a long tike all feels obvious, but here we are listening to this for the first time, tyere are many logical eductions let to the viewer, for example the reason why the wheel keeps on working after one lap, its hard if not impossible to understand things without pausing making the experience frustrating.

[pirateskeleton]

There’s another fun property to this sieve method, and that is that the numbers relatively prime to the primordial are all symmetrical along the length. For example, in the case of 30, you have [1 (-29), 7 (-23), 11 (-19), 13 (-17) …] mod 30. Another fun property is that you can use larger circles of the sieve to predict what primes have the highest likelihood to being a twin prime, and definitely discard certain ones from being twin primes, because the twins will maintain their positions with respect to the ones in the circle.

[KeldonA]

My favourite property is that the primorial set (that's what I called it when I first discovered this) contains numbers that are not only all coprime with each other, but are also coprime with each number (x) in the set + n * primorial_set_value.

And there's more.

Take any number x from the set, multiply it with each number in the set in order modulo primorial_set_value, and you will, I kid you not, get back every number in that primorial set, but each with a unique reordering.

When you model the sequence as intervals, it's even more interesting. Firstly, you can clearly see that it produces an infinite seed for EVERY single prime gap from the previous primorial set (though it does not imply infinite prime gaps of any amount).

This view of primes also gives you a remarkably different way of navigating and ordering potential primes.

Aaand, one of my favourites ... going back to the aspect of any x, y pairing from the set modulo the primorial_set_value giving you a value from the primorial set (along with the unique shuffling behaviour) gives you a really simple method of private key encryption!

I never found it faster for generating primes, but this was about 15 years ago, and written in Java in a very OO way (the JVM and most VMs are much more efficient now though).

[idontwantahandlethough]

"bro-terlude" is all I needed to subscribe. I needed more interesting math in my life anyway :)

You sir... you are the Queen AND crown jewels of exhausting analogies.
(but in all seriousness, super interesting video bromanguy, this was really neat!)

[marekmatusiak]

The proof of this solution is surprisingly simple.

It may be interesting that, as you can see, the twin numbers in the form p # + - 1 ends at p = 11.

The second remark is the vertical axis of symmetry of the circle.
In my similar algorithm I use numerical sequences with cyclic differences.
The use of wheels complicates and makes it difficult to understand the subject.

[hirojau]

I can't believe the video was so well made! It was genuinely funny and easy to understand. Also I notice you have an aops book!

[ingiford]

I have played with this, but more as a shifting ruler then a wheel. Good to have a different thought/method of it. Especially the cancellation of removing the smaller one from the larger one.

[joseville]

Great video!

I had used the ideas up to 5:00 before to generate prime candidates that are guaranteed not to be divisible by the first k primes. Ofc, this went further than that!

4:38 You're already using p_n to refer the nth prime, so using p_k to refer to the kth primorial is confusing. Also, it's inconsistent with your earlier notation which used a subscripted capital Pi and your later notation which used a (unsubscripted) Q. Just be mindful of consistency/notation next time. Calling one thing by one name one time and by a different name another time leads to unnecessary confusion. Calling two different things by the same name also leads to unnecessary confusion.

4:45 prime p divides the primorial p_k if only if p <= the kth prime

[lexinwonderland]

...the tissues on the table are a nice touch. (great video btw!!)

[haph]

Neat video. I felt like it went by too fast, as I had to watch it a few times to get what's going on.

Also, are you left handed? The parts where you were writing, you were writing left handed, and covering the text with your hand which made it hard to read. (I doubt this helped the "going to fast" feeling) Maybe try using more of the virtual text, or showing us the text after writing it, and just cover the parts you don't want to show with another piece of paper, revealing the next bit by moving that paper down. (I've seen teachers do this on overheads when they wanted to re-use what the wrote in previously when teaching the same course at multiple times) I guess if you want a third option, you could try using a whiteboard/chalkboard, and write bigger, so that less is covered by your had. Or trick a friend into writing it for you.

Anyways, neat video, though I am curious what the proof is that shows this is the most "efficient" method of generating primes (in whatever metric it is the best).