Like most people, I often dream of prime numbers. Actually, no, I'm not that geeky. However, I have been reading and viewing lots of stuff related to calculus lately. I do this from time to time. I get back into the most challenging mathematics I have ever tried to see if I can understand again some of the stuff I supposedly once learned, plus make some new personal advances. (Despite my love of mathematics, I'm honestly not that good at it.)
Anyhow, a couple of weeks ago, on a Saturday morning, I somehow got to thinking about prime numbers and how easy it would be to write a little computer program to identify a list of prime numbers. After all, all one would have to do is start with the number 2, then begin listing all of the natural (i.e. plain 'ol counting) numbers one by one, dividing each of them into the given number and see if there is any remainder. If any of the numbers divide into it evenly (without any remainder), then voila, it's a prime number! I'll just let the computer do all of the nasty, tedious, number crunching. I wondered just how big a prime number I could find (or in my personal case, "discover"). In doing a quick Internet search, it was cool to find that there is a name for this time-honored approach to divining prime numbers, the trial division approach (though it fell out of favor centuries ago - hey, better late than never). I also was quite thrilled to learn a neat trick to greatly reducing the numbers needed to run the program in order to determine if a number if prime or composite -- stop when you get to the number that is or larger than the square root of the number in question. Of course, this makes total sense if you think about it. There can obviously be no factors to consider that are greater than the square root of the number because you would have found already the other factor that multiplies with it to obtain the number. So, for a number like 100, the largest number you would have to check is 10. For a much bigger number, say one million, 1000 is the largest number that needs to be checked as a factor. No need to try out the remaining 999,000 numbers!
So, I quickly wrote such a program and the fruits of my labor are contained in this blog posting. As promised, I also integrated the graphing techniques I've been describing in recent posts by including the option of drawing a running graph of the total number of prime and composite numbers found. I'm not going to provide the level of explanation to my code as I have previously, but I'm very happy to answer questions about it if you look at the code and can't figure it out.
Here is a snapshot of the program:
How It Works
First, you enter a number as the upper limit of the range that will be searched for prime numbers. Then, you click the "Start Search" button to have the program begin its number crunching to search for prime numbers beginning with 2 and ending with the number you entered. You can also choose to graph totals of prime and composite numbers found so far, though the program runs a lot more slowly if you choose this option.
In the "Status Window" you will see the current number being analyzed with the factors being considered on the next line. Of course, the numbers are buzzing by very fast at the beginning, though things do slow down after awhile.
As prime numbers are found, they are listed in the first column. That column is actually the heart of the program, because all factors of other numbers can be reduced to two or more prime numbers. So, when a number is being analyzed (let's call it the target), each of the prime numbers found so far are divided into the target. If there is no remainder, then it is not a prime number and it is added to the middle column as a composite number, and the next natural number becomes the target.
As the program runs, you are given a running total of prime and composite numbers found so far.
The script that makes all this work can be found in the "Start Search" button. Basically, there are two Repeat loops, one nested in the other.
The first Repeat loop increments the variable "varNumber" which serves as the target number. Within that is another Repeat loop that is dividing all of the prime numbers found so far into it. Let's dissect this second Repeat loop. Here's the code:
put true into varPrimeFlag
put the number of lines in field "prime numbers" into varL
repeat with i = 1 to varL-1
put line i of field "prime numbers" into line 3 of field "feedback"
put varNumber/(line i of field "prime numbers") into varAnswer
put varNumber&", "&(line i of field "prime numbers")&", "&varAnswer&", r="&varAnswer-
round(varAnswer) into line (number of lines in field "answer")+1 of field "answer"
if varAnswer-round(varAnswer) = 0 then
put varNumber&", "&(line i of field "prime numbers") into line (number of lines in field
"composite numbers")+1 of field "composite numbers"
put false into varPrimeFlag
exit repeat
else
end if
if line i of field "prime numbers" > sqrt(varNumber) then exit repeat
end repeat
wait 1 tick
if varPrimeFlag is true then
put varNumber into line (number of lines in field "prime numbers")+1 of field "prime numbers"
end if
I really like the scripting technique of using LiveCode's list processing capabilities in tandem with text fields. It's a snap to continually add to any text field just by a script that counts up how many lines are being used, then saying to put the next data item to the +1 line. Similarly, it's a snap to take and use each line of data just by building a repeat loop that starts at line 1 and repeats for the number of lines in the field.
I use the variable "varPrimeFlag" to flag whether or not the target number is prime. As you can see, before the loop begins, I assume the number will be prime by setting it to true; if the loop finds it to be a composite number, I set varPrimeFlag to false. So, if nothing triggers this, the repeat ends with varPrimeFlag being true, and the number is added to the list of primes.
Lines 5 and 8 are key to determining if a number is composite:
put varNumber/(line i of field "prime numbers") into varAnswer
...
if varAnswer-round(varAnswer) = 0 then
Line 5 divides the target number by each and every prime number found so far. Line 8 takes the answer and subtracts from it the answer rounded off to the nearest whole number. If the answer is 0 this means that there was no remainder to the original division problem. Any number that divides into a second number, with no remainder, is a factor of the second number.
This line checks to see if the next prime number to be used to check out the target is larger than the square of the target number:
if line i of field "prime numbers" > sqrt(varNumber) then exit repeat
If it is, the repeat loop ends.
Also, you will find a procedure within the script for this button titled "graphPrime" that handles the graphing tasks.
Lloyd's Findings
Next, here are some of my "findings."
First, I programmed the time it took the program to compute all of the primes up to a given range. I think this is an interesting data point in and of itself. Here are three examples:
- Analyzing 1000 numbers takes 1:01 minutes
- Analyzing 2000 numbers takes 3:01 minutes
- Analyzing 5000 numbers takes 16:56 minutes
Next, here are two other interesting facts:
- 4999 is the largest prime number I've found so far.
- In the set of numbers 2-5000, there are 669 prime numbers (and 4330 composite numbers)
Next, I became interested in the factors of composite numbers. The program is not looking for all the factors, but merely asking the question of whether the number being analyzed is a prime or composite number. So, as soon as a factor is found, the number is deemed composite and the program moves on to the next number. So, obviously, every even number is quickly determined not to be a prime number because the factor 2 reveals this fact. So, I thought it be at least interesting to include in the output the first (i.e. smallest) factor found. So, the number 2 is obviously common with it being the first factor of half of the numbers. But, I was intrigued to find what would be the largest first factor.
My program revealed that in the data set 2-5000, 67 is largest first factor, and it is found in the following composite numbers: 4489, 4757, 4891.
I found this answer by copying and pasting all of the data in column two into Excel. I decided it would be good to partner LiveCode with Excel for this project. After all, why take the time to program functionality into my computer program when it already exists in Excel. There is a wonderful option in Excel called "Text to Columns..." under the "Data" file menu choice that lets you parse a list of numbers in each cell of a column into separate columns. So, the number pairs...
4,2
6,2
8,2
...can easily be parsed into two separate columns in excel using the comma as the delimiter.
Next, I found the results of the graph quite amazing. For example, consider your own hypotheses about the distribution of prime and composite numbers. Are they evenly spread out or they do they appear randomly, or in clusters? Do they occur is equal numbers, or in some proportion. Are the patterns consistent, or do the patterns stop and start up again? To be honest, I didn't know what to expect and I forced myself not to do any google searches because I wanted to make the discovery myself!
The running graph shows that the rate of which composite and prime numbers are distributed looks to be a linear function for each. The fact that the slopes are so straight and smooth is fascinating. I wasn't sure if I would find some "jaggy" lines showing gaps in the number of primes. However, there does seem to be a slight bend in the prime number graph, where the rate seems to be falling off slightly. So, I programmed the file to keep track of the ratio of the totals of prime and composite number found at any given point, and these are found in the third data column (each line contains a pair of numbers: the ratio and the point in the list). When I copy and paste these into Excel and plot them in a graph, here is what you find:
This graph clearly shows that the ratio gets smaller and smaller, meaning that as the more numbers you analyze, the fewer prime numbers there are, relative to the total. It seems to resemble an exponential-logarithmic distribution. (Rather impressive of me to notice this, don't you think?) Actually, in doing some research (aka I looked it up on Google), the distribution of prime numbers is known as the Prime Number Theorem. According to the Wikipedia entry, "Informally speaking, the prime number theorem states that if a random integer is selected in the range of zero to some large integer N, the probability that the selected integer is prime is about 1 / ln(N), where ln(N) is the natural logarithm of N." I guess that's about as informally as most mathematicians speak.
This also means that it is an asymptotic distribution, which is actually something I do understand. An asymptote is a number representing a limit. So, the ratio of prime to composite numbers will approach, but never reach, this number. (Interestingly, I did a google search for this number, but did not find it. Hmm, this makes me "curiouser."
After analyzing 5000 numbers, the ratio is .15, in other words, there are about 6.7 times as many composite numbers as prime numbers between the range of 2-5000, the number continues to decline. Amazing!
My little program, of course, is not of interest to a mathematician as it reveals nothing not previously know. Indeed, although the largest prime I have found is 4999, a number with 4 digits, the largest prime number yet discovered has 17,425,170 digits! (Read this article to learn about the largest prime number yet found.) However, contributing to the mathematics literature was not the point of this exercise. In was intended to be my own wonderful journey of personal discovery. But, you never know from where the next major mathematical discover will arise. I just read an article on Slate.com titled "The Beauty of Bounded Gaps" of an "ordinary" mathematician -- Yitang “Tom” Zhang, a math professor at the University of New Hampshire -- making a monumental discovery about prime numbers.
Here's a quote from the Slate article I found interesting:
"The primes are the atoms of number theory, the basic indivisible entities of which all numbers are made."
Boy, this really makes me feel that my humble investigation into prime numbers is important stuff. But, I had a truly emotional reaction to next quote from the article:
"This means, in particular, that prime numbers get less and less common as the numbers get bigger, though the decrease is very slow; a random number with 20 digits is half as likely to be prime as a random number with 10 digits."
I got emotional because I feel like I'm the one who discovered this! That's what math and science projects do to people.
There are so many other questions that I want to explore if I had time. The Slate.com article actually gives me some ideas for how to look for gaps in prime numbers. An obvious next question -- obvious just by thinking about it, and especially by watching the program run -- is that it takes more and more time to analyze a number as the number increases. But, does the time increase in a linear or exponential fashion? Perhaps I'll analyze these data and report on what I find in a future blog posting.
Perhaps you have a question you'd like me to consider exploring. If so, send it on! Better yet, use my program to explore your own prime number questions. And better still, build your own program to explore your questions, feeling free to use any of my code as a starting point.
So, those of you who teach mathematics, especially with middle and high school students, please consider integrating LiveCode into your teaching and challenge your students to think like a mathematician to discover mathematical principles and ideas on their own. Who cares if the answers are already found in some book or some Google search. A personal discovery based on questions you find meaningful makes it a real discovery.
No comments:
Post a Comment