Monday, October 27, 2014

Easiest Way To Prove Primes Are Infinite

This may be more of an implication than a proof, but I think it's worth sharing because it's so easy to do and may provide a potentially useful algorithm.  Certainly much easier than understanding the traditional proof of the infinitude of the primes in my opinion.

I call it counting by primes.  Was I the first to invent it?  Who knows.

Start with 2 and 3.  Call 2 by the name P1 and 3 by the name P2.

Multiply P1 and P2 in all possible combinations including repetition up to powers of 2.  So you have everything from P1^0 times P2^0 all the way up to P1^2 times P2^2.

So in this case you'd have a combination of numbers like 1 x 2 = 2, 2 x 2 = 4, 3 x 2 = 6, etc.

Look at all the primes you have and all the composites you've generated with those primes.  Generate an entire list, eliminating duplicates.  When you've generated a list, you may see several gaps in between the numbers.  Find the gap in between the lowest values.  In this case, it should be the gap between 4 and 6.  What's the value of the lowest missing number in this gap?  It's 5.  Call 5 by the name P3.

Multiply P1, P2, and P3 in all possible combinations including repetition up to powers of 3.

Look at all the primes you have and all the composites you've generated with those primes (not just in this most recent step, but in all steps of the algorithm thus far).  Generate an entire list, eliminating duplicates.  When you've generated a list, you may see several gaps in between the numbers.  Find the gap in between the lowest values.  In this case, it should be the gap between 6 and 8.  What's the value of the lowest missing number in this gap?  It's 7.  Call 7 by the name P4.

Multiply P1, P2, P3 and P4 in all possible combinations including repetition up to powers of 4.

Wash, rinse, repeat, as I've heard the gamer Aqualung say.  You'll find out that there's nothing to keep you from doing this forever, since even if there was no gap in the list, you could just pick the lowest number you haven't used yet as PN.

If there are typos here, or I messed something up, feel free to criticize.  But I think you can get the general idea and that's what is important.  Perhaps there's a flaw in the idea, but I don't see it.  I'm definitely not the best mathematician.  I remind myself of Winnie-the-Pooh.  A bear of very little brain, but darnit, he likes to try and think.  By the way, did you know Winnie-the-Pooh was created by a guy with a degree in mathematics?