# graphing primes

• May 26th, 2008, 11:36 AM
mysecondwish
graphing primes
I did this just for fun.

fig 1
http://a682.ac-images.myspacecdn.com...6c2d429661.jpg

fig 2

in (fig 1) 2^x*.5+1 intersects always and only with primes who's base2 conversion of the division table (fig 2) is converted to base10.

fig 1:
s is the base2 converted to base10 and n is countable integers.

fig 2:
to get the base 2 numbers from the division table I made all whole numbers 1 and numbers with a decimal 0.

I would like to know why this happens, if this has been discovered before and by who? Any help would be greatly appreciated, thanks.
• May 26th, 2008, 12:40 PM
serpicojr
Could you describe this a little more carefully?

First, the curve you're plotting is y = 2<sup>x</sup>/2+1 = 2<sup>x-1</sup>+1, correct?

Second, I don't understand what you mean by "s is the base2 converted to base10". The only interpretation I can come up with is, "Take a number n, write it in base 2, and then consider this as an expansion in base 10, and take the result." This cannot be right, as 16 base 2 is 10,000 and 20 base 2 is 10,010, but clearly this is not what's happening in your graph, as whatever 20 gets sent to is more than twice what 16 gets sent to.
• May 26th, 2008, 01:59 PM
mysecondwish
Quote:

Originally Posted by serpicojr
Could you describe this a little more carefully?

First, the curve you're plotting is y = 2<sup>x</sup>/2+1 = 2<sup>x-1</sup>+1, correct?

Second, I don't understand what you mean by "s is the base2 converted to base10". The only interpretation I can come up with is, "Take a number n, write it in base 2, and then consider this as an expansion in base 10, and take the result." This cannot be right, as 16 base 2 is 10,000 and 20 base 2 is 10,010, but clearly this is not what's happening in your graph, as whatever 20 gets sent to is more than twice what 16 gets sent to.

y = 2<sup>x</sup>/2+1 = 2<sup>x-1</sup>+1 is correct.

The curve is only half of what's going on. the picture I supplied for what I'm doing with the conversion didn't come out readable I see. well in text here is what I did:

1/1=1 | and is binary 1 or in decimal 1
2/1=2 | 2/2=1 and is binary 11 or in decimal 5
3/1=3 | 3/2=1.5 | 3/3=1 and is binary 101 or in decimal 13
4/1=4 | 4/2=2 | 4/3=1.3 | 4/4=1 and is binary 1101 or in decimal 17
5/1=5 | 5/2=2.5 | 5/3=1.6 | 5/4=1.2 | 5/5=1 and in binary is 10001 or in decimal57

so what I am doing is taking each whole number as 1 and any number with a decimal part as 0. So s is 1:5:13:17:57 and so on. I hope this helps out.
• May 26th, 2008, 05:51 PM
serpicojr

-----------------

Okay, so suppose p is prime. Now consider the numbers:

p/p, p/(p-1), p/(p-2), ..., p/3, p/2, p/1

Since p is a prime, it has no proper factors, so the numbers p/(p-1), ..., p/2 are not whole numbers. So, according to the definition of s, this gives s = 100...001, which p-2 0's between the 1's. And this is exactly 2<sup>p-1</sup>+1.

See if you can show the other direction: if 2<sup>n-1</sup>+1 = s, then show that n is prime.
• May 27th, 2008, 05:58 PM
mysecondwish
Yes and no, see 2<sup>x-1</sup>+1 = 1[00.. ..00]1 were [00.. ..00] is x-2.

And not every 1[00.. ..00]1 is a prime.

s in binary:
1
11
101
1101
10001
111001
1000001
11010001
101000001
1100100001
10000000001
111101000001
1000000000001
11000010000001
101010000000001

There is a pattern to s but it is not a numerical pattern, I found it more to be a graphical one. Look at the first vertical line of 1's, then the 2'nd line, and so on. The first line (or column) of 1's is every line, the second line of 1's is every other, the third line of 1's is every 3rd and so on. This pattern makes the next row of binary relatively easy to find. There are other aspects to the graphical pattern of s too but they are a bit harder to explain in words.

I'm looking for a numerical pattern to s but for now the only one that I have found of significance is that when s = 2<sup>n-1</sup>+1 then n is prime and
when s <> 2<sup>n-1</sup>+1 then the number is not prime.
Do I need to figure out how n = s?
• May 27th, 2008, 06:18 PM
serpicojr
Quote:

Originally Posted by mysecondwish
Yes and no, see 2<sup>x-1</sup>+1 = 1[00.. ..00]1 were [00.. ..00] is x-2.

And not every 1[00.. ..00]1 is a prime.

What I was trying to get at is that s is of the form 10...01 if and only if n is prime.

Quote:

