Tuesday, May 06, 2008

Clicking Into Place

I know I said my next post would be on statistics that seem to make sense but are really irrational, and I am halfway through that post. But, due to Bush's brainwashing me with NSA satellites or something, um...well...you get this post instead.

I’m sure you’ve probably heard the phrase, “It just clicked into place.” Last night (or rather, very early this morning) I experienced that. Literally. Like it was an actual audible “click” sound as a realized something regarding the prime numbers in the “factor field” that I’ve developed in Excel.

To give some background, I’ve been conversing with someone via e-mail after my post the other day that included my reference to the factor field. This person has looked over my spreadsheet and given some comments, and last night I responded to him. Which meant that in the process I was looking over the sheet a great deal and doing lots of mathematical conversions and the like.

Anyway, I went to bed after I sent the e-mail. And at about 12:30 in the morning, I suddenly shot up in bed because I heard the “click” as something slid into place in my brain. Yeah, I did the whole caricature thing of having the light dawn on me :-)

Of course the only problem is that there’s like maybe a dozen people on Earth who would care about my realization, and I don’t know any of them personally. But I figure why not post it into the Internet anyway? So I will.

First, I should note that with the factor field, I’ve mentioned the “spike” that occurs spaced out every 6 digits. Because of this, I wanted to see what prime numbers would look like in base-6 format (using only 0-5 for your digits, just as binary uses only 1 and 0). Last night, I compiled a short list of some of the primes and e-mailed them to the person I’ve been corresponding with, so here's the list of primes from 2 - 101 with their corresponding base-6 conversion:

2 = 2
3 = 3
5 = 5
7 = 11
11 = 15
13 = 21
17 = 25
19 = 31
23 = 35
29 = 45
31 = 51
37 = 101
41 = 105
43 = 111
47 = 115
53 = 125
59 = 135
61 = 141
67 = 151
71 = 155
73 = 201
79 = 211
83 = 215
89 = 225
97 = 241
101 = 245

And just for fun, converting the last 10 primes on the Excel sheet gives us this:

65413 = 1222501
65419 = 1222511
65423 = 1222515
65437 = 1222541
65447 = 1222555
65449 = 1223001
65479 = 1223051
65497 = 1223121
65519 = 1223155
65521 = 1223201

So as you can see, all the prime numbers after 2 & 3 end in either 1 or 5 in base-6.

Now because my hypothesis (which I lack the mathematical skills to prove beyond a shadow of a doubt) is that all prime numbers end in 1 or 5 in base-6, as I was trying to fall asleep I thought: “At what point do the prime numbers interfere with the 6-spike?” That is, at what point on the number series do prime numbers fall either 1 above or 1 below the spike (1 above the spike corresponds to a number ending in 5, one below corresponds to a number ending in 1).

Obviously 2 and 3 are ruled out from the get-go, because 2 x 3 creates the 6-spike. So I started with 5. And here’s what I got:

In this graphic, the blue lines are the 6-spike. The red cells are those that occur either 1 above or 1 below the 6-spike. The black cells are the other cells that do not fall either one above or one below the 6-spike.

I left the factors in the cells too. As a result, trace the 5-line down and you see that the first time it falls 1 above or 1 below the 6-spike (1 above in this case) is at 5 x 1. The next time it falls 1 above or 1 below the 6-spike (1 below in this case) is at 5 x 5. The next time (1 above) is at 5 x 7. Then again (1 below) at 5 x 11. Finally, it comes 1 above at 5 x 13.

Now look at the 7 line. 7 does the exact same thing but with the above/below polarity switched! The first time it appears is 1 below at 7 x 1. Then at 1 above at 7 x 5, etc. We see the same thing with the 11 and 13 lines. Thus we have:

N = multiple of 6.

N - 1 goes in an above/below sequence.

N + 1 goes in a below/above sequence.

And the real kicker…the N +/- 1 is itself the number that the factors are based on! Thus, take a factor of 6. Subtract 1. It is now 1 below a factor of 6. Multiply by 5 (i.e. 6 - 1) and you will be 1 above a factor of 6. Multiply by 7 (i.e. 6 + 1) and you will be 1 below a factor of 6. Multiply by 11 (i.e. [2 x 6] – 1) and you will be one above a factor of 6. Multiply by 13 (i.e. [2 x 6] + 1) and you will be one below a factor of 6.

Let’s give an example. 24 is a factor of 6.

24 – 1 = 23. 23 x 5 = 115. 115 – 1 = 114. 114 = 6 x 19.

24 + 1 = 25. 25 x 5 = 125. 125 + 1 = 126. 126 = 6 x 21.

24 – 1 = 23. 23 x 7 = 161. 161 +1 = 162. 162 = 6 x 27.

