Awkward Primes - Numberphile

Key Takeaways

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 know it's ridiculous to say there's anything new about primes, but you'll see. I'm going to start by remarking that primes are both very irregular and very regular. They're irregular because when you look at the 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 1 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 1 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 over log n. And that really is astonishing when you consider how irregular they are at the beginning. This line, well, 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? I 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 xy coordinates the x coordinate is going to be um k and the y's coordinate is going to be the kth 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,2. The second prime is three, so it's going to be 2,3 and then the third prime is five and we get 3,5 and so on. I want to look at those points and see how linear they are. All right. So, I 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,2. Let's call it a prime point. The second prime is three and it's the point 2,3 then five then seven 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 the line that goes through that point and that point, 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 four primes? 3 5 7. 3 5 7 are in a straight line. So, I can do four primes with two lines. What about five primes? I can do it with two lines. I use one line to cover 3 5 and 7 and another line to cover 2 and 11. Oh, that the line doesn't don't have to touch each other, right? They can touch each other. Oh. 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 on the line. We'll worry about that later. I'm just trying now to cover the primes with as few lines as possible. 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 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 3 5 and 7. Later on There may be a better way to do it. >> You might not that line might not exist later. >> Yeah, 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 an example of a famous computer science problem, which is called set cover. You you you want to cover You've You've got a 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? >> Well, not deadly serious. No, there's no money at stake. There's no no lives at stake. >> a real 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 six for six primes. When we get to seven primes, we want to cover 1 2 3 4 5 6 7. 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 known. So, seven primes we can do with three lines. Apparently, you can look it up in this thing called the online encyclopedia of You certainly can. Yeah. It it's sequence A00373813. You can look it up. So, as I said, this is something that computer science people will say, "Oh, set cover. I can do that. It's It's one of those NP-complete problems. So, it's not going to be easy to solve, but they do have good computer programs for attacking it." And my friend Max Alekseyev ran his program ran set 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 at just as we saw here, you don't have to increase. Oh, do they have names? Are they like called golden lines or >> No. No, they don't. >> a seam of gold. They They are like a seam. >> [music] >> A quick footnote, since we filmed this Max Alekseyev has calculated the lines required all the way out to the 861st [music] prime. The plot looks like this, and there were two really interesting golden lines here and here. There are 48 consecutive primes that can be covered by 68 lines. >> [music] >> 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. >> [music] >> 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. >> prime. >> 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 it 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. >> [laughter] >> 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. They're in the blue. And here [music] 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 [music] party pooper prime. And here they are, their very own entry in the online encyclopedia of integer sequences. [music] Amazing. I'm a very proud co-father. >> [music] >> Got so many questions coming into my head. 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. AH! AH, LIKE [laughter] THAT. The Robert Graves poem about the Welsh, the creatures that came out of the sea in Harlech. That's a different story. >> Okay. >> [laughter] >> 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 Numberphile 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 >> [music] >> 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 roles 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? >> [music] >> 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 Jan Ritsima van Eck's sequence. And I did a video for you about the van Eck's, the famous van Eck sequence.