Primes are like Weeds (PNT) – Numberphile

Primes are like Weeds (PNT) – Numberphile

DR. JAMES GRIME: So another
prime-generating formula is actually the most important
one of all. It’s called the prime
number theorem. So let me write it out. I think it deserves
being written out. Really important result
in mathematics. It’s so important that you
can refer to by its TLA. You can refer to it by its
three-letter acronym. Just call it PNT. People know what PNT is. It’s the prime number theorem. It’s that important. And the prime number theorem is
about how many primes are there, less than a number n. So how many primes are there
less than a billion? Something like that. And so the formula says
that the number of primes less than n– well, the symbol for
that is pi of n. Now, don’t be confused. This pi is not 3.14. It’s nothing to do with pi. We’ve reused the symbol
for something else. So it’s P for prime. So the number of primes
less than n. And this is approximately n
divided by natural log of n. A couple of things to say,
because some of you won’t be familiar with that
natural log of n. Some of you will. But for the ones who aren’t
familiar, I’ll try and quickly show you. It’s just a function. You could call it–
it’s just a thing. Any number– you
pick a number. Any number, like n, can be
written this way, as e to the power x. e is another constant. It’s 2 point– I never remember what it is. 718, something, something,
something. So any number can be written
in that way. It’s 2.718 to the power
of something. And the log of n is this bit. It’s x. It’s the power. So that’s what a log is. If I plot log of x, it
looks like this. This is actually growing,
but it grows really, really slowly. I think the log of
1 billion is 21. So you put in a big number, and
you’re actually getting a very small number out. It’s always getting bigger. It’s actually tending
to infinity. One more thing to say– this twiddle is a new
symbol to you. Tilde– or twiddles, as I like
to call it– it’s a new symbol. What it means is if you divide
those two things– so I’m going to divide
them, like that. If you divide those two things,
that’s tending to 1 as n gets bigger. That’s what it means. It’s slightly technical. You can say approximately
equal to, if you’re happy with that. But that has a proper meaning. So what it’s told us
is it tells us how many, on average– it gives an approximation, at
least– of how many primes we can expect less than
a number– 1 billion, 10 billion,
a googol. But we can then get some
results from that. That means that the proportion
of prime numbers is– well, if we divide by n, the proportion
of primes less than n is 1 over log n. So if we’re talking 1 billion,
I said the log of 1 billion was 21. So the proportion of
primes is 1/21. It’s like 5%. 5% of numbers less than
1 billion are prime. You can call it a probability
if you want. If I picked a number at random,
what’s the probability that it’s going to be
a prime number? It’s 5%. What does it mean? It does mean that the prime
numbers are getting rarer, more spaced out, as the
numbers get bigger. So this proportion is
getting smaller. The gaps– we can write the
gaps, as well. The average gap between primes
is now equal to log of n. So if n was 1 billion again–
let’s stick with that– it turns out the average gap
between the primes is 21. Some have bigger gaps. Some have smaller gaps. Some are twin primes. But the average gap is 21. BRADY HARAN: Let me give
you a number, and you give me all the stats. I’ll give you a number. Give me the state of the nation
for the first 5 and 1/2 billion numbers. DR. JAMES GRIME: 5
and 1/2 billion– 5 and 1/2 billion is this. So 1 billion has nine 0’s. So this is 5 and 1/2 billion. We’re going to take the log
of that, the natural log. What have we got? 22. BRADY HARAN: 22.4. DR. JAMES GRIME: 22.4. BRADY HARAN: So what
do you now know? DR. JAMES GRIME: So I know that
the proportion of primes less than 5 and 1/2
billion is 1/22. Again, it’s just like– well, let’s see. Is it 4%? Let’s see if we can do it. Yeah, so about 4% of numbers
less than 5 and 1/2 billion are prime. The average gap is about
22.4, 22, 23. So that’s a lot of
information. And then one more thing, then. One more thing we can
learn from this– our prime number formula. The n-th prime twiddles,
or is approximately, n lots of log n. So you might see where
this comes from. If the average gap is log n, and
you want to know the n-th prime, you can multiply by n. You add the gaps all together. The n-th prime is approximately
n log n. Which means 5 and 1/2 billion,
the 5 billionth, 500 million da-da-da-da-da prime is– it actually gets better
results the bigger the number is. So it helps you find– but it is an approximation,
rather than those formulas, the prime number formula
giving ones. One more thing I wanted
to say about this– this average gap we’ve
discovered, which is log n– and I said it was an average. So sometimes you get
bigger than that. Sometimes you get
a twin prime. You make an average of
it, you get log n. The gaps do have
bounds on them. You can’t go as big
as you like. There’s actually a little– it’s called Bertrand’s
postulate. And it says if you pick any
number– let’s pick the number n– he said that there will be
a prime that is bigger than n and smaller than 2n. So you can’t have a gap
that is too big. There’s a little
rhyme for this. The rhyme is, “Chebyshev said
it, and I’ll say it again, there’s always a prime between n
and 2n.” And if you put n as a prime instead– let’s take it as the
n-th prime– then the next prime you’re
looking for has to be sandwiched between prime
and 2 times the prime. Let’s pick a prime. Prime’s the nice version
to do it in. Well, pick a prime. BRADY HARAN: 11? DR. JAMES GRIME: 11’s fine. Right, so let’s have 11. All it’s telling you is that
you’re guaranteed to have a prime between 11 and
22, which is true. So your gaps can’t
get too big. For primes over 100, you
can do better than 2. That can actually shrink
down to 1.2. So that gives you quite
a narrow gap. So that just means that the
primes can’t have very, very, very long gaps between them. So they’re quite regular. Primes are always turning up. They’re fairly regular. And there’s infinitely
many of them. But they’re like weeds. They’re always popping up. You can’t get rid of them. There’s another prime. You don’t go for too long
without another prime popping up. BRADY HARAN: Surely when we
get up into sort of the Graham’s numbers of the
world, those weeds become a bit more sparse. DR. JAMES GRIME: They
become spaced out. But proportionally, compared
to the size of numbers that you’re using, the proportion is
actually very, very tiny. In absolute terms, they’re
really spaced out. But as a proportion to these
huge numbers we’re talking about, they’re close. This prime number formula is
actually the easy version of the prime number formula. There’s more sophisticated
versions of this. They look the same, but they’ve
added on extra terms. And so you can see that the
error is sort of zigzagging around 0-ish.

