Lloyd's (Hypothetical) Math Fair Contest Entry

You can tell from the title that I didn't actually submit this idea to any math fair. But, I think imagining a math and science fair is the right mindset for this blog posting. I really like the idea of giving the power of computer programming to students to explore topics that would be most suitable as entries into a math and science fair. Remember that there is a free edition of LiveCode available, so I hope many teachers will choose to begin offering this powerful computer programming environment to their students. Consider this blog posting as an example of what a student might do with such a powerful analytic and computational tool.

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.

LiveCode File | Macintosh Stand-alone | Windows Stand-alone

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 

So, if I were to devise alternate ways of crunching the numbers, I could use these data to compare the efficiency of the strategies. But, that wasn't a question I was interested in at the moment.

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)

Don't worry, at some point I'll run the program for much longer periods of time. I'm curious as to how long it could run before crashing -- I don't know of any limit to the number of lines in a text field, but I'm sure at some point I'll exceed some memory cache. (It will be rather cool to keep posted somewhere the "largest prime I found so far.")

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.

Graphing with LiveCode, Part 1: Learning How to Draw Lines with Scripts

In my previous post, I casually mentioned that it would be cool to graph the changing rate at which unique random codes were being generated. Graphing is a powerful visual tool. But how would one actually do this in LiveCode?

First, unfortunately, there is no graphing tool or widget in LiveCode (at least not that I'm aware of). But, LiveCode has many graphical drawing tools. In fact, it has the two most common graphical types: bitmap (i.e. paint) and vector (i.e. drawing).  I'm assuming you know the difference between the two. If not, you might want to do a quick google search at this point to learn the difference. In short, bitmap graphics are merely the turning on or off of pixels on the screen, whereas vector-based graphics are "defined" as objects. For example, if you've ever used a graphics package where you create rectangles and ovals and then could stretch any of these by clicking and holding on one of the the object's handles, or if you could click on the object and continually choose different line widths, line colors, fill colors, etc. after first drawing the object, then you are using a vector-based tool. It's as though the object is defined as having so many sides or lines, with each line being straight or curved, and being such and such color and thickness, etc. In contrast, bitmap graphics are drawn on the screen with attributes that cannot be changed or manipulated, other than by doing things such as taking an "eraser" tool and slowly erasing the object, or selecting an area of the screen and choosing to cut it.

So, it's great that LiveCode has both. In the tools palette, the bitmap graphic tools are in the bottommost section (e.g. spray can, eraser, pencil, etc.) and the vector graphics tools are just above those (e.g. rectangle tool, oval tool, line tool, etc.):

If you are still fuzzy on the whole bitmap vs. vector graphics thing, I suggest you take 5 minutes to play with these tools now. Just open a new card and start drawing a bunch of graphics. You'll quickly deduce the difference between these two graphics families.

In this blog entry, I'm just going to show how to draw a simple line with the brush bitmap tool. We won't actually do any graphing in the mathematical sense until part 2. But, you have to first understand how to use these tools first in simple scripts. So, this post will be rather boring in that we won't try to do any mathematical graphing (something I'll define better next time). Let's just take a few minutes to learn how to use scripting techniques to draw lines on the screen.

Cartesian Coordinate System - LiveCode Style

OK, let's get into it. Consider the following code of a button titled "Draw Lines":

 on mouseUp
   choose brush tool
   set the brush to 32
   set the brushColor to brown
   set the dragSpeed to 0
   drag from 25,200 to 50,150
   drag from 50,150 to 75,175
   drag from 75,175 to 100,140
   choose browse tool
end mouseUp

This script is yet another example of the natural language-feel of LiveCode. Line 2 says to choose the brush tool from the various bitmap graphic tools.

Line three selects the brush shape that will be used.  There are 35 built-in shapes. According to the LiveCode dictionary: "A brushID is a built-in brush number between 1 and 35. (These brushes correspond to LiveCode's built-in patterns 101 to 135.) By default, the brush is set to 8 (a round brush)."

32 is a thin, square brush shape, and a good one for plotting line graphs. 28 is probably the thinnest brush to choose. Brushes 5-8 give different round sizes, whereas brushes 1-4 give similar sizes, but in a square shape.

Line four chooses the color that the brush will paint with -- you can also use an RGB triplet here instead (e.g. 127,127,255).

Line five sets the speed at which the brush will draw, with 0 being as fast as possible (0 is best thought of as instantaneous).

Lines 6-8 draw three lines and we need to understand them perfectly before going on. First, you need to understand the grid system of the LiveCode stack window. Each pixel in the window can be identified with a pair of numbers. The first indicates how far from the left edge to go and the second number indicates how far from the top edge to go. So, with the pair 25, 200, you start from the top left corner and go to the right 25 pixels, then down 200 pixels.

At this point I'm hoping you are having a flashback to your high school algebra days to remember something called the Cartesian Coordinate system (named after the famous mathematician and philosopher, René Descartes). This is simply the same sort of grid consisting of two lines -- the x-axis (horizontal) and the y-axis (vertical) -- crossing each other at right angles, usually drawn to resemble a big plus sign, with the origin -- 0,0 -- at the center. (These crisscrossing lines are just that "lines," in the formal mathematical sense, meaning that they extend infinitely in all four directions, symbolized by small arrow heads.) The LiveCode grid system is similar except that 0,0 is in the top-left corner of the screen meaning that as the vertical number (second of the pair) gets bigger, the further down you go. In contrast, as y gets bigger using the classic Cartesian grid, you go up. This little difference will become more important in my next blog entry.

So, line 6 tells the computer to go to point 25, 200 (i.e. starting at the top left corner, go over 25 and down 200), then drag the brush to point 50,150, leaving a line segment between the two points.

Line 7 starts at 50,150, then drags another line to point 75,175. Finally, line 8 starts at 75, 175 and drags a final line to point 100,140. So, all we are doing is connecting the dots. Here is what the 3 line segments look like in a stack of size 500 by 500:

Not too exciting, I realize. But, you should play with this code, drawing different lines all connected to each other just by changing the coordinates (the pair of numbers for each starting or ending point) of the drag command. To have one long jagged line created, just be sure that the starting point of the next line segment is exactly the same as the ending point of the previous line segment.

Now notice line 9 -- "choose browse tool" -- this is the tool represented by the left arrow in the top left corner of the tool palette. If you leave off this command, the brush tool remains chosen and you will have to manually choose the browse tool.

OK, I Drew Some Graphics, So How Do I Erase Them?

Now, notice the Erase button. That button does just what it says -- it will erase all bitmapped graphics drawn on the card. Here's the code for this button:

on mouseUp
   choose select tool
   drag from 0,0 to 500,500
   cut
   choose browse tool
end mouseUp

The select tool is the first bitmap tool in the tool palette represented by the dotted rectangle. By dragging from 0,0 to 500,500 with the select tool, you have actually chosen the entire stack window. The command "cut" does just that -- it cuts, or removes, whatever bitmapped graphics are in this area.

OK, that's enough for now. Take some time to play with these commands, perhaps being bold and playing with other bitmapped tools using this scripting approach. If you haven't noticed already, these scripts mimic what you would do manually with your mouse, selecting various tools and drawing with them. It's pretty cool that you can actually script out these choices and movements with LiveCode.

In my next blog entry, I take these bitmap graphic scripting skills to the next level by using them to graph any mathematical equation, including lines, parabolas, the sine curve, whatever. I know, you can hardly wait.

Note: I deliberately have not provided any LiveCode file with this blog post. I'll include later one stack with all of the codes described in all the postings associated with this topic.