Ramsey Primes


by ramsey2879
Tags: primes, ramsey
ramsey2879
ramsey2879 is offline
#1
Feb8-12, 07:57 PM
P: 891
Ramsey Primes are those generated from a simple criteria that is easy to check. I checked all odd numbers from 1 to 1 million and 29455 numbers met the criteria. None were composite.

The check is to do the following sequence mod P and check to see that the (P-1)/2 term is zero and no term prior to that is zero.

The test sequence is S(0) = 2, S(1) = 3, S(n) = 6*S(n-1) - S(n-2) - 6. If P is prime, then S((P-1)/2) is divisible by P, but I am interested in a test that is valid only for primes. S((35-1)/2) is divisible by 35 but that is not the first term divisible by 35. Only primes seem to meet the more restricted criteria, i.e. have no term divisible by P prior to S((P-1)/2).

The first two Ramsey primes are 11 and 13 which I call a Ramsey Twin. The largest Ramsey Twin under 1 million is (998651, 998653).

Any thoughts are welcome.

Edit So far about 5 in 13 primes are Ramsey Primes so my test has limited value unless it can be proven that only primes can meet the test. Any way to prove this?
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
ramsey2879
ramsey2879 is offline
#2
Feb9-12, 07:25 AM
P: 891
Quote Quote by ramsey2879 View Post
Ramsey Primes are those generated from a simple criteria that is easy to check. I checked all odd numbers from 1 to 1 million and 29455 numbers met the criteria. None were composite.

The check is to do the following sequence mod P and check to see that the (P-1)/2 term is zero and no term prior to that is zero.

The test sequence is S(0) = 2, S(1) = 3, S(n) = 6*S(n-1) - S(n-2) - 6. If P is prime, then S((P-1)/2) is divisible by P, but I am interested in a test that is valid only for primes. S((35-1)/2) is divisible by 35 but that is not the first term divisible by 35. Only primes seem to meet the more restricted criteria, i.e. have no term divisible by P prior to S((P-1)/2).

The first two Ramsey primes are 11 and 13 which I call a Ramsey Twin. The largest Ramsey Twin under 1 million is (998651, 998653).

Any thoughts are welcome.

Edit So far about 5 in 13 primes are Ramsey Primes so my test has limited value unless it can be proven that only primes can meet the test. Any way to prove this?
I am sorry for the misinformation, but in the series 2,3,...S((P-1)/2), S((P-1)/2) is not always divisible by prime P. In fact for some primes no term is divisible by P. I was working with the same recursive sequence only the first two terms were S(0) = 0 and S(1) = 1 and something like S(P+1) was always divisible by prime P. In focusing on Ramsey Primes, I neglected to note that not all sequences 0,1, ... mod P had the sub sequence 3,2,3 within it.

Still about 5 in 13 primes are Ramsey Primes. Also, Primes 3 and 5 are Ramsey Primes.
ramsey2879
ramsey2879 is offline
#3
Feb10-12, 05:14 PM
P: 891
My code for Mathematical is short so I will include it below for reference. There are some flaws. For instance the Reap/Sow function generates a list of the form {Null,{{prime3,prime5,prime6,prime8,...}}}. I want to generate a simple list {prime3,prime5,prime6,prime8...}. Also, the code took about an hour to pick out 31 primes between 1049000 and 1050000. Overall, about 2/3 of the prime numbers are not picked out, but that is what I am looking for code that will generate only primes, not code that will generate all primes but also include some composites. So far some 30,000 prime numbers between 5 and 1050000 were generated with no false hits. Any help improving my code will be appreciated.
Caa = 5
Reap[While[Caa < 1050001,
Co = 1;
S0 = 2;
S1 = 3;

While[Co < ((Caa-1)/2),Temp = Mod[6 S1 - S0 - 6,Caa];If[Temp <= 1,Break[]];
S0=S1;S1=Temp;Co++];
n = ((Caa-1)/2) - Co; If[n<2,If[n>0, Sow[Caa]]];
Caa++;Caa++]]

