If you're seeing this message, it means we're having trouble loading external resources on our website.

Хэрэв та вэб шүүлтүүртэй газар байгаа бол домэйн нэрийг *.kastatic.org and *.kasandbox.org блоклосон эсэхийг нягтална уу.

Үндсэн товъёог

# The prime number theorem

## Video transcript

imagine we listed all integers in a growing spiral and colored the prime numbers blue and left the composite numbers black one interesting question we may ask is how many Prime's are there compared to composites first let's zoom out to see the big picture notice the prime color is dense in the center and slowly drops off in the distance but never seems to end one way I like to think about this is as follows imagine there is a tree at the center which is infinitely high the leaves which drop from this tree represent prime numbers which are scattered unpredictably below dense near the base of the tree and as we walk away from this tree we find fewer leaves though we always find them this is exactly what happens when we look at larger and larger integers we always find more Prime's though the number of primes we find gradually drops the further we looked so let's return to our question how many Prime's are there less than some integer X if we make a table we see the number of primes is always increasing though as we search further we find fewer and fewer let's graph the number of primes found on the vertical axis and the search size X on the horizontal as we zoom out to include billions of numbers notice the curve never flatlines it's always rising albeit gradually first let's think about the density of primes less than some integer X we can find the density by dividing the number of primes found by the search size for the first 100 integers we find 25 primes therefore 25% are prime of the first 1,000 integers we find twelve hundred and twenty nine primes twelve point two nine percent are prime of the first one million integers seven point eight four percent are prime and the first one hundred million integers contained five point seven six percent prime as we search further this density continues to drop though the speed at which it drops slows down here is a graph of the search size on the horizontal axis and the prime density on the vertical notice that as we zoom out the primes are a vanishing proportion of all integers amazingly we find this formula in nature we see it in galaxies storms flowers and even inside our bodies as the design of least resistance known as the logarithmic spiral notice that as the spiral rotates it gets further and further away from the center incredibly the rotation rate of a logarithmic spiral is related to the density of primes as follows we have the number of rotations call this Phi and the distance from the center call this R if we graph Phi against R and zoom out we see they are related according to the natural logarithm this means the natural logarithm of the distance is related to the number of rotations the graph of the natural logarithm is commonly written using the variable names y and x as y equals the natural logarithm of x notice the graph tapers off in the same way the density of primes gradually decreases hmm the final step is to invert this by changing the y axis to 1 divided by the natural logarithm of x and when we zoom out we find the exact same curve generated when we plot the density of primes let's confirm this by overlapping the two plots in green as a graph of the line y equals 1 over the natural logarithm of X and in red is the plot of prime number density up to X as we zoom out they approach each other the further we zoom out the more accurate the green estimate becomes this is known as the asymptotic law of distribution of prime numbers we now have a formula to accurately tell us the density of primes without counting the density of primes up to some integer X is approximately 1 divided by the natural logarithm of X or lon X so let's say you need to know the density of primes between 1 and 100 trillion simple 1 divided by lawn of 100 trillion equals 3 point 1 percent compare this to the actual result from counting all primes which is 3 point 2 percent this is off by 0.1 percent and as we check larger and larger numbers the difference approaches zero realize now that we can use this formula for prime density to estimate the number of primes up to X the number of primes is the area under the density curve for which we can simplify by assuming density is constant so number of primes equals size times density or X divided by lawn X this is the prime number theorem here is a graph of y equals x divided by lon X in blue and in yellow is a plot of an actual count of primes notice as we zoom out these lines eventually overlap as we look to infinity and that is it we have a formula which tells us approximately how many Prime's there are up to any value no counting needed for example let's say we need to know the number of primes less than 100 trillion 100 trillion divided by the natural log of 100 trillion equals 3 point 1 trillion compare this to the actual count which is 3 point two trillion this is over 99.99% accurate even at this relatively small scale so to recap given a search size up to some integer X the prime density is about 1 divided by lawn X and the number of primes is about X divided by lawn X this is the prime number theorem