Awkward Primes - Numberphile

[00:00] I have a story to tell you about prime

[00:01] numbers which I think is pretty

[00:04] interesting and it's a new way of

[00:06] looking at primes. I it's ridiculous to

[00:08] say there's anything new about primes,

[00:10] but you'll see. I'm going to um start by

[00:14] remarking that primes are both very

[00:16] irregular and very irregular. They're

[00:18] irregular because when you look at where

[00:21] the primes are on the number line, they

[00:23] grow like weeds. Every so often there's

[00:26] a weed, a prime number, and then there's

[00:27] a gap and then there's another weed. On

[00:29] the other hand, if you look at the

[00:31] picture in the large between one and a

[00:34] million, say the mathematical notation

[00:38] for that is pi of n. Pi of a million is

[00:40] the number of primes between 1 and n.

[00:43] Look at the the primes between one and

[00:46] 50,000. How many are there? And it sort

[00:49] of looks like this.

[00:53] Rather surprisingly, when you get up to

[00:55] 50,000,

[00:58] it's basically a straight line. So,

[01:00] they're not that irregular. The famous

[01:03] mathematician said, "This is one of the

[01:06] most astonishing things in mathematics,

[01:08] the smoothness of this function pi of

[01:11] n." What it is, pi of n is very close to

[01:16] n / log n. And that really is

[01:18] astonishing when you consider how

[01:20] irregular they are at the beginning.

[01:22] This line, it's not straight. It's not

[01:24] n. It's n over log n. But log n changes

[01:27] very slowly when you So when you draw

[01:30] this, it looks pretty straight. There's

[01:32] a slight droopiness to it. Neil, does it

[01:34] astonish you? Because primes are so

[01:36] fundamental, right? They're these

[01:37] fundamental important things. And I know

[01:40] like they do seem a little random at the

[01:44] start, but wouldn't something so

[01:45] fundamental, wouldn't it make sense that

[01:47] it was really simple and elegant?

[01:52] >> Why don't I think it's remarkable? Why

[01:55] log of n of all things? You know, why

[01:58] not

[02:00] square root of n say? Why log? I mean,

[02:04] log is one of those transcendental

[02:08] functions. It's a surprise. It looks

[02:11] pretty linear. So I thought to myself,

[02:14] how linear is it? What if we really

[02:16] tried to put straight lines through the

[02:19] primes? So what I want to do is look at

[02:23] points where the xycoordinates

[02:26] the x coordinate is going to be um k

[02:31] and the y coordinate is going to be the

[02:33] kith prime prime k.

[02:39] So it's begin going to begin the first

[02:41] prime is two. So the first point on this

[02:44] graph is going to be 1 comma 2. The

[02:46] second prime is three. So it's going to

[02:49] be 2 comma 3 and then the third prime is

[02:51] five and we get 3a 5 and so on. I want

[02:54] to look at those points and see how

[02:56] linear they are. All right. So I've made

[02:59] a piece of graph paper here going 0 1 2

[03:02] 3 and so on. And here's the prime. So

[03:06] the first prime is two. So that means we

[03:08] put a point at the coordinates 1 comma

[03:12] 2. That's called a prime point. The

[03:15] second prime is three and it's the point

[03:18] 2a 3. Then five then 7 then 11 then 13

[03:24] 17

[03:26] 19

[03:28] and then the next one is 23 and then 29

[03:31] and so on. There are the prime points

[03:33] and what I want to know is how close are

[03:36] they to being on straight lines. I'm

[03:38] going to define a sequence which is the

[03:40] number of lines we need to cover the

[03:43] first n primes with the smallest number

[03:45] of lines. So let me just do it and

[03:47] you'll see. So what's what's a of one?

[03:49] How many lines do we need to cover the

[03:51] first prime? We need one line. It can be

[03:53] anywhere you want. Just put it through

[03:54] that. So if n is one, the number of

[03:57] lines is one. What if n is two? We want

[03:59] to have a line through the first two

[04:01] primes. All right. I'll put a line. It

[04:03] goes through that point and that point

[04:04] as a straight line. One line is enough.

[04:07] two primes. I need one line. What about

[04:09] three primes? Dot dot dot. I want to

[04:12] have a line. There's no line that goes

[04:14] through those three points. Obviously, I

[04:17] need two lines to cover the three

