Today I finally received my books from Amazon.com. I had purchased George Polya's Induction and Analogy in Mathematics Volume I and Volume II; along with Knuth's book, Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition). I had been meaning to buy these books for some time now.
I first heard about Polya from my math teacher in advanced linear algebra class. I had asked him about developing mathematical concepts and he recommended me Polya's books for reference. I must say for a man who read these books at his own leisure, he had excellent taste in mathematical literature.
Polya talks about developing the notion of "guess work" in his book, he encourages you to try out your ideas to see if you have the right notion. The first question he asks you to try is find a pattern to a sequence of numbers.
At first glance I immediately started to take the difference between each number, first there is a difference of 20, then 10, then 20, then 10, then 30, and finally 30 again. I could not make out any discernible pattern, at least not right away. I had to take a step back and think about the first element in the sequence, 11. So I got my white boards together and started writing.
I thought maybe there was a formula for the way each element in the sequence came about, so I started to play with the indices of each element. Like everything,
increases by 1 for the use of this algorithm. I could not reproduce any of the numbers with out writing a formula for each element individually. Nothing came to mind with this technique. So then I took the first element, 11, and started to remember its properties.
11 is a prime number, so then I looked at the second element. 31 is also prime, so is 41, 61, 71, 101, and 131. All numbers are prime in this list and they all have one thing in common, besides being prime. They all end in 1, so the next element would be 151 and so forth.
I checked my work against the author's answer and online, it turns out that I am right. If you have experience with prime numbers this problem is a little less complicated and easier to figure out. The major clue is the first element, if don't know primes you may spend a lot of time on the differences of each element. Its a good first practice problem.
If this sort of problem interest you then I recommend you pick a copy of George Polya's Induction and Analogy in Mathematics volume 1, just as my teacher had recommended to me.
Now my friend recommend we add on to what we can do with this current knowledge, so I looked up how we can code a program that will check if a number is prime and also check if its last digit is 1. The second component is easy for me to program, so I don't need to find anything online for that. I am no expert programmer, so any solution I come with will most likely not be the most efficient. It rarely occurs that I write the shortest most efficient code, I usually write the code to be "readable". I like to make my code self-documented as possible, so when you read the code it does not look like hieroglyphics.
The language I love to use the most is python because that is what my computer science teacher used to teach me the fundamentals of programming. I also like python because it is easy to use for a mathematician like me. There are plenty knowledgable programmers online that can answer questions should you need help, or just borrow the code like we are about to do.
So, as I searched online I came across this one person's website that had exactly what I am looking for. If you look here there is a nice program that tells us if a number is prime, which is the first key in our quest for prime domination. For you "must be a better way" type, there is also this post on using numpy which can calculate a prime faster. How much faster is debatable, and not for what we are looking for. The author posts a two different methods, which we will go over.
The first task we have to conquer is determining if a number is prime. The author of the post explores more than one way to check if a number is prime, so will discuss these methods. Although this gets into computer science, it still deals with a lot mathematics.
Method 1: The Divisor Test
So the author starts off by testing a number for being a potential prime by doing the most basic test. Take any given n, we than proceed to divide every number less than n into n itself. So if we take small prime number, say
We would than take our 5 and divide by 4, 3, and 2. Can't divide by 1 because 1 is part of the definition of prime. By modular division, none of these numbers produce a remainder of 0. So we can conclude 5 is indeed prime:
The basic code looks like this:
The author goes through some techniques of how the code could be written more efficiently. Because this is not our concern, I will just show you the final product. Just incase you did not read the entire post, he turns the algorithm into a function. This way he can call upon the function in another piece of code as needed.
The next method the blog shows us is prime sieve. This is one of the earliest methods of finding primes that is thought in school. If we take a range of numbers say 1-100 and than we start taking out multiples of each prime we come across. By the end we should have crossed off all composite numbers.
Method 2: Prime Sieve
The final code that the author gives looks like this:
He even gives a funny picture that plots the first 1000 primes, each prime is represented as a vertical black line. Looking at the picture you might have guessed it to be a bar code of some sort.
- "NumPy¶." NumPy. N.p., n.d. Web. 14 Nov. 2012. <http://www.numpy.org/>.
- "How to Find Prime Numbers with Python." Pythonism. N.p., n.d. Web. 14 Nov. 2012. <http://pythonism.wordpress.com/2008/05/04/looking-at-prime-numbers-in-python/>.
- Polya, George. Mathematics and Plausible Reasoning Volume 1: Induction and Analogy in Mathematics. Vol. 1. Princeton, New Jersey: Princeton University Press, 1954. 1-8. 2 vols. Print.