24 + 1 = 25. 25 x 7 = 175. 175 – 1 = 174. 174 = 6 x 29.

24 + (2 x 6) – 1 = 35. 35 x 5 = 175. 175 – 1 = 174. 174 = 6 x 29.

24 + (2 x 6) + 1 = 37. 37 x 5 = 185. 185 + 1 = 186. 186 = 6 x 31.

24 + (2 x 6) – 1 = 35. 35 x 7 = 245. 245 + 1 = 246. 246 = 6 x 41.

24 + (2 x 6) + 1 = 37. 37 x 7 = 259. 259 – 1 = 258. 258 = 6 x 43.

So, to generalize it further, let us define an N class number as a positive number that is divisible evenly by 6.

1. (Nx - 1) x (Ny - 1) = X. X – 1 is an N class number.
2. (Nx + 1) x (Ny - 1) = X. X + 1 is an N class number.
3. (Nx - 1) x (Ny + 1) = X. X + 1 is an N class number.
4. (Nx + 1) x (Ny +1) = X. X – 1 is an N class number.

To test this, let Nx = 36 and Ny = 12.

1. (36 – 1) x (12 – 1) = 35 x 11 = 385. Subtract 1 and 384 = 6 x 64.
2. (36 + 1) x (12 -1) = 37 x 11 = 407. Add 1 and 408 = 6 x 68.
3. (36 – 1) x (12 +1) = 35 x 13 = 455. Add 1 and 456 = 6 x 76.
4. (36 + 1) x (12 + 1) = 37 x 13 = 481. Subtract 1 and 480 = 6 x 80.

But we can further generalize this by creating a new class, which I will call the P class. The P class is defined as any number that is N +/- 1. So take any N class, add or subtract one from it, and that is a P class number. From the above, we therefore know that any P class multiplied by another P class number yields another P class number. It comes in the following format.

Let us define Pdown as a N – 1 class number and Pup as an N + 1 number.

1. Pdown x Pdown = Pdown.
2. Pup x Pdown = Pup.
3. Pdown x Pup = Pup.
4. Pup x Pup = Pdown.

Now my theory is that all prime numbers are P class numbers, but not all P class numbers are prime numbers. After all, since a P class x a P class yields a P class, then we have proof that P classes can exist with factors. But here’s my theory on that: the only P class numbers that are not primes are those P classes that are created by multiplying other P class variables.

In other words, when thinking about primes, one need not worry about anything other than P class integers.

Let me explain by showing the first few primes again. After 2 and 3 (which create the 6-spike in the first place) we have 5, 7, 11, 13, 17, 19. Each of these shows both sides of the 6-spike.

The first “break” occurs after 23, because 25 has factors. But what are the factors of 25? Only 5 x 5. And 5 is a prime number. In fact, 5 is the smallest prime number that comes into play (again, because 2 and 3 are working to create the 6-spike so they are irrelevant here). In fact, if we multiply the smallest relevant primes, we get:

5 x 5 = 25.
5 x 7 = 35
7 x 7 = 49
5 x 11 = 55
5 x 13 = 65
7 x 11 = 77
5 x 17 = 85
7 x 13 = 91
5 x 19 = 95

And these results are all the numbers that are missing from the 6-spike as primes.

In any case, I think it’s safe to say that we can define a prime number as any P class number that is not divisible by any other P class number. And I also think that P class number that are divisible by any numbers at all are only divisible by other P class numbers. Therefore, we need not worry about any other numbers when testing for primes.

Now I'm sure there's probably something theologically relevant here, but since I was up until about 3:30 this morning working on this...I'll let Steve figure out the application for you :-P

1. "Now because my hypothesis (which I lack the mathematical skills to prove beyond a shadow of a doubt) is that all prime numbers end in 1 or 5 in base-6"

It's actually not too difficult to show that all primes will end in 1 or 5 in base 6 (although not all numbers ending in 1 or 5 are primes), with the exception of 2 and 3.

We can categorically eliminate numbers that end in 0, 2, and 4. These are non-odd numbers. No prime other than 2 will be even.

That leaves 1, 3, and 5.

Let Xn be any number that ends with the digit 3 in base 6, except 3. This number may be represented as:

Xn = 3 + 6n, where n > 0

We can factor 3 out of the expression:

Xn = 3(1 + 6n), where n > 0

Therefore, all numbers ending in the digit 3 in base 6 are divisible by 3 => No prime numbers will end in 3 in base 6.

That leaves 1 and 5.

Your hypothesis is fact.

:D

2. /me is waaaaayyyyyy too dumb to understand more than the 1st 4 paragraphs. :-)

3. Hey, thanks for the proof there, Mike :-)

