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: firstname.lastname@example.org
- References: <email@example.com>
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.
(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