Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #8473 > unrolled thread
| Started by | KenR <ramsey2879@msn.com> |
|---|---|
| First post | 2012-02-11 20:51 +0000 |
| Last post | 2012-02-19 11:35 +0000 |
| Articles | 3 — 3 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
Need help with prime Test KenR <ramsey2879@msn.com> - 2012-02-11 20:51 +0000
Re: Need help with prime Test "Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com> - 2012-02-12 10:05 +0000
Re: Need help with prime Test David Bailey <dave@removedbailey.co.uk> - 2012-02-19 11:35 +0000
| From | KenR <ramsey2879@msn.com> |
|---|---|
| Date | 2012-02-11 20:51 +0000 |
| Subject | Need help with prime Test |
| Message-ID | <jh6kd9$jsp$1@smc.vnet.net> |
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).
[toc] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com> |
|---|---|
| Date | 2012-02-12 10:05 +0000 |
| Message-ID | <jh82u0$okf$1@smc.vnet.net> |
| In reply to | #8473 |
On Sat, 11 Feb 2012 20:51:53 -0000, KenR <ramsey2879@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.
[toc] | [prev] | [next] | [standalone]
| From | David Bailey <dave@removedbailey.co.uk> |
|---|---|
| Date | 2012-02-19 11:35 +0000 |
| Message-ID | <jhqmpu$fbc$1@smc.vnet.net> |
| In reply to | #8473 |
On 11/02/2012 20:51, KenR 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). > > Using Do and While loops, tends to be frowned upon by some purists, but I think they are a good way to take a first stab at many problems. To exit a Do or While loop on some condition, use If[condition,Break[]]; If you want to exit multiple layers of loops, and/or function calls, use Catch/Throw. These are inefficient if used, but if you are going to execute them at most once, there is no problem. David Bailey http://www.dbaileyconsultancy.co.uk
[toc] | [prev] | [standalone]
Back to top | Article view | comp.soft-sys.math.mathematica
csiph-web