Proof due to Idris D. Mercer: www.idmercer.com/primes-density.pdf Join Wrath of Math to get exclusive videos, lecture notes, and more: ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin More math chats: ua-cam.com/play/PLztBpqftvzxXQDmPmSOwXSU9vOHgty1RO.html
I don't have that problem; usually I'm taking subsets of the seven deadly sins, so if the sin of gluttony is already in my set, adding it to the set doesn't change it into a different set. Unless I'm using multisets, but that's only for the most egregious sinners.
I do enjoy the joke at 4:50 where you just ignore that question and move on But if anyone IS curious, the only thing relating pi and prime counting is that "prime counting function" and "perimeter of a circle" both start with the letter P, so mathematicians used the Greek letter for P (pi) to denote it.
@@YAWTonwhile that is true, people without a strong math and engineering background may not know that for some disciplines log (x) means logₑ(x), while others assume log₁₀(x). As a matter of fact, I have seen people in the computer science field assume it is log₂(x). It can be very confusing.
Let's use ln for base e, lb for base 2 and ld for base 10. Could even do lo for base 8 and lx for base 16. And log has always to be used with specific base. To me that'd make lots of things way less confusing
@@2dark4noirFor the proof shown in the clip, the base of the log is irrelevant, except when where the base is specified (base 4, toward the end of the proof).
I would encourage anyone, especially people who are new to proofs, who has worked through this proof to open the PDF that one can find in Shaun's pinned comment. Shaun's exposition is excellent. The source document is terse and typical a of journal article (just 2 pages and wide spaced sentences with an "and this..." + stuff then, "implies" + stuff style). Learning to read proofs is a part of the game.
The way I learned logarithm notation is that "log" without a specified base is the common logarithm or base 10 log. "ln" is used for natural logarithm or base e log
In my experience log meaning base e is used by math people (because log base 10 is rarely relevant to pure math), log meaning base 10 is used by other disciplines
at 12:05 you mention that a log without a base written is assumed to be the natural log, but anyone who has used the log button on a casio calculator would know, the tradition is that the natural log is written as ln(x), and log(x) is log base 10. It's fine if you wanted to use log as the natural log, but its not the common way to do things, and your explanation was potentially misleading
2:48 I think for cryptographers, it absolutely IS a trivial task to find prime numbers. A consequence of the prime number theorem is that randomly choosing a number less than X has approximately a 1/ln X probability of landing on a prime, which will hit a prime (on average) in polynomial time. Testing if a number is prime can also be done in polynomial time, with something like Miller-Rabin if you want speed, or something like the AKS test if you want certainty. So finding primes is actually very easy!
For other people reading this, it's important to note that "bounded gap" in this context refers to having infinite primes with a gap lower than the bound. It does _not_ mean there are no, or even finitely many, primes with gaps greater than that bound.
4:50 your video editor, covertly speaking into a walkie talkie: he's trying to tell them what he knows... walkie talkie: remove any trace of that footage from existence
I think most people watching this would expect the default base of a logarithm to be not e but 10, since the common log base tends to be the base of the counting system in use (so in computer science contexts, for example, base 2 might be expected). for natural log I think most would expect it to be written as ln(x).
@@nickronca1562 That's just because a calculator needs to have both, so the notational difference of logx vs lnx is very convenient. but in many contexts the only log needed is base e log, and so log itself is allowed to stand for this.
depends on the context. For example when you analyze algorithms, the default base for log will be 2. In many cases it's logarithmic growth that is important rather than a specific base so it's important to just be mindful of what you're reading
Actually, there are just as many primes as there are in other numbers, they are just less dense. You see there are an infinite amount of numbers and there for an infinite amount of primes, you may be inclined to believe that these are different sizes of infinity, but they are not because you can match each prime up to infinity to a normal number like so: 2,3,5,7,11,13,17 1,2,3,4,5, 6, 7 Now it is true that within a given finite range there are very few primes. Like let’s say 1-100, if you try to match up each prime to a normal number , you will run out of primes very quickly, but this is infinity we are talking about and no matter how much add to infinity it’s still the same amount, so because of that we can just continue to match up numbers without running out.
In the nineties, I worked with an HP 250 system that was designed to do medical billing. I had to frequently resize the databases and could only use primes. I never actually knew why?🤔
This Channel is going miles..... Really great and fun stuff..... I never thought math could be fun..... Just don't forget me when u become famous, man 😊😊
The theory might be correct, but in practise, I gotta' tell you that prime number density tapers off VERY slowly. I've written a prime generator myself, aiming to eventually use the list to find large prime-less spans; and there are many centuries of numbers that contain 3-6 primes even beyond 580 billion. So the prime # density is still more than half of what it was between, say, 100 and 200.
Yeah I regretted that comment while editing; I just wanted to brush it off and move on; but I wish I hadn't insulted e; I love e. I have since apologized to e privately
You said something between the lines that many children in prime school intuitively understand. That some infinite sets of numbers on numberline could have small densities (38:00)... Is there any connection between density and something close to Cardinality - Countable, and Uncountable sets? Could we distinguish that all Countable sets have finite density when approaching infinity, but uncountable sets will have infinite density? And there would be probably some exceptions... like Rational numbers with infinite density... and you would be able probably to try device density by something similarly to Computational complexity (if something has density limited by some formula then its "local Cardinality in infinity" would be limited to value of this formula...
that's... an interesting thought i figured you do understand that cardinality and natural density are very different concepts, and they're merely tangent here... i dont think there's a particular relationship between them, precisely because of the counterexample you mentioned, but it's interesting to ask what "kind" of sets of R have infinite density?
It's fascinating to me that prime numbers are both infinite (the amount of them) and infinitesimal (the amount of them compared to non-Prime numbers, though both are countable, hence the same size infinities) at the same time
The same holds for the squares, triangular numbers, powers of 2, fibonacci numbers, numbers without a digit 0 in them, etc. etc. Worlds of wonder await you. 😉
37:20 I don't think it is all that difficult using properties of inverse functions. Because the original exponential function has domain R, the range of the logarithm is R by definition of inverse functions. Because it is an inverse function, it must be a bijection from its domain to its range. Therefore it either is strictly decreasing or strictly increasing. Because the base is >1, the logarithm is strictly increasing to positive infinity in the limit.
I actually did a similar proof a while back. But, I diverged majorly in step 4. I'm going to denote p(n) to be the number of primes less than or equal to n, as my keyboard doesn't have a pi button. (Lame, I know) Going from p(2^n) - p(2) < 4/1 + 8/2 + 16/3 + 32/4 + 64/5 + ... + 2^n / (n-1) I'll denote a(m) = 2^m / m-1. So, this is p(2^n) - p(2) < a(2) + a(3) + ... + a(n). Next off, we'll note that the first two terms are both 4, and that p(2) = 1. So, p(2^n) - 1 < 4 + 4 + a(4) + a(5) + ... + a(n), or p(2^n) < 9 + a(4) + a(5) + ... + a(n). Next, let's look at a(m+1)/a(m), with the constraint that 4 = 2/m, and 3/2 4. So a(m+1)
3:34 it's not entirely correct, you either had to exclude the numbers less or equal 1 from the possible values of x, or you had to say that m can be any integer (e.g. for x=1 if you said m=0, it would satisfy the inequality - it is the only m integer that does - but you said m has to be greater than 0, or if you take 0.15, the only m integer satisfying the statement, would be -1). It doesn't affect the proof btw, just it bugged me a bit.
There is a paradox in the holding that there infinite numbers and infinite primes. The products of primes, and their products, crowd out at an ever increasing rate later primes. Primes are “infinite,” but 5heir products are infiniter.
Ni Nils, thanks for your support! The two types of exclusive videos I make are the non-math exclusive videos of which I make a few each month and upload to UA-cam for members and to Patreon. There are a lot more normal math lecture videos which are uploaded to UA-cam and available only for channel members; due to Patreon's various video restrictions it's not feasible to upload all of these to Patreon, but if you send me a message on there with the group of videos you're wanting to watch, I can probably find a way to make them available to you (alternatively you could cancel Patreon and join on UA-cam where those member only videos are, but I know that's a pain).
I’m grateful primes get arbitrarily sparse on average or applications using factoring of numbers over, say, 10⁶ would get way more cumbersome and expensive than they are: this way one can just store factorings from the start or factorize more or less quickly using precomputed primes up to that boundary.
When I saw the root x at the end I thought hang on why doesn't this prove the Riemann Hypothesis...? Then I remembered about the 8. Still, I'd want some explanation why the argument cannot be refined to tighten the bound sufficiently to remove this extra factor of 8. I suppose something worth mentioning is that we cannot upper bound pi(x) by x/logx + some multiple of root x, since the RH only refers to the limit, not a stubborn inequality for all x...
the extra factors arent the issue here, the thing is that you're merely giving an upper bound... the riemann hypothesis is about the assymptotic behaviour of π(x)
That depends on how you define numbers. I guess for any set of numbers, there is always a bigger set of things you can call numbers. So that property becomes fairly trivial quite quickly. Like, the reals form 0% of the complex numbers, which form 0% of the quaternions, which...
@@DarinBrownSJDCMathI’ve always heard that if u were doing natural log its ln(x). If log(x) is supposed to be the same thing, why would we even invent the term ln(x)?
@@blockyshapes7001 Notational conventions sometimes differ based on who is using the notation. This is the case for "log" without a given base. If you're reading a scientific paper, or general usage, it's (probably) base-10 common log. However, if you're reading a paper in number theory or other areas of pure math, it's going to be natural log. If you read a computer science paper, it might even mean log base-2. Similar things happen in math all the time with notations and even definitions. Just ask a mathematician what a "ring" is, and you might get 3 different answers, depending on their research specialty.
Very nice proof! Very satisfying to see how everything comes together. I came up with my own “proof” that does something similar. It isn’t as rigorous, but I think it’s a bit more intuitive. If you start with the first prime, 2, you know that it is impossible for any even number after 2 to be prime. Before considering any primes after 2, half of all integers after 2 are “prime candidates”, while the other half are composite. Now, let’s look at the next prime, 3. Because 2 and 3 are coprime (they don’t share any prime factors), we know their multiples cycle independently of each other. Because of this, we know that a third of the “eliminated” integers are multiples of 3, and a third of the prime candidates are multiples of 3… which eliminates them. 1/3 of all integers after 3 are not multiples of 2 or 3, so they are our prime candidates. This cycle continues. 5 makes it so that 1/5 of the remaining candidates are eliminated, making the new ratio 4/15. 7 eliminates 1/7 of that, making the new ratio 24/105. Every succeeding prime multiplies the fraction of future prime candidates by (p-1)/p, which, being less than 1, always makes the ratio smaller. While, admittedly pretty shoddy as a proof, demonstrates at an intuitive level that it becomes more and more difficult to find primes the more primes have already been found.
Three comments (two short, one long): 1)I think you should've mentioned that the proof you are presenting is (a version of) a proof due to Pafnuty L'vovich Chebyshev, when he famously proved the Bertrand's postulate. (I see that in the description you quote Idris D. Mercer, who unfortunately doesn't quote Chebyshev either). 2)It was perhaps worth mentioning that the estimate you obtained is up to a constant coincides with the prime number theorem, so in a sense with this elementary argument we are already only a constant away from the truth. But, if you only want to show that the density goes to zero there is a much simpler proof that I will outline in the third part. 3)We begin with a lemma: product of ((p-1)/p) over all the primes is zero. Assume for now that the lemma is true and let's estimate pi(n). Since by the lemma the product is zero, we can find finitely many primes such that the product is less than eps/2, that is (p_1-1)/p_1 *(p_2-1)/p_2*...*(p_k-1)/p_k < \eps/2. What are the primes up to n? Well, first of all we might have all the p_m for 1
The abundance of primes declines to the limit of sequential differences, perhaps about 10^16. That low local abundance persists to infinity, compiling to reach 29.4%. See my demonstration: ua-cam.com/video/dksj4ikvgJM/v-deo.html
Do you mean can we check it by hand? Probably not, given its magnitude. It has more digits than there are seconds in a year. We do need to trust that the testing algorithm was correctly programmed and run.
Even more pedantically, the set of all prime numbers would have a cardinality less than the set of all integers because the set of all prime numbers is a subset of the set of all integers and does not contain all integers, so they cannot be the same size and thus there are less prime numbers than integers (kinda)
@@calamitalcomputers even _more_ pedantically, any infinite subset of the natural number has cardinality aleph 0, and so must have the same size. In this example, there’s a one-to-one mapping between primes and integers (or from primes to naturals, then to integers) so the two must have the same cardinality.
On an unrelated note: There's the same number of: * Infinite sequences of digits 0,1 * Infinite sequences of natural numbers * Infinite sequences of real numbers * Continuous functions on real numbers
False, there are infinite primes, just way less than there are non-primes, and a numbers 'prime-ness' becomes more and more difficult to prove as they get bigger.
There's the same number - of both there are countably many. (The two sets can be mapped one-to-one.) For a trivial subset of your set: consider the set {1, 11, 111, 1111, ...} That's obviously a countably infinite set.
@pietroppic That just means that the prime numbers are _more common_ than natural numbers that do not contain a 5 in decimal notation. That is _not_ the same thing as how many there are when infinities get involved.
@@MikeRosoftJH I understand you learned a little about a fancy thing at some point (countability). That is not however the ONLY reasonable way to talk about "more of these than those". Another way, more discriminating: long run PERCENTAGE of one vs the other. This way is much more illuminating in the case of primes vs other countably infinite subsets of N.
The point of the video though is that you can prove that limit approaches zero without having first proven that pi(x) approaches x/ln(x) as x grows to infinity.
No, just a good title. Everybody knows there's infinitely many primes, so the title begs the question of what I could possibly mean - and there will obviously be math involved in demonstrating something about primes and their rarity.
But there's an infinite amount of them. It's like, some infinities are larger than others. Believe it or not, the only reason we know there's infinite primes, is because there's infinite numbers. That's just how infinity works.
...That's not how we know there are infinite primes. Obviously, there needs to be infinite natural numbers for there to be infinite primes, but that's not enough. For instance, the only "prime" (abusing terminology a bit here) under addition is 1.
@@sillymel That is how we know. Because there's always one more when you multiply a concurrent set of primes, and just so you know, it isn't always prime when you multiply a series of primes and add one. That is how we know. There's no trick to it, it's just that there are primes, and infinite natural numbers, so infinite primes. 1 isn't prime. 2 is.
I'm aware how the proof works, and yes, there is a trick to it. You pretty much just said what the trick is: If you take the _first_ n primes (picking the first ones is important; this won't with any arbitrary string of consecutive primes) and add 1, the result is always another prime. That doesn't work with any old subset of the natural numbers. As for the other thing, I'm aware that 1 isn't normally prime. That's why I put "prime" in quotes. To be more specific about what I meant: 1. In this case the natural numbers must include 0, the additive identity. 2. A natural number is a prime-analogue with respect to addition if it can be expressed as the sum of natural numbers in exactly two ways.
Turns out I over-simplified things because I didn't want to explain proof by contradiction here. Ignore that part about 1 plus the product of the first n prime numbers being prime as well. I'm not quite sure I understood what you were getting at in the first half of your. Numbers can't be concurrent. Did you mean consecutive? I really hope there's more to your argument than "Primes exist. There are infinite numbers. Therefore there are infinite primes.
@sillymel if you multiply the 1st n primes and add one, it doesn't always leave a prime. Sometimes, it leaves a composite number, which has a prime factor that is larger than the largest prime in the original calculation.
Proof due to Idris D. Mercer: www.idmercer.com/primes-density.pdf
Join Wrath of Math to get exclusive videos, lecture notes, and more:
ua-cam.com/channels/yEKvaxi8mt9FMc62MHcliw.htmljoin
More math chats: ua-cam.com/play/PLztBpqftvzxXQDmPmSOwXSU9vOHgty1RO.html
I LOVE Maths
Why did we take this massive detour instead of using the x/logx approximation? The limit of 1/logx, x to inf is zero, no?
"Did you know that there are very few primes?"
"Yeah? How many are there exactly?"
"Infinitely many."
"Ooookay"
I hate it when the sin of gluttony gets in my subset which inadvertently turns it into a different set
Same, it's a massive pain!
I don't have that problem; usually I'm taking subsets of the seven deadly sins, so if the sin of gluttony is already in my set, adding it to the set doesn't change it into a different set. Unless I'm using multisets, but that's only for the most egregious sinners.
I do enjoy the joke at 4:50 where you just ignore that question and move on
But if anyone IS curious, the only thing relating pi and prime counting is that "prime counting function" and "perimeter of a circle" both start with the letter P, so mathematicians used the Greek letter for P (pi) to denote it.
@@twixerclawford also ‘Product’
A difference in notation: for me and at least one other commenter, log is in base 10 and ln is in base e.
The proof make no assumptions about the unspecified base of log, so the specification of the base is irrelevant.
Me too
@@YAWTonwhile that is true, people without a strong math and engineering background may not know that for some disciplines log (x) means logₑ(x), while others assume log₁₀(x). As a matter of fact, I have seen people in the computer science field assume it is log₂(x). It can be very confusing.
Let's use ln for base e, lb for base 2 and ld for base 10. Could even do lo for base 8 and lx for base 16. And log has always to be used with specific base. To me that'd make lots of things way less confusing
@@2dark4noirFor the proof shown in the clip, the base of the log is irrelevant, except when where the base is specified (base 4, toward the end of the proof).
I would encourage anyone, especially people who are new to proofs, who has worked through this proof to open the PDF that one can find in Shaun's pinned comment. Shaun's exposition is excellent. The source document is terse and typical a of journal article (just 2 pages and wide spaced sentences with an "and this..." + stuff then, "implies" + stuff style). Learning to read proofs is a part of the game.
The way I learned logarithm notation is that "log" without a specified base is the common logarithm or base 10 log. "ln" is used for natural logarithm or base e log
Depends, a lot of people agree with you though; perhaps my experience is unusual
In my experience log meaning base e is used by math people (because log base 10 is rarely relevant to pure math), log meaning base 10 is used by other disciplines
this is the smallest prime numbered comment. lol.
smart
No
1 is not a prime
2
5 is prime
at 12:05 you mention that a log without a base written is assumed to be the natural log, but anyone who has used the log button on a casio calculator would know, the tradition is that the natural log is written as ln(x), and log(x) is log base 10.
It's fine if you wanted to use log as the natural log, but its not the common way to do things, and your explanation was potentially misleading
The convention in most areas of pure math (such as number theory) is that log always indicates the natural log.
I thought log without a base by default is base 10, while ln is base e
2:48 I think for cryptographers, it absolutely IS a trivial task to find prime numbers. A consequence of the prime number theorem is that randomly choosing a number less than X has approximately a 1/ln X probability of landing on a prime, which will hit a prime (on average) in polynomial time. Testing if a number is prime can also be done in polynomial time, with something like Miller-Rabin if you want speed, or something like the AKS test if you want certainty. So finding primes is actually very easy!
I just found your channel and your content is awesome! That "sin of gluttony" joke got me good. Thanks for sharing!
Thank you!
It’s a little misleading to say they get “rarer and rarer” because there are results on bounded gaps between primes, most famously Zhang’s.
Original paper put the upper bound on the gap between primes to be ~70 million. Later results dropped it to ~243.
I agree, but some details one must gloss over in the interest of time
@@agnelomascarenhas8990 Cool! What's the paper? I come from the geometry world so not as familiar with number theory.
For other people reading this, it's important to note that "bounded gap" in this context refers to having infinite primes with a gap lower than the bound. It does _not_ mean there are no, or even finitely many, primes with gaps greater than that bound.
If two primes are close, they can still be rare, surely? As in the average density tending towards zero?
4:50
your video editor, covertly speaking into a walkie talkie: he's trying to tell them what he knows...
walkie talkie: remove any trace of that footage from existence
Plot twist: the walkie talkie is a decepticon.
I think most people watching this would expect the default base of a logarithm to be not e but 10, since the common log base tends to be the base of the counting system in use (so in computer science contexts, for example, base 2 might be expected). for natural log I think most would expect it to be written as ln(x).
I thought log without a base is log base 10.
Depends, when you first learn it this is generally the case; but after high school it's more common that the assumed base is e.
@@WrathofMath No, that's ln(x). log(x) means log base 10. That's how it is on calculators including both Google calculator and my TI-84.
@@WrathofMath It seems to be field specific as to whether or not log is base 10 or base e. I prefer ln for natural log to avoid this confusion.
@@nickronca1562 That's just because a calculator needs to have both, so the notational difference of logx vs lnx is very convenient. but in many contexts the only log needed is base e log, and so log itself is allowed to stand for this.
depends on the context. For example when you analyze algorithms, the default base for log will be 2. In many cases it's logarithmic growth that is important rather than a specific base so it's important to just be mindful of what you're reading
Actually, there are just as many primes as there are in other numbers, they are just less dense.
You see there are an infinite amount of numbers and there for an infinite amount of primes, you may be inclined to believe that these are different sizes of infinity, but they are not because you can match each prime up to infinity to a normal number like so:
2,3,5,7,11,13,17
1,2,3,4,5, 6, 7
Now it is true that within a given finite range there are very few primes. Like let’s say 1-100, if you try to match up each prime to a normal number , you will run out of primes very quickly, but this is infinity we are talking about and no matter how much add to infinity it’s still the same amount, so because of that we can just continue to match up numbers without running out.
In the nineties, I worked with an HP 250 system that was designed to do medical billing. I had to frequently resize the databases and could only use primes. I never actually knew why?🤔
This Channel is going miles..... Really great and fun stuff..... I never thought math could be fun..... Just don't forget me when u become famous, man 😊😊
The theory might be correct, but in practise, I gotta' tell you that prime number density tapers off VERY slowly.
I've written a prime generator myself, aiming to eventually use the list to find large prime-less spans; and there are many centuries of numbers that contain 3-6 primes even beyond 580 billion.
So the prime # density is still more than half of what it was between, say, 100 and 200.
Subscribed for the Nintendo Land music in the background at 1:58
Fantastic tune
I'm not sure I can keep watching. e is not an ugly number.
41, 43 and 47 are
17, 19 and 53 aren't
If it isn't ugly, then why can't you keep watching?
Yeah I regretted that comment while editing; I just wanted to brush it off and move on; but I wish I hadn't insulted e; I love e. I have since apologized to e privately
@@WrathofMathdont take it back. its so overrated. its nice but it deserves to be knocked down a few pegs
@@WrathofMath Thank you. I'll watch the rest.
2:30 is this music from Nintendo Land?
You said something between the lines that many children in prime school intuitively understand. That some infinite sets of numbers on numberline could have small densities (38:00)... Is there any connection between density and something close to Cardinality - Countable, and Uncountable sets? Could we distinguish that all Countable sets have finite density when approaching infinity, but uncountable sets will have infinite density?
And there would be probably some exceptions... like Rational numbers with infinite density... and you would be able probably to try device density by something similarly to Computational complexity (if something has density limited by some formula then its "local Cardinality in infinity" would be limited to value of this formula...
that's... an interesting thought
i figured you do understand that cardinality and natural density are very different concepts, and they're merely tangent here... i dont think there's a particular relationship between them, precisely because of the counterexample you mentioned, but it's interesting to ask what "kind" of sets of R have infinite density?
30:29 what if x ≤ 1? The smallest m possible is 1,
4^(1-1)=4^0=1.
So this can't hold for x ≤ 1.
We are looking at the case x->infinity, so it’s enough to consider “large enough” values of x
There's also some nuances when x is a power of 4. For example, when x = 16, then 16
Nvm. Typed too soon
It's fascinating to me that prime numbers are both infinite (the amount of them) and infinitesimal (the amount of them compared to non-Prime numbers, though both are countable, hence the same size infinities) at the same time
The same holds for the squares, triangular numbers, powers of 2, fibonacci numbers, numbers without a digit 0 in them, etc. etc. Worlds of wonder await you. 😉
37:20 I don't think it is all that difficult using properties of inverse functions. Because the original exponential function has domain R, the range of the logarithm is R by definition of inverse functions. Because it is an inverse function, it must be a bijection from its domain to its range. Therefore it either is strictly decreasing or strictly increasing. Because the base is >1, the logarithm is strictly increasing to positive infinity in the limit.
I actually did a similar proof a while back. But, I diverged majorly in step 4.
I'm going to denote p(n) to be the number of primes less than or equal to n, as my keyboard doesn't have a pi button. (Lame, I know)
Going from p(2^n) - p(2) < 4/1 + 8/2 + 16/3 + 32/4 + 64/5 + ... + 2^n / (n-1)
I'll denote a(m) = 2^m / m-1. So, this is p(2^n) - p(2) < a(2) + a(3) + ... + a(n).
Next off, we'll note that the first two terms are both 4, and that p(2) = 1. So, p(2^n) - 1 < 4 + 4 + a(4) + a(5) + ... + a(n), or p(2^n) < 9 + a(4) + a(5) + ... + a(n).
Next, let's look at a(m+1)/a(m), with the constraint that 4 = 2/m, and 3/2 4. So a(m+1)
3:34 it's not entirely correct, you either had to exclude the numbers less or equal 1 from the possible values of x, or you had to say that m can be any integer (e.g. for x=1 if you said m=0, it would satisfy the inequality - it is the only m integer that does - but you said m has to be greater than 0, or if you take 0.15, the only m integer satisfying the statement, would be -1).
It doesn't affect the proof btw, just it bugged me a bit.
There is a paradox in the holding that there infinite numbers and infinite primes. The products of primes, and their products, crowd out at an ever increasing rate later primes. Primes are “infinite,” but 5heir products are infiniter.
They're not even different infinities. They're the same kind of infinite; you can put them into a one-to-one correspondence. They're just shy.
Hello! I am just wondering, yesterday I subscribed to your Patreon, but I can’t watch your members only videos. How do I do? Interesting video btw!
Ni Nils, thanks for your support! The two types of exclusive videos I make are the non-math exclusive videos of which I make a few each month and upload to UA-cam for members and to Patreon. There are a lot more normal math lecture videos which are uploaded to UA-cam and available only for channel members; due to Patreon's various video restrictions it's not feasible to upload all of these to Patreon, but if you send me a message on there with the group of videos you're wanting to watch, I can probably find a way to make them available to you (alternatively you could cancel Patreon and join on UA-cam where those member only videos are, but I know that's a pain).
Vsauce of modern age
I’m grateful primes get arbitrarily sparse on average or applications using factoring of numbers over, say, 10⁶ would get way more cumbersome and expensive than they are: this way one can just store factorings from the start or factorize more or less quickly using precomputed primes up to that boundary.
The sum of reciprocal of primes diverges is really counter intuitive given the rarity of prime!
Your videos are fantastic!
Thank you!
When I saw the root x at the end I thought hang on why doesn't this prove the Riemann Hypothesis...? Then I remembered about the 8. Still, I'd want some explanation why the argument cannot be refined to tighten the bound sufficiently to remove this extra factor of 8. I suppose something worth mentioning is that we cannot upper bound pi(x) by x/logx + some multiple of root x, since the RH only refers to the limit, not a stubborn inequality for all x...
the extra factors arent the issue here, the thing is that you're merely giving an upper bound... the riemann hypothesis is about the assymptotic behaviour of π(x)
I’m just in the process of rebooting my brain following a crash.
Huh. I didn't realize infinity was so little...
yup, he's just a little guy
The final prime is the end of ALL numbers
All integers are as scarce. There's literally 0% of the numbers being integers as well. Now that's how crazily large the amount of numbers are.
That depends on how you define numbers. I guess for any set of numbers, there is always a bigger set of things you can call numbers. So that property becomes fairly trivial quite quickly. Like, the reals form 0% of the complex numbers, which form 0% of the quaternions, which...
There may be very few of them, but there are enough that the sum of their inverses diverges.
10:23 IS THAT WHY IT'S CALLED A POWER SET???
Yeah
this video has a prime effect on my understanding.
very nice. very nicely explained, in deed. 👍👍
Thank you!
4:50 100 is composite???? I’m so confused
There are 25 numbers that are prime up to and including 100, AKA 100>=p where p is a prime has 25 solutions for p
X/ln(X) not log
2:16 i think you mean odd
More helpful to consider the sum of the reciprocals. Converge= few, diverge = many.
0:46 No, not Poisson, but de la Vallée Poussin.
I said Poussin, and used the pronunciation I found upon looking it up - which was similar to Poisson.
11:55 When you write just log(x) without a base it's assumed it's the log of base 10, isn't it? log base e is ln(x)
The usual convention in pure math is that "log" means natural log.
@@DarinBrownSJDCMathI’ve always heard that if u were doing natural log its ln(x). If log(x) is supposed to be the same thing, why would we even invent the term ln(x)?
@@blockyshapes7001 Notational conventions sometimes differ based on who is using the notation. This is the case for "log" without a given base. If you're reading a scientific paper, or general usage, it's (probably) base-10 common log. However, if you're reading a paper in number theory or other areas of pure math, it's going to be natural log. If you read a computer science paper, it might even mean log base-2.
Similar things happen in math all the time with notations and even definitions. Just ask a mathematician what a "ring" is, and you might get 3 different answers, depending on their research specialty.
There are very few primes. An infinite number of them, but, really, not many.
I thought e was used in ln not log
3 is our prime of primes, probably.
love 3
hiii i love your vids and they're inspiring me to make my own ❤
Thank you and that's awesome! You learn an awful lot making videos, good luck!
The true smallest prime numbered comment
I dunno if you can describe a set of numbers that is infinite as “few”.
why don't you write Log base e as ln?
You mean asymptotic, not approximate, right?
Well Optimus is the Last Prime
A very fine lark, good sir! A jolly jape!
A honky-tonk hullabaloo!
Very nice proof! Very satisfying to see how everything comes together.
I came up with my own “proof” that does something similar. It isn’t as rigorous, but I think it’s a bit more intuitive.
If you start with the first prime, 2, you know that it is impossible for any even number after 2 to be prime. Before considering any primes after 2, half of all integers after 2 are “prime candidates”, while the other half are composite.
Now, let’s look at the next prime, 3. Because 2 and 3 are coprime (they don’t share any prime factors), we know their multiples cycle independently of each other. Because of this, we know that a third of the “eliminated” integers are multiples of 3, and a third of the prime candidates are multiples of 3… which eliminates them. 1/3 of all integers after 3 are not multiples of 2 or 3, so they are our prime candidates.
This cycle continues. 5 makes it so that 1/5 of the remaining candidates are eliminated, making the new ratio 4/15. 7 eliminates 1/7 of that, making the new ratio 24/105. Every succeeding prime multiplies the fraction of future prime candidates by (p-1)/p, which, being less than 1, always makes the ratio smaller.
While, admittedly pretty shoddy as a proof, demonstrates at an intuitive level that it becomes more and more difficult to find primes the more primes have already been found.
3 is a pretty big prime
Three comments (two short, one long):
1)I think you should've mentioned that the proof you are presenting is (a version of) a proof due to Pafnuty L'vovich Chebyshev, when he famously proved the Bertrand's postulate. (I see that in the description you quote Idris D. Mercer, who unfortunately doesn't quote Chebyshev either).
2)It was perhaps worth mentioning that the estimate you obtained is up to a constant coincides with the prime number theorem, so in a sense with this elementary argument we are already only a constant away from the truth. But, if you only want to show that the density goes to zero there is a much simpler proof that I will outline in the third part.
3)We begin with a lemma: product of ((p-1)/p) over all the primes is zero. Assume for now that the lemma is true and let's estimate pi(n). Since by the lemma the product is zero, we can find finitely many primes such that the product is less than eps/2, that is (p_1-1)/p_1 *(p_2-1)/p_2*...*(p_k-1)/p_k < \eps/2. What are the primes up to n? Well, first of all we might have all the p_m for 1
I'd go for "There are Infinite primes" :)
I rapped about it once ua-cam.com/video/3er2XfJSG_k/v-deo.html
The abundance of primes declines to the limit of sequential differences, perhaps about 10^16. That low local abundance persists to infinity, compiling to reach 29.4%. See my demonstration: ua-cam.com/video/dksj4ikvgJM/v-deo.html
Prime numbers are few but they are infinite
Remember that newest biggest mersenne?
Is there an existing proof that it's prime? Or do we just forever have to trust that they got it right?
I would consult Google before commenting on a UA-cam video if you actually want an answer.
Do you mean can we check it by hand? Probably not, given its magnitude. It has more digits than there are seconds in a year. We do need to trust that the testing algorithm was correctly programmed and run.
@@dropyourself good point.
@@tomkerruish2982you don’t have to trust it. You can implement it yourself too.
Yes it's proven. We don't need to check every factor "by hand" to verify a prime number. How that's done is interesting and worth learning about.
There are the same number of primes as integers, actually
Yes, if you cheat like your mentor (not the youtuber)
Even more pedantically, the set of all prime numbers would have a cardinality less than the set of all integers because the set of all prime numbers is a subset of the set of all integers and does not contain all integers, so they cannot be the same size and thus there are less prime numbers than integers (kinda)
@@calamitalcomputers even _more_ pedantically, any infinite subset of the natural number has cardinality aleph 0, and so must have the same size. In this example, there’s a one-to-one mapping between primes and integers (or from primes to naturals, then to integers) so the two must have the same cardinality.
Nope
yet, there are as many primes as rationals
This feels incorrect
On an unrelated note: There's the same number of:
* Infinite sequences of digits 0,1
* Infinite sequences of natural numbers
* Infinite sequences of real numbers
* Continuous functions on real numbers
True if lim x->♾️ ln(x) = lim x->♾️ e^x
There are as many primes as computable numbers (which are virtually all numbers you likely ever encountered in your life).
Ah yes, every schoolchild knows that 1 + 1 = 4^1/2
Calling density zero "very few" is a bit confusing
I thought there were an infinite number of primes?
Fun fact: there is no prime even number expect 2 because they all can be divided by 2
Almost nothing on the thumbnail is a prime number
yes
False, there are infinite primes, just way less than there are non-primes, and a numbers 'prime-ness' becomes more and more difficult to prove as they get bigger.
Prime density approaches 0% as you look at bigger and bigger numbers.
There are more primes than numbers that dont contain the digit 5
There's the same number - of both there are countably many. (The two sets can be mapped one-to-one.) For a trivial subset of your set: consider the set {1, 11, 111, 1111, ...} That's obviously a countably infinite set.
@MikeRosoftJH the sum of the recyprocal of the primes diverge, while the other converges
@pietroppic That just means that the prime numbers are _more common_ than natural numbers that do not contain a 5 in decimal notation. That is _not_ the same thing as how many there are when infinities get involved.
@sillymel right, since both are subsets of the natural numbers, it could be confusing, right?
@@MikeRosoftJH I understand you learned a little about a fancy thing at some point (countability). That is not however the ONLY reasonable way to talk about "more of these than those".
Another way, more discriminating: long run PERCENTAGE of one vs the other. This way is much more illuminating in the case of primes vs other countably infinite subsets of N.
less than half of all numbers are primes!
Nice video
Thank you!
in theory could it work as a proof to just say that π'(x) approaches 0 as x approaches ∞
This is a prime numbered comment.
3 is prime, this is shorter. Lol
Since pi(x) is x/ln(x), pi(x)/x = 1/ln(x) which equals 0 as x goes to infinity.
“Since pi(x) is x/ln(x)”, no it’s not.
pi(2) = 1, but 2/ln(2)=2,885
The point of the video though is that you can prove that limit approaches zero without having first proven that pi(x) approaches x/ln(x) as x grows to infinity.
Yeah
"Very few" in infinity is still infinity.
There are only 13 primes
Multiply them all and add 1
22
-1 should be prime 😢
Smaller prime comment
Primes don’t exist ok. 0.5. Now they are gone (odds too)
There’s literally infinite prime numbers, click bait?
No, just a good title. Everybody knows there's infinitely many primes, so the title begs the question of what I could possibly mean - and there will obviously be math involved in demonstrating something about primes and their rarity.
@ I was just being sarcastic :)
Instructions unclear. Prime numbers proven not to exist. 3 is composite after all!!
the prime factors that make up this comment's number are 2 and 5
before anyone gets confused because they add to seven whitch is prime it is partitioning not factors
@@petrolheadshed mb i made a mistake i fixed the wording now
11th comment! (going off UA-cam's counter which I think counts replies)
welcome and thank you for coming
Prime number comment x3
Since I am greek, my educated guess would be that π(x) comes from the greek word "πρώτος" which means prime (when refering to numbers).
I’m the best prime comment
your 8th
Now 4th
But there's an infinite amount of them. It's like, some infinities are larger than others. Believe it or not, the only reason we know there's infinite primes, is because there's infinite numbers. That's just how infinity works.
...That's not how we know there are infinite primes. Obviously, there needs to be infinite natural numbers for there to be infinite primes, but that's not enough. For instance, the only "prime" (abusing terminology a bit here) under addition is 1.
@@sillymel That is how we know. Because there's always one more when you multiply a concurrent set of primes, and just so you know, it isn't always prime when you multiply a series of primes and add one. That is how we know. There's no trick to it, it's just that there are primes, and infinite natural numbers, so infinite primes. 1 isn't prime. 2 is.
I'm aware how the proof works, and yes, there is a trick to it. You pretty much just said what the trick is: If you take the _first_ n primes (picking the first ones is important; this won't with any arbitrary string of consecutive primes) and add 1, the result is always another prime. That doesn't work with any old subset of the natural numbers.
As for the other thing, I'm aware that 1 isn't normally prime. That's why I put "prime" in quotes. To be more specific about what I meant:
1. In this case the natural numbers must include 0, the additive identity.
2. A natural number is a prime-analogue with respect to addition if it can be expressed as the sum of natural numbers in exactly two ways.
Turns out I over-simplified things because I didn't want to explain proof by contradiction here. Ignore that part about 1 plus the product of the first n prime numbers being prime as well.
I'm not quite sure I understood what you were getting at in the first half of your. Numbers can't be concurrent. Did you mean consecutive?
I really hope there's more to your argument than "Primes exist. There are infinite numbers. Therefore there are infinite primes.
@sillymel if you multiply the 1st n primes and add one, it doesn't always leave a prime. Sometimes, it leaves a composite number, which has a prime factor that is larger than the largest prime in the original calculation.
I was thinking why there's only 7 comments untill I saw this video was posted 58 minutes ago...
Because this video is prime content
hope a 40 minute proof video isn't too intense for people!
90th comment!!
This is stupid..., coz obviously absolutely there are infinitely many primes out there (!!). 😂😂😂