Prime Distribution Meets Set Cover: Insights from the Line Game

Name: 4211 - The Party Pooper Prime - Numberphile
Uploaded: 2026-04-07T14:24:25.783315+00:00
Duration: 12 min 13 s
Channel: Numberphile
Description: Summary and key takeaways on 4211 - The Party Pooper Prime - Numberphile: Summary & Key Takeaways, covering Prime Distribution Primes appear irregular on the

Numberphile

Apr 07, 2026

•

12 min video

•

2 min read

YouTube video ID: VFoIPlUalRY

Source: YouTube video by Numberphile — Watch original video

PDF

Primes appear irregular on the number line, growing like weeds that sprout in unpredictable places. Yet the counting function π(n), which records how many primes lie below a given integer n, behaves with surprising smoothness. The classic approximation π(n) ≈ n / log n captures this regularity, and the appearance of the transcendental log n in the formula feels almost magical.

The Line‑Covering Game

To explore this tension, each prime is plotted as a point (k, primeₖ), where k is the index of the prime in the ordered list. The challenge becomes: what is the smallest number of straight lines needed to cover the first n points? Lines are treated as independent segments; they need not connect or form a continuous shape.

This formulation is a concrete instance of the set‑cover problem. Every possible line defines a set of prime points it can cover, and the task of selecting the fewest lines that together cover all points mirrors the classic NP‑complete optimization. Because the problem is computationally hard, exact answers rely on exhaustive search rather than simple formulas.

Empirical Findings

Computational work extending up to the 861st prime uncovers a strikingly irregular sequence of minimal line counts. Long flat stretches emerge where a single line sweeps up many consecutive primes. Such a line earns the nickname “golden line” for its efficiency.

Occasionally a prime appears that cannot be accommodated by the existing collection of lines; adding a new line becomes unavoidable. This prime is labeled an “awkward prime” because it forces a step up in the line count. A particularly memorable case is the “party pooper” prime, which terminates a streak of 112 consecutive primes that were covered by only 69 lines.

The full sequence of minimal line requirements has been entered into the Online Encyclopedia of Integer Sequences as A373813. Among the recorded patterns are a streak of 48 consecutive primes covered by 68 lines and the longer 112‑prime streak ending at the party pooper prime.

Quotable Moments

“Primes are both very irregular and very irregular.”
“This is one of the most astonishing things in mathematics, the smoothness of this function π of n.”
“An awkward prime is a prime that causes a step up.”
“The party pooper prime.”
“It’s a mathematical thing. It’s a deadly serious thing.”

Takeaways

Primes look irregular on the number line but the counting function π(n) follows the smooth approximation n / log n.
Plotting each prime as (k, primeₖ) lets us ask how many straight lines are needed to cover the first n points.
Determining the minimal line cover is a variation of the NP‑complete set‑cover problem, so exact solutions require computational search.
Computations up to the 861st prime reveal long stretches—such as 112 consecutive primes covered by only 69 lines—interrupted by “awkward primes” that force an extra line.
The resulting sequence of minimal line counts is recorded as OEIS A373813, with the “party pooper” prime marking the end of the 112‑prime streak.

Frequently Asked Questions

What is an "awkward prime" in the line-covering game?

An awkward prime is a prime that forces the minimal number of covering lines to increase by one; when the current set of lines can no longer cover the next prime without adding a new line, that prime is labeled awkward.

How does the line-covering problem relate to the set-cover problem?

The line-covering problem can be modeled as a set‑cover instance where each possible line represents a set of prime points it covers; finding the smallest collection of lines that together cover all points is exactly the set‑cover optimization, which is NP‑complete.

Who is Numberphile on YouTube?

Numberphile is a YouTube channel that publishes videos on a range of topics. Browse more summaries from this channel below.

Does this page include the full transcript of the video?

Yes, the full transcript for this video is available on this page. Click 'Show transcript' in the sidebar to read it.

Helpful resources related to this video

If you want to practice or explore the concepts discussed in the video, these commonly used tools may help.

Graph Paper Notebook For Math Recommended

Provides a structured grid for plotting prime number coordinates and visualizing geometric patterns in number theory.

Amazon →

Prime Numbers: A Computational Perspective Book

Explores the intersection of prime number theory and computational methods, mirroring the podcast's focus on algorithmic analysis.

Amazon →

Large Dry Erase Grid Board

Allows for large-scale visualization of coordinate plotting and line-covering games discussed in the episode.

Amazon →

The Music Of The Primes Book

Provides historical and theoretical context on the distribution of prime numbers and the Riemann Hypothesis.

Amazon →