[04:19] points. What about uh four primes? 357.

[04:22] 357 are in a straight line. So, I can do

[04:25] four primes with two lines. What about

[04:28] five primes? I can do with two lines. I

[04:30] use one line to cover three, five, and

[04:33] seven. and another line to cover two and

[04:38] 11.

[04:38] >> Oh, that the line doesn't don't have to

[04:40] touch each other, right?

[04:41] >> They can touch each other.

[04:43] >> They don't have to join. It doesn't have

[04:44] to.

[04:45] >> They don't have to connect. No, they're

[04:46] line segments. You just put them down.

[04:48] And of course, there could be primes way

[04:50] out here on the on the line. We'll worry

[04:53] about that later. I'm just trying now to

[04:55] cover the primes with as few lines as

[04:58] property. I'm I'm getting lines of

[04:59] primes. How many do we need? How many

[05:02] lines do we need? All right. So I did

[05:04] with uh with five. 1 2 3 4 5. What if we

[05:06] have one more? The line through those

[05:08] two does not go through that one. So I

[05:11] think we're going to need another line

[05:12] for six primes. We need three lines

[05:15] >> as we get higher and higher. This line

[05:17] here you used for example to join um

[05:20] three, five, and seven. Later on

[05:24] >> there may be a better way to do it.

[05:25] >> You might not that line might not exist.

[05:27] >> That's right. Yeah. Yeah. I mean the

[05:28] line exists but we don't need to use it.

[05:30] We're looking for the best way to cover

[05:33] the primes with straight lines. This is

[05:35] actually a famous uh an example of a

[05:38] famous computer science problem which is

[05:39] called set cover. You you you want to

[05:42] cover you you've got your set of objects

[05:45] and you've got a set of things you can

[05:47] use to cover them and you want to find

[05:48] the optimal the smallest subset of your

[05:52] objects to cover the things you're

[05:54] trying to cover. Here we're trying to

[05:56] cover the primes and we're using lines.

[05:59] Is this like a mathematical thing or is

[06:00] this a game? Like

[06:02] >> it's a mathematical thing. It's a deadly

[06:04] serious thing. Oh yes.

[06:06] >> Deadly serious.

[06:07] >> No. Well, not deadly serious. No,

[06:08] there's no money at stake. There's no no

[06:10] lives at stake.

[06:11] >> But it's a re It's a legit It's real.

[06:13] It's It's hardcore math.

[06:14] >> It's hardcore and it's new. The first

[06:16] time we need three lines is for the for

[06:19] six primes. When we get to seven primes,

[06:23] we want to cover 1 2 3 4 5 six seven. We

[06:25] want to go all the way out to here. And

[06:26] we can do it if we're clever with three

[06:29] lines. We can repeat lines through a

[06:32] point. And that and that is no. So seven

[06:34] primes we can do with three lines.

[06:37] >> Apparently you can look it up in this

[06:38] thing called the online encyclopedia.

[06:40] >> You certainly can. Yeah, it's sequence A

[06:44] 373813. You can look it up. So as I

[06:46] said, this is something that computer

[06:49] science people will say, "Ah, set cover.

[06:52] I can do that." It's it's one of those

[06:54] NPcomplete problems. So, it's not going

[06:56] to be easy to solve, but they do have

[06:59] good computer programs for attacking it.

[07:12] And my friend Ma Max Alex ran his

[07:17] program ran set a good set cover program

[07:21] up to 410

[07:23] primes. It looks like this. And more

[07:26] precisely, here it is. And you can see

[07:31] it's increasing and it's a bit

[07:33] irregular. There are long flat

[07:35] stretches. And you get a long flat

[07:37] stretch when you get a really good line

[07:40] that has a lot of primes on it. You

[07:42] don't you can just as we saw here, you

[07:44] don't have to increase.

[07:46] >> Or do they have names? Are they like

[07:47] called golden lines or

[07:49] >> No. No, they don't.

[07:50] >> They're like a seam of gold. They they

[07:52] are like a seam.

[07:55] A quick footnote. Since we filmed this,

[07:57] Max Alex save has calculated the lines

[08:00] required all the way out to the 861st

[08:03] prime. The plot looks like this. And

[08:05] there are two really interesting golden

[08:07] lines here and here. There are 48

[08:13] consecutive primes that can be covered