ramsey2879
ramsey2879 is offline
#4
Feb15-12, 09:20 AM
P: 891

Ramsey Primes


Quote Quote by ramsey2879 View Post
My code for Mathematical is short so I will include it below for reference. There are some flaws. For instance the Reap/Sow function generates a list of the form {Null,{{prime3,prime5,prime6,prime8,...}}}. I want to generate a simple list {prime3,prime5,prime6,prime8...}. Also, the code took about an hour to pick out 31 primes between 1049000 and 1050000. Overall, about 2/3 of the prime numbers are not picked out, but that is what I am looking for code that will generate only primes, not code that will generate all primes but also include some composites. So far some 30,000 prime numbers between 5 and 1050000 were generated with no false hits. Any help improving my code will be appreciated.
Caa = 5
Reap[While[Caa < 1050001,
Co = 1;
S0 = 2;
S1 = 3;

While[Co < ((Caa-1)/2),Temp = Mod[6 S1 - S0 - 6,Caa];If[Temp <= 1,Break[]];
S0=S1;S1=Temp;Co++];
n = ((Caa-1)/2) - Co; If[n<2,If[n>0, Sow[Caa]]];
Caa++;Caa++]]
The code was used to find 31083 primes between 3 and 1061001, no composites were picked. one problem with the code is that it requires a recursive formula to determine S((P-1)/2) Mod P so I did some manipulation to find a equivalent test that doesn't require recursion to find S((p-1)/2):

2,3,10,51 is of the Form S(n) = 6S(n-1)- S(n-2) - K K = 6 and Test is S((P-1)/2) = 0, Mod P etc
1,2,9,50 is of the Form S(n) = 6S(n-1) - S(n-2) - K K = 2 and Test is S((P-1)/2) = -1, Mod P etc

