Sunday, September 23, 2012

A Proof As Proof

Alright, this one needs a preface. Also, if you don't like number theory, skip to the next entry.

This is a proof, as in a schematic for reaching a solution, like you see in mathematics. Proofs in math are to show how theorems are universally true. This isn't precisely like that, but hopefully you get the idea.

This is also proof of something, which is different from "a proof." This is proof that my brain never shuts up, even when I'm supposed to be working and focusing on something else. Like when I'm at work, taking calls, and it's relatively busy, so over the course of an eight hour shift, I'm averaging 30- to 45-second breaks between calls. That's not a lot of time when it comes to thinking about something other than work. Especially when you think about averages: sometimes I get a break that's longer than that, and sometimes I get no break at all. But still my brain keeps spinning.

This is also proof (same definition as the previous paragraph, not the same as the first) that I'm out of practice coding, because none of what follows is a legitimate language, but more a blend between Visual Basic 1, ActionScript 2 and 3, Excel formulae, and some just plain made up to express ideas I don't know the right code for off the top of my head.

And this was conceived, designed, and written (by hand on a sheet of paper) in about 3 days, just at work.
getlist(primes);
listcount(primes) -> m;
listvalue(primes; m) -> n;
lblNext;
if (n>2) {
___n+2 -> t;
}
else {
___n+1 -> t;
}
loop (d=0) {
___if (m-1=0) {
______goto lblAdd;
___}
___m-1 -> m;
___(t / listvalue(primes; m)) - floor(t / listvalue(primes; m), 1) -> d
}
goto lblNext
lblAdd
addItem(listcount(primes) + 1; 
If you can't follow along, no worries.

This is a brute-force prime number generator. It takes a pre-existing list of prime numbers "getlist(primes)", finds the last value in the list (the next two lines). If the last value is "2" it adds one to the value, and starts testing for a state I like to call "primeness" (adding one, because I know that the next prime number is 3); if the last prime number in the list is greater than 2, it adds 2, which skips even numbers, cutting the number of cycles in half.

Before I explain the next part, I need to explain another part about primes. Most people know that primes are numbers that can't be divided by any numbers other than one and itself, but that's not quite true. What's really true is that primes are numbers whose factors include no other primes other than itself. A "prime factor" is a number that's used to multiply to get another number, for example, the prime factors of 6 are 2 and 3. The prime factors of 12 are not 2 and 6 or 3 and 4, because 6 and 4 are not primes.

What this program does, instead of dividing the test number (t) by every number between 1 and itself, divides the test number by every prime between itself and the lowest prime on the list.

That's what this next part does. The loop circles until the value "d" becomes equal to zero, and I'll explain "d" in a moment.

First, the program has to check to make sure that it hasn't reached the end of the list. That's what the little if-statement checks. Then it does a factorization check.

"Floor" is a term from Microsoft Excel that rounds a value down to the whole number (",1"). So if I divide, say, 9 (which is the next odd non-prime) by the first prime on the list, 7, I get a value around 1.29. Subtract from that the "floored" value of itself, and... well the important thing is that it isn't zero. So the loop cycles again. The next number it checks is 5. Five doesn't divide out evenly... but the next lowest prime on the list does. (It's 3, if you didn't know).

So 9 divided by 3 is 3 (I hope that's not a shock) and 9 divided by 3, floored, is also 3. Subtract the two from each other and you finally do get zero. Now that you've reached zero, the loop ends... and what happens? The program sends it back up to choose the next number (11).

No, I'm not going to tell you how it works with 11. You'll have to figure that out yourself.

When it finds a prime, the program adds it to the list, and can be re-run to go hunting for the next prime number.

Now, I know these programs already exist, and the existing ones can probably do more sophisticatedly with fewer lines than my amateur attempt, but that's not the point. The point is that my head won't shut up.

No comments:

Post a Comment