Awkward Primes - Numberphile

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 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 the kith 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 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. 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. connect. No, they're line segments. You just put them down. And of course, there could be primes way out here 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 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. 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 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 lives at stake. — But it's a re It's a legit It's real. 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 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 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 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 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. 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. Like what's the longest line for each number of primes? 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.