There is a pattern to s but it is not a numerical pattern, I found it more to be a graphical one. Look at the first vertical line of 1's, then the 2'nd line, and so on. The first line (or column) of 1's is every line, the second line of 1's is every other, the third line of 1's is every 3rd and so on. This pattern makes the next row of binary relatively easy to find.
Note that s has a 1 in the mth digit slot if and only if m divides n, i.e. if n is a multiple of m. Thus it makes sense that the mth digit slot is 1 once every m times.

Quote:

I'm looking for a numerical pattern to s but for now the only one that I have found of significance is that when s = 2<sup>n-1</sup>+1 then n is prime and
when s <> 2<sup>n-1</sup>+1 then the number is not prime.
Do I need to figure out how n = s?
I'm not sure what sort of numerical pattern you're looking for. Do you mean like finding s as a nice function of n? I don't think you're going to end up doing that too easily--your function has a very "arithmetic" feel to it, and such functions typically can't b expressed in a nicer way than the way they're originally defined.
• May 27th, 2008, 07:44 PM
mysecondwish
Quote:

Do you mean like finding s as a nice function of n? I don't think you're going to end up doing that too easily
I agree, it most likely cannot be done.

But it would be cool if it could be done.
It still wouldn't help the search for primes at all.
For instance a 1 million digit prime would need to have 2<sup>p-1</sup>+1 bits of storage.
I'm going to guess and say that a 1 million digit prime would fill our universe a couple of times with data.
• May 28th, 2008, 05:57 AM
DivideByZero
[quote="mysecondwish"]
Quote:

Originally Posted by serpicojr
1/1=1 | and is binary 1 or in decimal 1
2/1=2 | 2/2=1 and is binary 11 or in decimal 5
3/1=3 | 3/2=1.5 | 3/3=1 and is binary 101 or in decimal 13
4/1=4 | 4/2=2 | 4/3=1.3 | 4/4=1 and is binary 1101 or in decimal 17
5/1=5 | 5/2=2.5 | 5/3=1.6 | 5/4=1.2 | 5/5=1 and in binary is 10001 or in decimal57

could you please explain how you got the decimal values?

I don't see how you got '5' for the decimal value for 2/1, 2/2
how did you get the binary value? 2 != 11 in binary
• May 28th, 2008, 07:48 AM
sunshinewarrior
[quote="DivideByZero"]
Quote:

Originally Posted by mysecondwish
Quote:

Originally Posted by serpicojr
1/1=1 | and is binary 1 or in decimal 1
2/1=2 | 2/2=1 and is binary 11 or in decimal 5
3/1=3 | 3/2=1.5 | 3/3=1 and is binary 101 or in decimal 13
4/1=4 | 4/2=2 | 4/3=1.3 | 4/4=1 and is binary 1101 or in decimal 17
5/1=5 | 5/2=2.5 | 5/3=1.6 | 5/4=1.2 | 5/5=1 and in binary is 10001 or in decimal57

could you please explain how you got the decimal values?

I don't see how you got '5' for the decimal value for 2/1, 2/2
how did you get the binary value? 2 != 11 in binary

I've just got it.

1. For each natural number, write out the result of dividing it by each natural number up to and including itself.

2. Where it divides perfectly (leaving an integer and no remainder) write 1. Where it does not, write 0.

3. Write this sequence of 1s and 0s out as a binary number.

4. Convert that binary number to base 10.

Makes sense?
• May 28th, 2008, 08:36 AM
mysecondwish
Quote:

Originally Posted by sunshinewarrior
I've just got it.

1. For each natural number, write out the result of dividing it by each natural number up to and including itself.

2. Where it divides perfectly (leaving an integer and no remainder) write 1. Where it does not, write 0.

3. Write this sequence of 1s and 0s out as a binary number.

4. Convert that binary number to base 10.

Makes sense?

yep thats what i did.
• May 29th, 2008, 05:56 AM
DivideByZero
oooooo Thats really cool!!!

Have you figured out why it works yet?

