MathGroup Archive 2012

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Need help with prime Test

  • To: mathgroup at
  • Subject: [mg124921] Re: Need help with prime Test
  • From: "Oleksandr Rasputinov" <oleksandr_rasputinov at>
  • Date: Sun, 12 Feb 2012 05:03:05 -0500 (EST)
  • Delivered-to:
  • References: <jh6kd9$jsp$>

On Sat, 11 Feb 2012 20:51:53 -0000, KenR <ramsey2879 at> wrote:

> I need to generate more "Ramsey" Numbers to further verify that only
> prime numbers can meet the criteria. Ramsey numbers are those
> generated from a simple criteria that is easy to check. I imported a
> CSV list into my Mathematica version 8 to check all 30,759 numbers
> that my Excel macro selected and they all turned out to be prime. That
> is all that my program selected from all odd numbers from 3 to
> 1,048,655, as large as my Excel program could test. I would further
> test my program using my Mathematica software but I would like some
> help to write the most efficient program to do the job.  Right now, I
> am trying to write a while loop inside a do loop but don't know how to
> exit the loop before the counter becomes 0 in the case that it is
> clear that P is not prime.
> The check is to do the following binary recursive sequence mod P and
> check to see that the (P-1)/2 term is zero and no term prior to that
> is zero. If so then I believe P should be prime based upon the results
> so far.
> The test sequence is S(0) = 2, S(1) = 3, S(n) = 6*S(n-1) - S(n-2) - 6.
> It appears that S((P-1)/2) is divisible by P then P is very likely
> Prime, 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 about 1/3 of the primes seem to meet the more
> restricted criteria, i.e. the sequence has no term divisible by P
> prior to S((P-1)/2).

I assume that your Ramsey numbers are not the same as those usually going  
by that name (see e.g.  
Otherwise, finding such numbers is an unsolved problem in itself (although  
in general they are not prime). As regards the primality test, I would  
suggest using Mathematica's built-in primality test (the function PrimeQ).  
However, as stated in the documentation,

"PrimeQ first tests for divisibility using small primes, then uses the  
Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a  
Lucas test. As of 1997, this procedure is known to be correct only for n <  
10^16, and it is conceivable that for larger n it could claim a composite  
number to be prime."

To this I would add that no counterexamples are currently known (e.g.


(a strong pseudoprime to all prime bases less than 200, from

doesn't fool PrimeQ). However, if you encounter numbers larger than 10^16  
that are apparently prime and need to be completely certain of it, you can  
use the function ProvablePrimeQ from the PrimalityProving` package.

  • Prev by Date: Re: Abort computation on any message
  • Next by Date: Re: Some assistance from seasoned users.
  • Previous by thread: Need help with prime Test
  • Next by thread: Re: Need help with prime Test