Skip to main content
Loading Explore guides…
Prime Number Race · Acedra
Home
Explore
Mathematics
Prime Number Race
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
49 segments
Copy
Hide video
0:00
Hey everyone, this is the third in a trilogy of videos with Grant Sanderson from 3Blue1Brown about sequences that don't necessarily do what you'd expect. Links to the first two videos are on the screen and in the video description; you don't have to have watched them to understand this one but you may want to watch them to get the full experience.
0:22
The way this is gonna work, um we're gonna have a race between prime numbers, okay. And we're going to have two different categories: those which are 1 mod 4, meaning when you divide by 4 they leave a remainder of 1, and those which are 3 mod 4. And we're basically just going to count up the prime numbers. So the first one is 2, and 2 is disqualified from the race because it's the oddest
0:43
prime, it doesn't really fit into the pattern of the rest, it's the only one that's even. Next uh we've got 3 and then the next one is 5 and then the next prime is 7. 7 is 3 above a multiple of 4; and then 11 is also 3 above a multiple of 4. And then the next one 13 is just 1 above a multiple of 4, and then the next one, 17. So they seem pretty neck and neck so far as we're kind of counting up. So after 17 we've got 19, which is 3 above a multiple of 4, and then 23 which is 3
1:12
above a multiple of 4. And then the next one will be 29, and then after that we're going to have 31, 37. And one thing you might notice is that so far in the whole race, even though it's pretty neck and neck, team 3 has always been in the lead so far. And you might say, okay, that seems maybe just kind of at random that that would be the case; but actually if we continue this race - and if you want I can give you some visuals that like show the race continuing on -
1:36
- (Brady: Do you know someone) (who's good at making mathematics visuals?) - I I can call a guy. But uh it will be- it'll always be 3 who seems to be in the lead. And you know they're pretty close, they're a pretty even balanced like you might expect; but if it was completely random, if it was just random which bucket you're tossing it into you wouldn't expect such a long streak for there to be a particular winner.
2:11
And in fact it continues going on until the first time that team 1 mod 4 is gonna break into the lead is going to happen at the prime 26,861. But even then the next prime after that is going to be 26,863. So that was just one brief moment of peeking into the lead and then after that they do stay in the lead quite a bit longer, team 3 mod 4. And then the next time that team 1 is able to get ahead is going to happen at 616,841. And it keeps the lead a little bit longer then
2:48
but then 3 takes over. And if you're looking at most of the numbers, most of the time it seems like- you know 99% of the time the team that's in the lead is team 3. And this was actually a conjecture that someone made that said: is it the case that as we let n tend to infinity and we consider at all of the points of the race, how often was it the case that team 3 was in the lead? Does that percentage of the time approach a 100%? Interesting question.
3:13
You might expect it to be true, if there's any reason that there should be more 3s then you might expect it to either fall, you know, completely 50/50 or completely to 100%. But, you know, I think the question I'd like to talk about a little is why would you expect something like this to happen? It feels like the prime shouldn't have a bias one way or another, um why does this team get any kind of advantage? - (Well primes do have a bias, they have a bias towards odd numbers )
3:36
Fair point, okay, so there's a very strong bias towards odd numbers; um and maybe you're on to something there that we shouldn't treat primes so randomly. But often you have this criteria that's once you rule out the obvious things that primes aren't going to do, the things based on divisibility constraints, their behavior feels random. And this this heuristic actually helps people make a lot of conjectures and a lot of it kind
3:59
of susses out- uh turns out to be true once you delve into it. And so something like this- another one um that's in in same vein, let's say we look at the last digits of the primes. Is it going to be a 1? Is it going to be a 3? Is it going to be a 7 or is it going to be a 9? If you perform that race, as you do that longer and longer they all tend to be about 25% of the time, but two of them are distinguished winners. They tend to be winning
4:23
the race even if it's just by a little bit. So in the long run it tends to be about 25% percent of them primes end in a 1 but there is just this gentle bias. And you might ask why; okay there's a very- you say the biased to be odd, there's a very clear reason they're like strongly biased to be odd. What is the what is the reason then that 3 mod 4 would have this kind of advantage? - (You have- so are you) (confirming to me that it does have an advantage? Is it- has
4:45
that conjecture been proven or?) That's- that's a really interesting question which we will get to at the end of the video actually. That- for the moment let's just consider that conjecture something that has strong empirical suggestiveness um but it's very tricky to prove that kind of thing and then the answer is surprising and we will get to it. Ah, here's a question of how much detail we want to go into. I think this is a pretty satisfying intuition, if you're willing
5:09
to take on faith one magical fact that I present to you. So the story is going to start outside of here but instead with a formula a lot of people might know for pi of all things: 1 over 1 minus 1 over 3 plus 1 over 5 minus 1 over 7... So I'm basically toggling whether I add or subtract, and I'm going over all of the odd numbers. So this isn't primes, it's all of the odd numbers that I'm doing. In fact I'm going to give a name to let it be kind of clear,
5:37
this plus minus pattern where I'm going to make up a function that seems needlessly complicated right now that I'm going to call chi of n. And basically chi of n is going to be defined to be +1 if n is 1 mod 4, it's going to be -1 when n is 3 mod 4, and then I could maybe say that it's 0 you know if n is even. And so basically what we're doing is we're adding up chi of n divided by n. Overly fancy way of saying, I'm toggling between plus and minus on the odd numbers, but
6:08
it's it's nice to have a name for that function for what we get to in a moment. Now some people might know that this actually converges, if you look at this on the number line you have your 1, you subtract back a little bit to 1/3, plus 1/5, minus 1/7 - and I can even draw that out a little bit if we want. We've got 1, and if we subtract 1/3 you land somewhere here,
6:30
if we add 1/5, you know, because that step is smaller we don't quite get to that 1. And then if we subtract 1/7 that step was smaller still and so you'll basically be bouncing back and forth. You know you're going to converge to something and the value you converge to is pi-fourths. That is actually not important for where we're going but the fact that it's a number- it's going to be something. Who doesn't love pi right? Right now pi is almost just like an imposter into our story,
6:57
it doesn't really have much of importance other than the fact that it's something. Now the magical fact, the absolute magical fact, is the number theorists favorite way to take a logarithm. And it works like this, we're going to take our series - and in order for this trick to work, there's just a couple criteria the series has to have. There's got to be a number associated with every natural number, so we might think of 0s for all of the evens here, um and then it has to
7:24
have the property that when I multiply the terms associated with two numbers like 3 and 5 that the product of the terms corresponds to the product of those numbers. So in this case 3 times 5 is 15 and negative 1/3 times positive 1/5 is indeed negative 1/15. It's not exactly obvious but this will hold no matter which ones you look at. So for example if we take 1/7 and 1/3: negative 1/7 times
7:49
negative 1/3 will be positive 1/21. And if we go- it would be a positive 1/21. So as long as that property holds you can do this magical thing to take a logarithm, where I'm going to say, I don't like composite numbers, I'm going to kick out my composite numbers. If you're not prime um either you're not going to be in the club or you're going to get a strong punishment based on how not prime you are. So 1 we don't like you, 1 gets kicked out entirely.
8:15
1/3 you get to stay. So your term gets to stay, 1/5 you get to stay, 1/7 you get to stay. 1/9 we say okay, 1/9 you're not prime, I don't like you, but you're just a prime power. At least you only have one prime factor so you're not as bad as those dirty composites like 6 or 15. So we'll let you stay, but because you're the square of a prime we're going to give you a punishment by reducing you by 1/2. So it gets to stay but
8:42
only half as powerful. And then it goes on: 1/11, you're prime, you're cool, you get to stay. 1/13, you're prime, you're cool, you get to stay. 1/15, not only are you not prime you have two different prime factors, you're very composite, you're out of the club entirely. And I'll just do a couple more to kind of make it clear: we've got 1/17 - and notice I've got two pluses in a row but that's
9:02
because we kind of kicked out the minus. All we care about is whether this number is 1 mod 4 or 3 mod 4. So I'll be subtracting off 1/19, I will also be subtracting off 1/23,
9:15
because uh 1/21 got kicked out for having too many factors. 1/25 we're going to have to keep him but divide him by 2. A way of saying, okay you're not prime, but you're just a prime power, and because you're the square of a prime you get reduced. And just to make this extra clear, the next one that we see is the cube of a prime, 1/27, so I'm going to reduce it by 1/3 that gets me 1/ 27. In general
9:40
what we're doing here is we're taking 1 over k times something divided by p to the power of k; where p is a prime number, k could be anything, and we're basically taking this chi function of p to the k. Which is just a way of measuring, are you plu- are you 1 mod 4 or 3 mod 4? So that might be how you write this in general. - (So Grant if this is) (some kind of shortcut, it's not feeling like a shortcut but all right) - So it's it's not a shortcut, it's just the coolest way-
10:09
because if you- okay I do this, I do this completely random procedure to my series, and you'd say what is it going to equal? I don't know, some completely different number that's completely unrelated to the thing that we started with. Because you went, primes are such a random thing that you're hacking them off at these seemingly random points, you should expect nothing normal to come from this. But the beauty is that what you get is just the natural log of
10:30
whatever it was before. And um we could do this with a lot of different things actually: another famous sequence people might know is if we take 1 over 1 + 1 over 4 + 1 over over 9 and we add up the reciprocals of all the square numbers. So we kind of go on and we're always adding up 1 over n squared. This has the property we care about where when you multiply corresponding terms, what
10:55
you get corresponds to their product. If we do the same game, we kick out some prime numbers, we keep the prime powers but we reduce them a little bit, uh it'll again be a logarithm. So this sequence happens to be pi squared divided by 6, and if we do our whole like prime number game - whatever we want to call it - what we'll get will be the natural log of pi squared over 6. And so that that holds in
11:18
general and it's it's the weirdest possible way to take a logarithm. Why am I talking about this? The reason is that if we look at the sequence that we have here; now we have uh mostly primes, we've got some prime powers in there, but it's mostly prime numbers and we're kind of adding or subtracting them and this might give us a little bit of an indication that if they're to stay roughly evenly balanced, you know, that would justify the fact that we're equaling some
11:45
constant. Where if there were systematically way more that are 1 above a multiple of 4 or way more that are 3 above a multiple of 4, the whole series might diverge. A couple other magical facts I'll throw down will be that this series diverges absolutely, which is a way of saying if we changed all of the minuses to be pluses and we just asked, hey I'm going to add up the sizes of all of these terms, does that converge to any number? It goes and blows up to infinity.
12:10
And what that kind of tells us is if we look at the camp that are all of the things that are being added and all the camp that are being subtracted, both of those blow up to infinity. And so when we're cutting it off at a finite point they have to stay roughly balanced with each other. So this tells us two important things: one is why we have a kind of even balance in our race, and it's not that-
12:29
(But this was- but you did this with the odd numbers, this is just prime numbers but it's) (the same sort of principle) - The key equation at this point is to focus on what happens after we do our log trick where all the stuff that remains in the series is mostly primes. So what I could say is, if we kick out all the prime powers those- they don't actually amount to that much. They converge absolutely, um and in fact they have to be just bounded by some constant. And so
12:56
we could say if we ignore all the prime powers we would have the sequence which sometimes you're adding a prime, sometimes you're subtracting it, and because it equals just a constant, just some number, we can know that neither one of those camps blows up much faster than the other. However, all of the nuance for who's winning the race happens when we really think hard about what happens to those
13:16
prime powers. Here's the like intuition - it is not a proof - but here's the vague intuition for why you might expect 3 mod 4 to be winning this race even if you didn't start performing the race. If you knew some analytic number theory, you had a strong familiarity with the series, your prediction might be I'm going to put my money on horse number 3. And how do I want to draw this? I'm going to
13:39
kind of have two buckets here; this is going to be all of the stuff that we're adding in our sum and then this is going to be all of the stuff that we're subtracting. And we're just going to kind of- what kind of things are we adding? What kind of things are we subtracting? So the stuff that we're adding, it's all of the primes which are 1 above a multiple of 4 so- or rather the reciprocals of those. So 1/5, 1/13, 1/17 - these are the kind of things that we're adding. But
14:05
there's also some squares of primes that we're adding: in fact critically the square of every prime. Because even if you started from someone who is going to be a negative, like -1/3, once we look at the square term corresponding to it it's something that we're adding. So also in this camp of things that we're adding is you have things like one half of 1 over 9, or you also have things like one half of 1 over 25, or one half of 1 over 49. So
14:34
all of the primes are represented here with their squares. And then in terms of the cubes, those ones are also kind of accounted for but only the ones which are one above a multiple of 5. So for example 5 cubed is going to make it in, 1 over 125, but uh 3 cubed is actually something that we subtracted so it's accounted for in the other one. And maybe I'll even write that over here, so we've got -1/3 by 1 over 27. This is- the point I want to make I
15:01
guess is if we look at this negative bucket - I'll also write up in the top - also subtracting all of the primes associated with things that are 3 above a multiple of 4. So we're subtracting 1/3, subtracting 1/7, subtracting 1/11. What I want you to notice is how all of the all of the even powers necessarily end up in this positive bucket. So we also have you know 1/4 outside of 1/81 - all of the even powers end up here. This gives a bias in some sense in the direction
15:27
of our adding bucket. So a priori, if we just say looking at all of these terms what might we we expect? We'd say, well, there's this little bit of a bias for those in the adding bucket to just have more numbers. If there were always the same amount of numbers 1 above a multiple of 4 and 3 above a multiple of 4, because of those powers of the primes that show up here, that gives a little
15:51
bit of added weight to this positive bucket. So if we know that we actually want these terms to be roughly evenly balanced, in the sense that they're canceling each other out so much that they get to- I mean the natural log of pi/4, it's a very small number but the critically is it's a constant, it's not like something that suggests one half of this uh plus/minus bucket is going to tend off
16:13
to infinity. It means in order to make up for the fault that they get by not getting of the any of the fourth powers or any of the squares or any of the sixth powers, we need just a little bit more primes to start with, a little bit more that are in this um 3 mod 4 bucket. Again, it's not a proof, but that's where you might get this little intuition that uh in order for this equation to balance out
16:33
you need a little leg up in that second camp. What this would suggest is that there should be a bias for 3- team 3 to stay in the lead more, there should be a bias where there'll always be a few more um primes that are mod 3 to make up for this uh imbalance that they get once you introduce the powers. But the- what you might expect is saying how often is it the case that they are in the lead? If
16:56
we're watching this horse race, is it the case that after some amount of time team 3 always stays in the lead there on thereafter? Okay that's a little bit strong. The softer consideration, which was the conjecture made, is that the proportion of numbers for which when you look at everything up to that um the team 3 is in the lead tends to be closer and closer to 100% as you look at more and more
17:19
numbers. So as this horse race is proceeding, and you widen and widen your glance, you say at various different checkpoints on their track a vast majority of those checkpoints should be ones where team 3 is in the lead. Now interestingly that's not true; and if you look at what's the percentage of numbers where team 3 was in the lead on your way up it kind of toggles. It's always very very big it's- you know 99%, 98%, close to 100% but forever and forever it just sort of
17:48
wanders around and it doesn't approach anything. Let's say you look at the first billion numbers. You might notice that as we look at the race up to that billion numbers, 99.5% of the time team 3 was in the lead; but uh there was some times that team 1 was in the lead. Then you might ask, okay what if I looked at the first trillion numbers, the first quadrillion numbers. You might expect, oh when I look at the first quadrillion then it's 99.99% of the time that team 3 is in the
18:12
lead - that's not true. As you look at it then, you know, maybe it's like 98% of the time that team 3 is in the lead. So they do trade off but there's a clear bias for team 3, and the question is, you know, how often do they trade off? And uh turns out if you measure in a slightly different way- so we're going to change the rules of the race, where rather than counting each prime um exactly you kind of discount them by the- the reciprocal of that prime.
18:38
If- for the sake of the proofs I guess that must have made it uh easier to prove, but it turns out the team 3 will tend to be in the lead, as you look at more and more numbers it's in the lead 99.59% of the time. So as you look at bigger and bigger numbers it tends to be the case, with the appropriate metric, that this is the amount of time the team 3 is in the lead. So it's it's almost always in the lead but not almost always in the usual mathematician sense of the phrase.
19:08
Because usually when they say 'almost always' they mean like 100% uh or it tends to 100%. So instead it's in the normal human way of using the word almost, almost always uh the case that uh team 3 is in the lead. But it is not such a clean fact that it's just 100% or 0. - (Does it ever get to) (a point where it will be in the lead forever or?) - No - (So no matter where you are in the number line)
19:33
(team 1 has always got another moment in the front coming?) - Exactly, team 1 will always have a chance. And in fact in this metric, as you look at bigger and bigger swaths, it has 0.5% of the time it'll be up there. - (It's the Little Engine That Could) - Yes yes it really is, it really is. (It's the tortoise!) - It is the tortoise, slow and steady um every now and then it beats the hare - even if the hare seems systematically better.
19:59
Thanks for watching this video. If you want to see more from Grant you probably already watch his channel 3Blue1Brown, there'll be links in all the usual places. I'd also like to say thank you to Numberphile's Patreon supporters who make it possible for me to travel and have the time to meet with people like Grant and make these videos. If you'd like
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat