MathGroup Archive 2012

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

Search the Archive

Re: Need help with prime Test

  • To: mathgroup at smc.vnet.net
  • Subject: [mg124921] Re: Need help with prime Test
  • From: "Oleksandr Rasputinov" <oleksandr_rasputinov at ymail.com>
  • Date: Sun, 12 Feb 2012 05:03:05 -0500 (EST)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • References: <jh6kd9$jsp$1@smc.vnet.net>

On Sat, 11 Feb 2012 20:51:53 -0000, KenR <ramsey2879 at msn.com> 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. http://mathworld.wolfram.com/RamseyNumber.html).  
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.

803837457453639491257079614341942108138837688287558145837488917\
522297427376533365218650233616396004545791504202360320876656996\
676098728404396540823292873879185086916685732826776177102938969\
773947016708230428687109997439976544144845341155872450633409279\
022275296229414984230688168540432645753401832978611129896064484\
5216191652872597534901

(a strong pseudoprime to all prime bases less than 200, from  
http://www.trnicely.net/misc/mpzspsp.html#MB)

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