[08:15] by 68 lines. Then a whopping streak of

[08:19] 112 primes can be covered by 69 lines.

[08:24] But after that, nothing Max has found

[08:26] has come even close.

[08:29] And there's no reason to be found for

[08:32] this golden sweet spot

[08:36] that the sequence increases. It looks to

[08:40] me like it's roughly linear. I suspect

[08:42] it's actually about going like x over

[08:45] log x because that's in the nature of

[08:47] the game. But there are long stretches

[08:49] where you get a really good line that

[08:52] covers a lot of primes. And so you don't

[08:54] have to increase the number of lines

[08:56] until you get to the next awkward prime.

[08:59] And it looks like that. So

[09:02] >> that's a good name. An awkward prime. An

[09:04] awkward.

[09:05] >> An awkward prime is a prime that causes

[09:07] a step up.

[09:08] >> A step up. Yes. They're the awkward

[09:10] primes. Yes. Good. Yes.

[09:12] >> Can we can we have that name?

[09:13] >> All right. Sure. And the these

[09:15] >> Can you put is Can you put that in the

[09:17] OEIS?

[09:17] >> I think. Yeah.

[09:18] >> And will you call them awkward primes?

[09:20] >> Yeah. Sure. Sure. Okay.

[09:22] >> That's on tape now. That's on tape.

[09:25] >> An awkward prime causes a step up in the

[09:28] number of lines needed in your little

[09:30] line game here.

[09:32] >> Well, another footnote. You just

[09:34] witnessed the birth of the awkward

[09:36] primes. Here they are highlighted on the

[09:39] original sequence. there in the blue.

[09:44] And here it is, perhaps the most awkward

[09:46] prime of them all. The one that ends

[09:47] that whopping streak of 112 primes in a

[09:51] row that can be covered by 69 lines. The

[09:54] party pooper prime. And here they are,

[09:57] their very own entry in the online

[09:58] encyclopedia of integer sequences.

[10:01] Amazing. I'm a very proud co-father.

[10:07] >> Got so many questions coming into my

[10:09] head.

[10:10] >> Yeah. Yeah. Like what's the longest line

[10:12] for each number of primes? What's the

[10:14] longest line that's got three primes on

[10:16] it and four primes on it? And

[10:17] >> I'm coming to that.

[10:20] >> Like that Robert Graves poem about the

[10:23] Welsh the creatures that came out of the

[10:25] sea in Harl.

[10:29] >> That's a different story.

[10:30] >> Okay.

[10:32] But the last line is, "Ah, but I was

[10:34] coming to that."

[10:38] >> Puzzle alert, people. Puzzle alert. The

[10:42] diabolical geniuses over at Jane Street

[10:44] have cooked this one up to test your

[10:46] number skills. This is what it looks

[10:48] like. There are more details over on

[10:51] their site and via the links below. It

[10:53] is a doozy. For those who don't know,

[10:55] and there can't be many number file

[10:57] viewers who don't, Jane Street is our

[10:59] channel sponsor. They're a quantitative

[11:01] trading firm with offices in New York,

[11:03] London, Hong Kong, Amsterdam, Singapore.

[11:06] They use techniques from machine

[11:08] learning, distributed systems,

[11:10] programmable hardware, statistics to

[11:12] trade on markets around the world. And

[11:14] when they aren't doing that, well, they

[11:17] don't mind a puzzle or two. In fact,

[11:19] there's a whole puzzle page on their

[11:21] site, which I've linked to down below.

[11:23] And while you're there, check out all

[11:25] the open rolls at Jane Street they're

[11:26] currently hiring for. Even though

[11:28] they're a financial firm, they don't

[11:30] expect you to have a background in

[11:32] finance or any specific field really.

[11:34] They're just looking for smart people

[11:36] who enjoy solving interesting problems.

[11:39] Now, why don't you go try those puzzle

[11:41] links?

[11:45] It's not just it's the concatenation,

[11:48] the stringing together of all the

[11:50] chunks. This whole thing is the

[11:53] sequence. And what we're drawing

[11:55] actually is a pin plot officially.

[11:58] There's one other sequence I've seen in

[12:00] the past. This was Yan Ritz Van X

[12:04] sequence that I did a video for you

[12:06] about. The Van X, the famous Van X

[12:10] sequence.