This is the problem I have insofar as I'm public skewl edjukated when it comes to math (which actually means I learned math by reading Number Theory books on my own). And I also like science, so I kinda just merge the two and use math the same way as the scientific method (hypothesize, test, review results, tweak hypothesis, etc.)

It's nice having someone who can do the actual proof to show beyond all doubt that something is so!

Building off of it, given my above definitions (the P class is N +/- 1; N is a multiple of 6), all P class numbers would end in 1 or 5 in base-6. Therefore, my conclusion that all primes are P class (but not all P class are primes) is also supported by your proof that all primes end in either 1 or 5 here too.

It does make me wonder if there's an easy way (relatively speaking) to figure out large primes. For instance, coming up with the million digit long prime number. We could try 6 followed by 999,998 0s and ending in a 1. This would be a P class number (since 6 followed by 999,999 0s is divisible by 6, and we're simply adding 1 to that number). So we would know that it would have the POTENTIAL to be a prime number. Only problem is that I doubt there's an easy way to tell whether any P classes multiply together to form 600000...0000001 or SOMEONE would have already figured it out.

A method that I think should work is this: Find the square root of a P class number to give us the upper limit of how many factors we'd need to find, since any factors X has that are higher than the square root of X *HAVE* to be multiplied by numbers that are smaller than the square root of X too, so searching all factors below the square root of X will reveal these (example: the square root of 99 is 9.94..., which we can round up to 10. Even though 11 is a factor of 99, we don't have to search for it because we will find it when we see that 9 is a factor of 99.). Then we test the P class numbers that are smaller than the square root of the P class number we are searching for (which is 1/3 of the remaining numbers--those that end in 1 or 5 in base-6). If there are no matches, we've demonstrated it's prime.

So, if we could find the square root of 60000...000001 then there shouldn't be THAT many tests to do afterwards........

:-P

4. This is the sweetest thing ever. I can't lie. I'm a complete Math nerd. I just don't do much with it anymore... I really enjoyed reading this!

5. I just included this (after quoting Mike's proof) on my personal blog, so I thought I'd add it here too :-)

-----

This got me to thinking about my other hypothesis that all P numbers are either prime or have factors that are other P numbers. And now I've been able to prove that.

Remember that I previously defined a P number as: "The P class is defined as any number that is N +/- 1" and N was defined as "a positive number that is divisible evenly by 6." In reality, this definition is too restrictive, so allow me to redefine it slightly:

A P class number is any number in base-6 whose last digit (read left to right) is either a 1 or a 5.

Because this is a base-6 definition, everything in my previous definition still works (N is a multiple of 6 in base-10, so all N numbers will convert to ending in a 0 in base-6; N + 1 or N - 1 in base-10 will convert to a number that ends in either 1 or 5 in base-6 respectively).

Under this new definition of a P class number, we can also include the number 1 (as it is a number whose last digit is either a 1 or a 5).

Now, my hypothesis is that a P class number must be either prime or its factors must also be P class numbers. Since prime numbers are divisible by 1 and 1 is a P class number, we can actually exclude the "prime" portion from the above and simply say: A P class number can only be divisible by another P class number.

To prove this, we need to demonstrate that A) any P class number multiplied by another P class number will give us yet a third P class number (which I demonstrated in my previous post) and B) no non P class number can ever be multiplied by any other number (P class or not) to form a P class number. So to prove it:

1. Any number that ends in digit x multiplied by a number that ends in 1 will have x as it's terminating digit. Therefore, if multiplying by a P class number that ends in 1 to get another P class number, you must multiply by a number that ends in either 1 or 5. Therefore, multiplying a P class number that ends in 1 requires multiplying by another P class number to yield a P class number.

2. In an even base system (and base 6 is an even base system since 6 is even), any number x multiplied by any even number will be an even number. Examples (in base-6):

3 x 2 = 10 (x = 3)
4 x 2 = 12 (x = 4)
12 x 4 = 52 (x = 12)

Therefore, any number multiplied by 0, 2, or 4 must be an even number and cannot end in either 1 or 5.

3. An even number multiplied by a number that ends in 3 will end in 0 in base-6 (we don't really need to demonstrate this step, since even numbers were excluded in step 2, but I'm including it just to be complete); an odd number multiplied by a number that ends in 3 will end in 3 in base-6. Example:

2 x 3 = 10.
3 x 3 = 13.
4 x 3 = 20.
5 x 3 = 23.

Therefore, no number multiplied by a number ending in 3 could end in 1 or 5.

4. This leaves only 5. Taking a look at the multiplication table of 5 in base-6 is quite interesting:

5 x 1 = 5
5 x 2 = 14
5 x 3 = 23
5 x 4 = 32
5 x 5 = 41
5 x 10 = 50

