Archive for the ‘pnt’ Category

The Prime Number Theorem

July 9, 2011

So one of the few math books I’m still fairly interested in poking at sooner rather than later, since graduating and moving on to a computer programming job, is “The Prime Number Theorem”,  by Jameson. It claims to be accessible at the undergraduate level, so I’m sort of optimistic I can follow it. When I’m feeling ambitious, I figure I’ll read the book and do the exercises, and even write posts about what I learn as I go. And cook more. And eat healthier. And…

Right, so I started reading, and got to the first set of exercises. I know I’ve done the second and third before. The second (show there are arbitrarily large gaps between primes) I actually remember doing from my freshman year as an undergraduate, so didn’t put much into it. The third (show p_n\leq 2^{2^{n-1}} and that this implies \pi(x)\geq (\log\log x)/(\log 2)) I remembered doing while I was reading Hardy & Wright more recently, and decided to see if I could get the inequalities right again. It took a few minutes, but I think I got there.

The first exercise, though, took me an embarrassing amount of time. Good start, huh? The problem reads:

Let ≥ 1 and let = {30n+r : 0 ≤ r ≤ 29}. For which values of r is 30n+r not a multiple of 2, 3, or 5? By considering the possible positions of multiples of 7, show that E contains at most seven primes (seven cases, no short cuts!)

Ok, so the first part of that question I got without much difficulty (actually, I got wrong without much difficulty). It’s just all the other primes bigger than 5 but less than 30: 7, 11, 13, 17, 19, 23, 29 (see my error yet?). The second part got me though (since I got the first part wrong). There’s only 7 numbers in that list I just picked out, so what more is there to show? Any 30n+r that’s prime must have an r from that list, because everybody else is divisible by 2, 3, or 5, right?

Nope. Stupid 1. The case r=1 isn’t accounted for. So that means that primes could actually show up in any of 8 spots. So that’s where the hint about multiples of 7 comes in. The first multiple of 7 in the 30 consecutive integers comprising E corresponds to r = 0, 1, …, 6, and then for any of those choices, you can easily write down what the other multiples of 7 are. For example, if the first multiple of 7 in E is with r = 3, then the other multiples are at 10, 17, and 24. Notice that, in this case, the prime 17 would have to get taken out of the 8 possible spots for primes (since it is now known to be a multiple of 7), and we’d be down to 7 primes. The same thing happens in the other 6 cases about the multiples of 7, and we obtain the result.

So that slightly rocky start, those 5 pages of reading and 3 exercises, took just under a week, start to finish (not that I was actively working on it that every day). And, in all honestly, I only sorted out that first one when I sat down to start writing, here, that I couldn’t figure it out. But whatever. There’s my first post since graduation. Perhaps I’ll keep learning some math after all (in addition to the math/stats sorts of things I’m learning for work). Here’s to fewer errors in section 2!