Subtracting 1 from each term reduced K by 4
Doubling each term multiplies K by 2, i.e.:
2,4,18,100 is of the Form 6S(n-1) - S(n-2) - K K = 4 and Test is S((p-1)/2 = -2, Mod P, etc
Subtracting 1 from each term again reduces K by 4 i.e. to 0,:
1,3,17,99 is of the Form 6S(n-1) - S(n-2) K = 0 Test is S((P-1)/2) = -3, Mod P, etc.
Thus a direct formula exists for S((P-1)/2)
ramsey2879
ramsey2879 is offline
#5
Feb16-12, 12:03 AM
P: 891
Bill Simpson help me with the following Mathematica code which runs more than 20 times faster.
In: Timing[f =
Compile[{{Co, _Integer}, {S0, _Integer}, {S1, _Integer}, {Caa, \
_Integer}},
Module[{xCo = Co, xS0 = S0, xS1 = S1, Temp},
While[Temp = Mod[6 xS1 - xS0 - 6, Caa]; xCo > 0 && Temp >= 1,
xS0 = xS1; xS1 = Temp; xCo--];
xCo]];
Caa = 349049001;
Reap[While[Caa < 349049501, Co = (Caa - 3)/2; S0 = 2; S1 = 3;
If[f[Co, S0, S1, Caa] == 1, Sow[Caa]];
Caa += 2]]]
Out: {11001.066`, {Null, {{349049059, 349049069, 349049179,
349049291, 349049293, 349049317, 349049333, 349049347,
349049411, 349049443}}}}
According to Mathematica there are 21 primes in the range and the code found 10 of them. Again no composites were picked out. The code appears to have a better chance of picking a given prime as the size of the prime increases. I still believe that the code can be made to speed up by first checking whether the (P-1)/2 term in the sequence equals 0 mod P before doing the recursive algorithim to see if any prior term equals 0 mod P. Also inspection of the location of a prior zero may be a step in factoring composite numbers P whose (P-1)/2 term = 0 mod P.
Norwegian
Norwegian is offline
#6
Feb16-12, 01:21 AM
P: 144
Hi,

I find this interesting, and want to look into what is going on here. Myfirst thougt was about the name Ramsey, have you just named the primes after yourself, or is there some other connection? Then where did the test sequence come from? Did you try all sequences, or did you see that this particular one had some good properties. To prove your claim, if true, one could try to use the closed form expression for S(n)

4S(n) = rn+sn+6, with r=3+2√2 and s=3-2√2, (hope i got that right)

and see what can be done over Q(√2).
dodo
dodo is offline
#7
Feb16-12, 03:37 AM
P: 688
Quote Quote by Norwegian View Post
[...] one could try to use the closed form expression for S(n)

4S(n) = rn+sn+6, with r=3+2√2 and s=3-2√2, (hope i got that right)

and see what can be done over Q(√2).
I was scribbling earlier in that direction, and (in my pre-grade ignorance) I only got as far as
[tex]\begin{align*}
S(n) &= \frac {(3+2\sqrt 2)^n + (3-2\sqrt 2)^n} 4 + \frac 3 2 \\
&= \frac {\left( \sum_{k=0}^{\lfloor\frac n 2\rfloor} \binom n {2k} 3^{n-2k} 8^k \right) + 3} 2 \\
&= \frac {3^n + 8m + 3} 2 \quad,\quad {\scriptsize \mbox{ for some integer }m}\end{align*}[/tex]
From "empirical evidence" I was hoping to find something related to the quadratic nature of 2 mod p, as S((p-1)/2) appears to be divisible by p (I think) for primes p of the form 8ką3. But to no avail yet.
ramsey2879
ramsey2879 is offline
#8
Feb16-12, 10:58 AM
P: 891
Quote Quote by Norwegian View Post
Hi,

I find this interesting, and want to look into what is going on here. Myfirst thougt was about the name Ramsey, have you just named the primes after yourself, or is there some other connection? Then where did the test sequence come from? Did you try all sequences, or did you see that this particular one had some good properties. To prove your claim, if true, one could try to use the closed form expression for S(n)

4S(n) = rn+sn+6, with r=3+2√2 and s=3-2√2, (hope i got that right)

and see what can be done over Q(√2).
I did name the primes after myself, but after seeing Dodo's comment that the primes are of the form 8n +/- 3, I would see no purpose in naming them if all primes of this form met the test. As to how I found this particular sequence, one could look at all my posts in the Triangular and Fibonicci Numbers Group in Yahoo that I set up. One of the earliest is http://tech.groups.yahoo.com/group/T...bers/message/6. As one can see recursive series of the form S(n) = 6S(n-1) - S(n-2) + K often play an important role in the posts on triangular numbers that I made. I often tried writing out these sequences in mod form since early on I had noted some interesting facts about products, these types of series, and triangular numbers. Just happened to notice the relationship with primes and the Test series very recently. Nothing specific caused me to go there.
Your direct formula agrees with my data and the formula posted for OEIS A001541 and A003499 so I believe you are right. I am not very well versed in number theory and I often make careless errors, so I appreciate your post.
Followup, in the range 349049001-349049500, primes 349049123 and 349049227 which are of the form 8n +/- 3 (two such primes out of 12) do not pass my prime test, so I guess we may as well name the group of primes that do pass the test "Ramsey Primes"
dodo
dodo is offline
#9
Feb16-12, 12:55 PM
P: 688
Quote Quote by ramsey2879 View Post
[...] but after seeing Dodo's comment that the primes are of the form 8n +/- 3, I would see no purpose in naming them if all primes of this form met the test.
Not all the primes of the form 8ną3 would pass your test - some (like 29) will have zeroes in the sequence before S((p-1)/2). (Besides, I don't have a proof of that.)


Register to reply

Related Discussions
Ramsey spectroscopy Atomic, Solid State, Comp. Physics 2
Ramsey Number. Set Theory, Logic, Probability, Statistics 3
Pythagorean Primes and Gaussian Primes, divisibility question Linear & Abstract Algebra 3
Ramsey's theorem help..~ Engineering, Comp Sci, & Technology Homework 0
Ramsey 2879 Linear & Abstract Algebra 0