If you note, this has the same type of thing we find in base-10 systems with the number 9. In base 10, you can construct the multiples of 9 by simply writing a column of numbers from 0 - 9. Then, to the right of each number, write the inverse (9 - 0) next to the previous number. Hence:

09
18
27
36
45
54
63
72
81
90

Here, the same thing is seen in base-6, only with the range of 0-5:

05
14
23
32
41
50

Likewise, just as the digits in the 9 sequence add up to 9 (i.e. 18 is 1 + 8 = 9, 36 is 3 + 6 = 9), so in base-6 in the 5 sequence the digits add up to 5 (23 is 2 + 3 = 5; 41 is 4 + 1 = 5). I'm guessing (though I haven't tested it) that this is the case of any even base system. (I.e., given base N where N is an even number, then the multiplication table of N - 1 will display the above behavior.)

In any case, that's just something I discovered but it's not relevant to the current discussion. What is relevent is this: a number that ends in 5 can only end in 1 if multiplied by a number that ends in 5; and a number that ends in 5 can only end in 5 if multiplied by another number that ends in 1. Therefore, the only way to make another P class number multiplying by a P class that ends in 5 is if you multiply it by another P class number.

Conclusion: A P class number can only be divisible by another P class number.

-----

6. Laura said:
---
This is the sweetest thing ever. I can't lie. I'm a complete Math nerd. I just don't do much with it anymore... I really enjoyed reading this!
---

Somehow I missed this before! So you must be one of the "maybe a dozen people on Earth who would care" about this! :-D

Personally, I'm a born-again math nerd. I started out loving math as a kid, but moved to a new school district in junior high where they put me in remedial math for two years in a row! Why? Because "everyone in 7th and 8th grade takes these classes." So I started to hate math then. It wasn't really until after I started college that I began to like it again, and then just because I was studying physics. So now I'm a math-phile yet again.

7. I did enjoy this post.

But

Well, of course, all the prime numbers greater than 3 will have a remainder (modulo 6) of 1 or 5.

Because,

If they had remainder 0, they'd be divisible by 6.
If they had remainder 2, they'd be divisible by 2.
If they had remainder 3, they'd be divisible by 3.
If they had remainder 4, they'd be divisible by 4.

So, I'm sure its true, but I'm not sure it helps. Or maybe I missed the point.

You should be able to construct an even more elaborate grid with 30 (2x3x5), and 210 (2x3x5x7) and so forth.

for 30:

rem | Screened? (affirmative means number is not prime)

0 | y
1 | n
2 | y
3 | y
4 | y
5 | y
6 | y
7 | n
8 | y
9 | y
10 | y
11 | n
12 | y
13 | n
14 | y
15 | y
16 | y
17 | n
18 | y
19 | n
20 | y
21 | y
22 | y
23 | n
24 | y
25 | y
26 | y
27 | y
28 | y
29 | n

The filter pattern is dictated by the remainder being decomposable by primes that are already included in the base.

Maybe this could provide some computational simplicity in looking for very large prime numbers, since the product of sequential primes get very fast, very quickly. The problem is that the filter also gets very gappy very quickly, particularly in the high end of the remainder (one doesn't notice this with 6, because there are only two data points).

In fact, if I recall correctly, one technique for looking for large primes is explicitly multiplying smaller primes and then adding one (which takes partial advantage) of the discussion above.

-Turretinfan

8. TF said:
---
In fact, if I recall correctly, one technique for looking for large primes is explicitly multiplying smaller primes and then adding one (which takes partial advantage) of the discussion above.
---

Actually, that wouldn't work. Even without other considerations, it would only be possible if you included 2 as one of the primes--otherwise, you will get an odd answer and adding 1 to it will make it an even number, and therefore impossible to be a prime.

But since I've shown that all primes are a P class (that is, all primes have to fit 6n +/- 1 in base 10), and multiplying two P classes together yields another P class number, then after multiplying two primes together you'd have to either add or subtract 2 (depending on if it's mod 6 ends in 1 or 5) to get to another P class number which might possibly be a prime number.

Oh well. It's always fun to think :-)

9. Yes, of course 2 has to be included. And it does work:
1 +1 = 2 which is prime
1*2=2 +1 = 3 which is prime
1*2*3=6 +1 = 7 which is prime
1*2*3*5=30 +1 = 31 which is prime
1*2*3*5*7=210 +1 = 211 which is prime
1*2*3*5*7*11=2310 +1 = 2311 which is prime

I'm not sure whether it has been proved.

-TurretinFan

10. Ah, that makes sense then because 2 isn't one of the P class numbers, so it wouldn't fit the rule I mentioned.