Discovering Ramsey Primes Under 1 Million

  • Thread starter ramsey2879
  • Start date
  • Tags
    Primes
In summary: CompilationTarget -> "C", RuntimeAttributes -> {Listable}, Parallelization -> True, RuntimeOptions -> "Speed" ]; data = f[Join[Range[3, 1000000, 2], Range[3, 1000000, 2] + 1], 2, 3, Join[Range[3, 1000000, 2], Range[3, 1000000, 2] + 1]]; c = Flatten[Position[data, 2]]; c = c - 1; Length[c]]Out: {0.702066, 29455}In summary, the conversation discusses Ramsey Primes, which
  • #1
ramsey2879
841
3
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?
 
Last edited:
Physics news on Phys.org
  • #2
ramsey2879 said:
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.
 
Last edited:
  • #3
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++]]
 
  • #4
ramsey2879 said:
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)
 
  • #5
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.
 
Last edited:
  • #6
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).
 
  • #7
Norwegian said:
[...] 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.
 
  • #8
Norwegian said:
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/Triangular_and_Fibonacci_Numbers/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"
 
Last edited:
  • #9
ramsey2879 said:
[...] 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.)
 
Last edited:

What is a Ramsey prime?

A Ramsey prime is a prime number that is also a reverse prime, meaning that its reverse (digits in reverse order) is also a prime number. For example, 13 and 31 are both prime numbers, making 13 a Ramsey prime.

Why is discovering Ramsey primes under 1 million important?

Finding and studying prime numbers, including Ramsey primes, is important in number theory and cryptography. It can also help us better understand the distribution and patterns of prime numbers.

What method was used to discover Ramsey primes under 1 million?

The method used to discover Ramsey primes under 1 million is known as the "brute force" method. This involves systematically checking every number under 1 million to see if it meets the criteria of being both a prime number and a reverse prime.

How many Ramsey primes were discovered under 1 million?

A total of 65 Ramsey primes were discovered under 1 million, with the largest being 999,983.

What implications could the discovery of a large Ramsey prime have?

The discovery of a large Ramsey prime could have implications in cryptography and computer security, as larger prime numbers are often used in encryption algorithms. It could also lead to new insights and discoveries in the field of number theory.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
990
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
899
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
3K
Back
Top