Ramsey Primes

ramsey2879

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?

ramsey2879

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

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

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

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

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) = rⁿ+sⁿ+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

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

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

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.)