48 thoughts on “Primes are like Weeds (PNT) – Numberphile

  1. Because(2,3) it's seed spread further grow more weed, for example : 5=5/2+1/2=3, grow 5 prime by 2 and EULER PRODUCT (2-1)/2, 11=11/3+1/2-5/6+2/3+1=5, from 3,(1*2)/(2*3), 29=29*4/15+1/2-5/6-9/10+29/30+2/3-14/15+4/5+2=10, from 5 and 4/15, it keep growing never stop, like Euclid's infinite prime number.

  2. I love your primes Dr Grimes but your acronyms need polishing. Acro = initial, nym = word.
    PNT is not a word (unless, perhaps, you pronounce it punt). But in any case there's a much more elegant way to say "three-letter [non]acronym". The word is trigram. It even sounds mathematical.

  3. what if I found a way to make a primality test that does not involve module operations or probability? 🙂

  4. (@6:23): …looks to me like this postulate could be used as a proof for why the number 1 isn't prime.

  5. Primes. The higher they get, the more spaced out they get.
    What's that got to do with weed?

    Anyway, weeds have roots. Natural roots.
    And they don't have logs.

  6. So if ln(x) tends towards infinity and the approximation approaches being exactly correct doesn’t that mean that prime numbers make up 0% of all whole numbers

  7. Nice video, one thing thoug; I'm afraid you calculated 5.5 milliard, instead of 5.5 billion. Not a real bit deal, the US-Americans have that messed up permanently, and for that reason, English actually allows this mistake now. I thought I would point it out though.

    Thank you for the video.

  8. I was doing some math and found that (2n)+(n^2)-1 created primes very well if n is even. Example: (2 x 99922222222220)+(99922222222220^2)-1 is prime. I also saw that up to 200 being n (leaving out odd numbers) it spit out a prime 42% of the time.

  9. E = 2.7 1828 1828 45 90 45 2 3 5 360
    2.7,then 1828 twice,then the angles in an eqilateral triagle,then the first three primes,then the sum of the oofs in a psqare.

  10. But what if primes were divisible by more numbers than 2? And I'm totally doing a lateral swipe to imaginary numbers but it could be useful

  11. How to quickly check if a number N is prime: check all prime factors under √N, if they all aren't factor N is prime

  12. I think that an equation for nth prime that is more accurate is (ln(n) + ln(ln(n) * n))/2*n. It is more accurate because the nth prime is a larger number than n and so has bigger spaces between the primes that n. So, n *ln(n) will always underestimate the value of the nth prime.

  13. You can have arbitrarily large gaps between primes. n! + (any number 1 through n) will not be prime, giving a gap of n.

  14. Composites are just a combination of primes, so that means composites are also just a combination of the primes I smoke everyday

  15. hi. i just noticed. what proof do you have that x/lnx as x approaches infinity is equal to 1???? because if u try to use calculator and increase the value of x little by little, you will get infinity too. assume x/lnx has a limit, then you can use lhopitals rule right?
    because inf/inf… then =1/(1/x) =x = inf not 1. pls help

Leave a Reply

Your email address will not be published. Required fields are marked *