Few areas of mathematics resonate with so many as those focused on prime numbers which appropriately have a giant role in number theory. And counting prime number offers a way to be introduced into number theory in a big way with surprisingly simple mathematics. Celebrating simple mathematics is something I deeply enjoy, and talking about it, is a pleasure.
So I'm going to talk about how you can maybe have a feel of discovery yourself, using some really simple mathematical ideas for the basic concepts where you just need to know what a prime number is, and simple division with throwing away the remainder. There will be a bit of calculus though thrown in for completeness near the end but don't worry if you don't know calculus as you don't have to understand it! It's just for those folks who find that interesting.
Now let's do some simple math. And start with considering some simple ideas.
For example 3 divides fully into 10 only 3 times. For number theory integers are important, so we don't care about the remainder. And 3 is a prime number. The numbers with 3 as a factor including 3 itself less than 10 are: 3, 6, 9
We'll use [10/3] = 3, in order to show we don't care about the remainder, where the [] is something called the floor function, which can also be shown as floor(), so floor(10/3) =3 as it's just another way of showing the same thing.
So we have counted 3, 6 and 9, with [10/3]. Similarly 2 is prime, and the numbers with 2 as a factor up to 10, are 5, where we have that exactly: 2, 4, 6, 8, 10
Now these things were noticed a long time ago, and people figured out how to use this approach to count the prime numbers, like we're in the process of doing up to 10, where it matters that you know the numbers that are prime up to the square root of 10. And don't panic with mention of the square root! Again the focus is on integers, so we actually want the biggest integer whose square is less than 10, which is, yup, 3 again.
With 2 and other numbers with it as a factor, called composite, we have a list of even numbers, and with 3 and its composites we have a list of numbers that have 3 as a factor, and have included ALL non-negative integers up to 10, with those lists except, 0, 1, 5 and 7.
In number theory 0, is not considered a positive integer, and doesn't really matter for counting so we will not mention it again. While 1 is not considered prime.
So we've discovered 5 and 7 are prime with this approach.
And if counting, would note the two primes less than square root of 10, as 2 and 3, and the found primes...wait, so how do we count?
Well if we count for the even composites, we know it's [10/2] - 1 = 4, because 2 is prime, and for composites divisible by 3, we have [10/3] - 1 = 2. But there's a problem!
That problem is that 6 is even AND it is divisible by 3, so we counted it twice!
And one approach is to now subtract for that overcount by counting it, which we can do with [10/6] = 1, which is the hard way.
When I considered this problem over a decade ago, I looked at 3, 6, 9 and thought it silly to count 6 again since I had it counted with 2, 4, 6, 8, 10, and I was right! It IS silly, or maybe I should more politely say, naive. However, hundreds of years ago that's how mathematicians did it, which leads to something kind of convoluted.
My approach was to ignore at each prime the counts already made at a lesser prime.
If you wish to play with that concept and figure out a prime counting function from here, go ahead, and I'll continue with it, conceptually before showing the mathematics that follows.
So now we have [10/2] - 1 = 4 composites, and [10/3] - 1 - 1 = 1 composite, for a total of 5 composites, which is correct! That second 1 was subtracted to handle 6, which may seem like cheating at this point as I know to subtract it, but don't worry, you'll see some math in a bit, which shows how it's done.
If you can figure out how to go from here to a complete mathematical function, then you can get a feel for discovery. Remember the idea here is simple: how can I best prevent overcounting by correcting for counts of composites already counted?
The 5 composites up to and including 10 are: 4, 6, 8, 9, 10
So yes! We DID count them, so what's the count of primes?
The prime count is: 10 - 5 - 1 = 4.
Those primes of course are: 2, 3, 5, 7
So we subtract the 5 composites, and then have to subtract 1, for yup, 1, which is not considered prime, and we have the full prime count.
That concludes our first prime count! Easy, right?
One thing I want to talk more about is why we need to know primes up to the square root of 10.
Why? Well we're pairing primes up with other numbers with composites, and if you get to products of bigger primes, like 5*5 = 25, you are beyond 10. For every composite less than or equal to 10, you will have a prime factor less than the square root of 10, as it takes two to make a composite. That means we can focus on those primes, which are 2 and 3.
The same principle would apply for bigger numbers, like for 100, we need 2, 3, 5 and 7.
When you get to 11, 11*11 = 121, but for anything smaller, one of those primes will have to show up. For instance, 7*11 = 77, gets counted when considering composites with 7 as a factor.
Most of the concepts presented here were quite revolutionary--hundreds of years ago! Where I snuck in something innovative. If you caught it, good for you! It was a new way of looking at things introduced by me in the summer of 2002.
Did you notice it?
If you missed it, see if it jumps out at you in one of the equations I use. If you figured it out on your own before getting here, good for you! If you didn't don't feel bad.
The main workhorse is something I call the dS function, which corrects the count at each prime without overcounting. THAT was my innovation! Just seemed like a smart thing to do.
The corrected count, which I call dS(x,pj) at each composite, where p is prime, where j tells you which one, like j =1 for 2, as it's the first prime, and j = 2, for 3, and so forth is:
dS(x,pj) = [x/pj] - 1 - (j-1) - S(x/pj, pj - 1)
where S(x/pj, pj-1) is the count of composites that multiply times pj to give a product less than or equal to x, where notice that pj must be less than or equal to sqrt(x) or the composite count given by [x/pj] - 1 will not be correct.
That embodies everything we've been doing up to this point. If you figured it out, good for you! If you can read it given our discussion that's great as well.
Now I'll go back through what we did with 10, so you can see it in action.
So for dS(10,2) = [10/2] - 1 - (1-1) - S(10/2, 2-1) = 5 - 1 - S(5,1) = 4
Here S(5,1) = 0, as there are no composites less then 5 that multiply times a prime, as 4 is the only composite less than 5, and it's a product of primes.
Which is what we go before. So it's just saying there are 4 even composites, just like we found out before. That takes no effort for the thing.
I get a little fancy in not showing the floor in the S function, so next is.
dS(10,3) = [10/3] - 1 - (2-1) - S(10/3, 3-1) = 3 - 1 - 1 - S(10/3, 2) = 1
And there's even less room beneath 10/3, as there are no composites beneath it, only 2 and 3 which are both prime.
Here it actually did some work! It correctly threw out another 1 as it corrected for 6.
To see that other piece with the S function pull out other overcounts you have to use bigger numbers. For example S(16/3,2) = S(5,2) = 1, because 2(2)(3) is the only composite case where 3 is multiplied times a composite up to 16.
I don't typically write the floor() inside the S function as I consider it redundant.
If you've followed this far, and maybe wonder what is the point of all of the above, or maybe even still wonder how I got it, never fear! I've discussed these things for over a decade and am concentrating things into a single post for reference. To see it all explained in detail, one of my better posts I think is:
somemath.blogspot.com/2012/10/composite-counting-functions-and-prime.html
This approach also leads to a nonlinear partial differential equation:
P'y(x,y) = -(P(x/y,y) - P(y, sqrt(y))) P'(y, sqrt(y))
Here's my most recent post which links to a post which steps through the derivation:
somemath.blogspot.com/2012/11/differential-equation-and-prime-counting.html
To me the research here is most dramatic in showing the simplest, fast prime counter humanly available.
Where pj is the jth prime:
P(x,n) = x - 1 - sum for j=1 to n of {P([x/pj],j-1) - (j-1)}
That summation will count primes if you make sure n equals the count of primes up to sqrt(x), but no higher. And an example of what it gives is P(100,4) = 25.
The summation is built around what I call the dS function, and you can see pieces of it in there, but with it close to full mathematization it's just a lot more compact.
You can actually go even further and have it find primes on its own, where it promptly looks a lot messier:
To see a recent step through of a demonstration I think the following is a good post which is on one of my other blogs:
beyondmund.blogspot.com/2013/05/simple-and-fast-prime-counter.html
That is the fastest prime counter available for its size as it completely encapsulates the ideas introduced here, and it turns out that shrinks things down considerable as to presentation.
It's NOT the fastest prime counting algorithm available though. It IS the fastest for its size, with the smallest presentation you will see for a fast prime counter. It is easy to explain, present, and implement, so I think it's a great introduction to the subject.
But here is the full prime counting function fully mathematized where it figures out which numbers are prime below square root of x on its own. Figured I should include it, though it's not nearly as pretty as when you hand it those primes, and it's not as fast:
P(x,y) = [x] - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}
where if y is greater than sqrt(x), then P(x,y) = P(x,sqrt(x)).
It's actually a little prettier with the summation sign and square root symbol though it's still all integers. But Blogger doesn't make that easy for me to do, so I've just used the format above.
There's nothing else like it in number theory. It actually involves something called a difference equation. If that means nothing to you, don't worry! Just covering all the bases and this thing links to some of the most complicated mathematics human beings have ever discovered. It is one of my greatest discoveries.
Whew! What a journey. That was SO much fun too. From simple to advanced, we journeyed from very easy concepts to mathematics touching on the limits of human knowledge.
And I've stepped through the concepts it uses in this post! If you can understand what I said previously about counting composites at each prime without counting ones previously counted then you have the principles in place! And maybe can kind of see things within it that echo back to what was above.
If you've skimmed through this post to the end, maybe you can challenge yourself by trying to derive the prime counter JUST using the principles explained. And if you get stuck you can check out the various links to find more detail on how it is done.
James Harris
No comments:
Post a Comment