Links may be affiliate links. We only include resources that are genuinely relevant to the topic.

Summarize another video

Full Transcript YouTube

I have a story to tell you about prime
numbers which I think is pretty
interesting and it's a new way of
looking at primes. I it's ridiculous to
say there's anything new about primes,
but you'll see. I'm going to um start by
remarking that primes are both very
irregular and very irregular. They're
irregular because when you look at where
the primes are on the number line, they
grow like weeds. Every so often there's
a weed, a prime number, and then there's
a gap and then there's another weed. On
the other hand, if you look at the
picture in the large between one and a
million, say the mathematical notation
for that is pi of n. Pi of a million is
the number of primes between 1 and n.
Look at the the primes between one and
50,000. How many are there? And it sort
of looks like this.
Rather surprisingly, when you get up to
50,000,
it's basically a straight line. So,
they're not that irregular. The famous
mathematician said, "This is one of the
most astonishing things in mathematics,
the smoothness of this function pi of
n." What it is, pi of n is very close to
n / log n. And that really is
astonishing when you consider how
irregular they are at the beginning.
This line, it's not straight. It's not
n. It's n over log n. But log n changes
very slowly when you So when you draw
this, it looks pretty straight. There's
a slight droopiness to it. Neil, does it
astonish you? Because primes are so
fundamental, right? They're these
fundamental important things. And I know
like they do seem a little random at the
start, but wouldn't something so
fundamental, wouldn't it make sense that
it was really simple and elegant?
>> Why don't I think it's remarkable? Why
log of n of all things? You know, why
not
square root of n say? Why log? I mean,
log is one of those transcendental
functions. It's a surprise. It looks
pretty linear. So I thought to myself,
how linear is it? What if we really
tried to put straight lines through the
primes? So what I want to do is look at
points where the xycoordinates
the x coordinate is going to be um k
and the y coordinate is going to be the
kith prime prime k.
So it's begin going to begin the first
prime is two. So the first point on this
graph is going to be 1 comma 2. The
second prime is three. So it's going to
be 2 comma 3 and then the third prime is
five and we get 3a 5 and so on. I want
to look at those points and see how
linear they are. All right. So I've made
a piece of graph paper here going 0 1 2
3 and so on. And here's the prime. So
the first prime is two. So that means we
put a point at the coordinates 1 comma
2. That's called a prime point. The
second prime is three and it's the point
2a 3. Then five then 7 then 11 then 13
17
19
and then the next one is 23 and then 29
and so on. There are the prime points
and what I want to know is how close are
they to being on straight lines. I'm
going to define a sequence which is the
number of lines we need to cover the
first n primes with the smallest number
of lines. So let me just do it and
you'll see. So what's what's a of one?
How many lines do we need to cover the
first prime? We need one line. It can be
anywhere you want. Just put it through
that. So if n is one, the number of
lines is one. What if n is two? We want
to have a line through the first two
primes. All right. I'll put a line. It
goes through that point and that point
as a straight line. One line is enough.
two primes. I need one line. What about
three primes? Dot dot dot. I want to
have a line. There's no line that goes
through those three points. Obviously, I
need two lines to cover the three
points. What about uh four primes? 357.
357 are in a straight line. So, I can do
four primes with two lines. What about
five primes? I can do with two lines. I
use one line to cover three, five, and
seven. and another line to cover two and
11.
>> Oh, that the line doesn't don't have to
touch each other, right?
>> They can touch each other.
>> They don't have to join. It doesn't have
to.
>> They don't have to connect. No, they're
line segments. You just put them down.
And of course, there could be primes way
out here on the on the line. We'll worry
about that later. I'm just trying now to
cover the primes with as few lines as
property. I'm I'm getting lines of
primes. How many do we need? How many
lines do we need? All right. So I did
with uh with five. 1 2 3 4 5. What if we
have one more? The line through those
two does not go through that one. So I
think we're going to need another line
for six primes. We need three lines
>> as we get higher and higher. This line
here you used for example to join um
three, five, and seven. Later on
>> there may be a better way to do it.
>> You might not that line might not exist.
>> That's right. Yeah. Yeah. I mean the
line exists but we don't need to use it.
We're looking for the best way to cover
the primes with straight lines. This is
actually a famous uh an example of a
famous computer science problem which is
called set cover. You you you want to
cover you you've got your set of objects
and you've got a set of things you can
use to cover them and you want to find
the optimal the smallest subset of your
objects to cover the things you're
trying to cover. Here we're trying to
cover the primes and we're using lines.
Is this like a mathematical thing or is
this a game? Like
>> it's a mathematical thing. It's a deadly
serious thing. Oh yes.
>> Deadly serious.
>> No. Well, not deadly serious. No,
there's no money at stake. There's no no
lives at stake.
>> But it's a re It's a legit It's real.
It's It's hardcore math.
>> It's hardcore and it's new. The first
time we need three lines is for the for
six primes. When we get to seven primes,
we want to cover 1 2 3 4 5 six seven. We
want to go all the way out to here. And
we can do it if we're clever with three
lines. We can repeat lines through a
point. And that and that is no. So seven
primes we can do with three lines.
>> Apparently you can look it up in this
thing called the online encyclopedia.
>> You certainly can. Yeah, it's sequence A
373813. You can look it up. So as I
said, this is something that computer
science people will say, "Ah, set cover.
I can do that." It's it's one of those
NPcomplete problems. So, it's not going
to be easy to solve, but they do have
good computer programs for attacking it.
And my friend Ma Max Alex ran his
program ran set a good set cover program
up to 410
primes. It looks like this. And more
precisely, here it is. And you can see
it's increasing and it's a bit
irregular. There are long flat
stretches. And you get a long flat
stretch when you get a really good line
that has a lot of primes on it. You
don't you can just as we saw here, you
don't have to increase.
>> Or do they have names? Are they like
called golden lines or
>> No. No, they don't.
>> They're like a seam of gold. They they
are like a seam.
A quick footnote. Since we filmed this,
Max Alex save has calculated the lines
required all the way out to the 861st
prime. The plot looks like this. And
there are two really interesting golden
lines here and here. There are 48
consecutive primes that can be covered
by 68 lines. Then a whopping streak of
112 primes can be covered by 69 lines.
But after that, nothing Max has found
has come even close.
And there's no reason to be found for
this golden sweet spot
that the sequence increases. It looks to
me like it's roughly linear. I suspect
it's actually about going like x over
log x because that's in the nature of
the game. But there are long stretches
where you get a really good line that
covers a lot of primes. And so you don't
have to increase the number of lines
until you get to the next awkward prime.
And it looks like that. So
>> that's a good name. An awkward prime. An
awkward.
>> An awkward prime is a prime that causes
a step up.
>> A step up. Yes. They're the awkward
primes. Yes. Good. Yes.
>> Can we can we have that name?
>> All right. Sure. And the these
>> Can you put is Can you put that in the
OEIS?
>> I think. Yeah.
>> And will you call them awkward primes?
>> Yeah. Sure. Sure. Okay.
>> That's on tape now. That's on tape.
>> An awkward prime causes a step up in the
number of lines needed in your little
line game here.
>> Well, another footnote. You just
witnessed the birth of the awkward
primes. Here they are highlighted on the
original sequence. there in the blue.
And here it is, perhaps the most awkward
prime of them all. The one that ends
that whopping streak of 112 primes in a
row that can be covered by 69 lines. The
party pooper prime. And here they are,
their very own entry in the online
encyclopedia of integer sequences.
Amazing. I'm a very proud co-father.
>> Got so many questions coming into my
head.
>> Yeah. Yeah. Like what's the longest line
for each number of primes? What's the
longest line that's got three primes on
it and four primes on it? And
>> I'm coming to that.
>> Like that Robert Graves poem about the
Welsh the creatures that came out of the
sea in Harl.
>> That's a different story.
>> Okay.
But the last line is, "Ah, but I was
coming to that."
>> Puzzle alert, people. Puzzle alert. The
diabolical geniuses over at Jane Street
have cooked this one up to test your
number skills. This is what it looks
like. There are more details over on
their site and via the links below. It
is a doozy. For those who don't know,
and there can't be many number file
viewers who don't, Jane Street is our
channel sponsor. They're a quantitative
trading firm with offices in New York,
London, Hong Kong, Amsterdam, Singapore.
They use techniques from machine
learning, distributed systems,
programmable hardware, statistics to
trade on markets around the world. And
when they aren't doing that, well, they
don't mind a puzzle or two. In fact,
there's a whole puzzle page on their
site, which I've linked to down below.
And while you're there, check out all
the open rolls at Jane Street they're
currently hiring for. Even though
they're a financial firm, they don't
expect you to have a background in
finance or any specific field really.
They're just looking for smart people
who enjoy solving interesting problems.
Now, why don't you go try those puzzle
links?
It's not just it's the concatenation,
the stringing together of all the
chunks. This whole thing is the
sequence. And what we're drawing
actually is a pin plot officially.
There's one other sequence I've seen in
the past. This was Yan Ritz Van X
sequence that I did a video for you
about. The Van X, the famous Van X
sequence.