but something is still wrong..
1/1=1 | and is binary 1 or in decimal 1 [ok]
2/1=2 | 2/2=1 and is binary 11 or in decimal 5 [11 in decimal is 3]
3/1=3 | 3/2=1.5 | 3/3=1 and is binary 101 or in decimal 13 [101 in decimal is 5]
4/1=4 | 4/2=2 | 4/3=1.3 | 4/4=1 and is binary 1101 or in decimal 17 [1101 in decimal is 
5/1=5 | 5/2=2.5 | 5/3=1.6 | 5/4=1.2 | 5/5=1 and in binary is 10001 or in decimal57  in decimal is 
well i guess it doesn't really change the effect because they are still prime numbers (except for 1)!

good job!!
• May 29th, 2008, 08:33 AM
serpicojr
Quote:

Originally Posted by DivideByZero
but something is still wrong..
1/1=1 | and is binary 1 or in decimal 1 [ok]
2/1=2 | 2/2=1 and is binary 11 or in decimal 5 [11 in decimal is 3]
3/1=3 | 3/2=1.5 | 3/3=1 and is binary 101 or in decimal 13 [101 in decimal is 5]
4/1=4 | 4/2=2 | 4/3=1.3 | 4/4=1 and is binary 1101 or in decimal 17 [1101 in decimal is 
5/1=5 | 5/2=2.5 | 5/3=1.6 | 5/4=1.2 | 5/5=1 and in binary is 10001 or in decimal57  in decimal is 

Good eye!

Quote:

well i guess it doesn't really change the effect because they are still prime numbers (except for 1)!
I don't think that was the point. In fact, for 6, we get 111001, which is 57, not a prime. The point was, for primes p, you always get 2<sup>p-1</sup>+1 via this process.

Quote:

Have you figured out why it works yet?
We did within the first few comments.
• May 29th, 2008, 10:02 AM
sunshinewarrior
Quote:

Originally Posted by serpicojr
Quote:

Originally Posted by DivideByZero
but something is still wrong..
1/1=1 | and is binary 1 or in decimal 1 [ok]
2/1=2 | 2/2=1 and is binary 11 or in decimal 5 [11 in decimal is 3]
3/1=3 | 3/2=1.5 | 3/3=1 and is binary 101 or in decimal 13 [101 in decimal is 5]
4/1=4 | 4/2=2 | 4/3=1.3 | 4/4=1 and is binary 1101 or in decimal 17 [1101 in decimal is 
5/1=5 | 5/2=2.5 | 5/3=1.6 | 5/4=1.2 | 5/5=1 and in binary is 10001 or in decimal57  in decimal is 

Good eye!

Quote:

well i guess it doesn't really change the effect because they are still prime numbers (except for 1)!
I don't think that was the point. In fact, for 6, we get 111001, which is 57, not a prime. The point was, for primes p, you always get 2<sup>p-1</sup>+1 via this process.

Quote:

Have you figured out why it works yet?
We did within the first few comments.

Yeahbut - you're too quick for us tyros. We're still catching up and I've only today, having thought about it overnight, even been able to read with udnerstanding your point about 100...001 with p-2 zeros being significant.

Ah well.

Also, I presume, since 1000...0001 represent 2n + 1, a reversal, with 111111....11111 (for p x 1s) represents Mersenne numbers? And amongst those will be Mersenne primes?
• May 29th, 2008, 03:14 PM
serpicojr
Yes!
• July 2nd, 2009, 10:49 AM
mysecondwish
sorry to bump this, but I was wondering if this could be a proof of contradiction for p vs. np? As there is no way this could be np!
• July 2nd, 2009, 02:29 PM
DrRocket
Quote:

Originally Posted by serpicojr

What I was trying to get at is that s is of the form 10...01 if and only if n is prime.

This not true in either direction. What you have described are primes of the form . In fact such numbers are precisely those of the form 10...01 base 2. Not all numbers of this form are prime, for instance is not prime (9 is 1001 base 2). In fact, all numbers of this form are divisible by three. This follows simply because 2 is congruent to 1 mod 3.

It is the "+1" that defeats your conjecture so soundly. Primes of the form are called Mersenne primes. They have been extensively studied. Only 47 are known. They can be quite large. It is an open question as to whether the number of Mersenne primes is infinite.
• July 2nd, 2009, 04:49 PM
mysecondwish
Quote:

Originally Posted by DrRocket
Quote:

Originally Posted by serpicojr

What I was trying to get at is that s is of the form 10...01 if and only if n is prime.

This not true in either direction. What you have described are primes of the form . In fact such numbers are precisely those of the form 10...01 base 2. Not all numbers of this form are prime, for instance is not prime (9 is 1001 base 2). In fact, all numbers of this form are divisible by three. This follows simply because 2 is congruent to 1 mod 3.

It is the "+1" that defeats your conjecture so soundly. Primes of the form are called Mersenne primes. They have been extensively studied. Only 47 are known. They can be quite large. It is an open question as to whether the number of Mersenne primes is infinite.

DrRocket your right, but not in the context of this discussion. serpicojr is correct in the matter at hand.
• August 19th, 2009, 12:23 PM
talanum1
Put those numbers of mysecondwish in the opposite order (take it as a matrix and transpose it) and you have the division matrix. This matrix has several "stair" patterns in it. I'm working on formularising them so that a portion of it can be constructed at any column nummber. I'm attempting to use it to get a lower bound on the amount of composites smaller than a given number.

I use the submatrix with columns in P = {x | x = 5 (mod 6)} and rows in S = {x | x = 1 (mod 6)} union {x | x = 5 (mod 6)}. In this matrix the square root boundry coincides with a stair pattern of the first twin divisors of the column number. Where first twin divisors are defined as: a,b devides c (for c the column number in P) and a,b not equal to c and a,b (both) devides no smaller column number and a,b are adjacent in S.