mersenneforum.org The Fischbach Prime a mersenne variation
 Register FAQ Search Today's Posts Mark Forums Read

 2009-08-17, 03:55 #1 Carl Fischbach     Oct 2007 2×17 Posts The Fischbach Prime a mersenne variation Iv'e come up with a prime number generator that seems to generate large primes, as far as I can test with a slightly greater effeciency than the mersenne equation can. Here's the equation (2^prime +1)/3= possibly prime Here's a side by side test between the Fischbach prime and the mersennne prime The mersenne prime is prime when 2 is raised to the following powers, 2,3,5,7,13,17,19,31,or 61. The Fischbach prime is prime when 2 is raised to the following powers,3,5,7,11,13,17,19,23,31,or 43. You people seem to be so clever on this forum why don't you come up with a system to test the Fischbach prime for primality and generate a prize winning prime and take the money to the bank.
2009-08-17, 04:26   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

25·173 Posts

Quote:
 Originally Posted by Carl Fischbach Iv'e come up with a prime number generator that seems to generate large primes, as far as I can test with a slightly greater effeciency than the mersenne equation can. Here's the equation (2^prime +1)/3= possibly prime Here's a side by side test between the Fischbach prime and the mersennne prime The mersenne prime is prime when 2 is raised to the following powers, 2,3,5,7,13,17,19,31,or 61. The Fischbach prime is prime when 2 is raised to the following powers,3,5,7,11,13,17,19,23,31,or 43. You people seem to be so clever on this forum why don't you come up with a system to test the Fischbach prime for primality and generate a prize winning prime and take the money to the bank.
Wow, so for all numbers n<=61, countof(Mersenne primes)=9 and countof(Fischbach primes)=10.

And that is significant because ... ?

What about for n<=1million? What is the ratio?

Is a "Fischbach prime" test more (or even as) efficient as a Mersenne prime test? If not and the test takes 10 times longer then can we expect a corresponding 10+ times increase in the number of primes found?

Last fiddled with by retina on 2009-08-17 at 04:34 Reason: than ----> then, stupid mistake.

 2009-08-17, 04:34 #3 axn     Jun 2003 23·3·193 Posts Stop calling primes named after other people by your own name!
 2009-08-17, 04:39 #4 Carl Fischbach     Oct 2007 2×17 Posts The mersenne prime has shortcuts for testing primality I looked at my equation for shortcuts for primality testing and couldn't find any, someone else may have some better luck, it's a lucrative proposition if you find them.
2009-08-17, 04:39   #5
flouran

Dec 2008

15018 Posts

Quote:
 Originally Posted by axn Stop calling primes named after other people by your own name!
ECPP is the fastest test for proving the primality of the Wagstaff ("Fischbach") prime (according to Wikipedia). That's a run-time of O(log^5 n) right? The LL test (with FFT) has a run-time of O(log^2 n log log n) when testing the primality of a Mersenne number n? Of course, I might/will be wrong with some of this information since I am not an expert in compuational number theory.
So I doubt anyone can come up with a primality test to prove the primality of Wagstaff ("Fischbach") primes that cuts the run-time by a poly-logarithmic factor. Of course, a probable primality test may suffice. Miller-Rabin has a run-time of $\tilde{O}(\log^2 n)$ with a probability of error at most of 1/4 per iteration. Grantham's RQFT cuts this probability of error down to at most 1/7710 per iteration. Zhang's One Parameter Quadratic Base Test (a variant of the BPSW test) runs in about the same time (see his paper "A One Parameter Quadratic-Base Version of the Baillie-PSW Probable Prime Test") and has a much less probability of error than RQFT.

A TRIVIAL probable prime test which has a much lower probability of error than either RQFT and OPQBT that runs in $\tilde{O}(k \log^2 n)$ time, where k=7 in the worst possible case, is by executing 1 iteration in RQFT followed by 1 iteration in OPQBT. I have attached a pdf file describing this RQFT+OPQBT test (I wrote it a couple months ago just for fun). It also talks more about Zhang's OPQBT in a bit more detail:
Trivial_Probabilistic_Primality_Test.pdf
P.S. I use the term "Selfridge" in this pdf, as it is a term coined and popularized by Jon Grantham which refers to the run-time of the Miller-Rabin test (in other words, $\tilde{O}(\log^2 n)$).
Comments are more than welcome regarding the pdf file I attached.

Last fiddled with by flouran on 2009-08-17 at 05:30

 2009-08-17, 04:58 #6 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 126408 Posts Aww, you guys all gave the game away so early. I wanted Carl Fischbach to see if he could find the Wagstaff primes below 1million by himself, hence my question about the ratio for n<=1million.
 2009-08-17, 05:20 #7 Carl Fischbach     Oct 2007 3410 Posts I'm not making any claims beyond what Iv'e tested, the proof you want is beyond my scope.
2009-08-17, 05:22   #8
flouran

Dec 2008

72·17 Posts

Quote:
 Originally Posted by Carl Fischbach I'm not making any claims beyond what Iv'e tested, the proof you want is beyond my scope.
Carl Fischbach,

Please look at my post; it is meant to be of help to you (I hope so at least): http://mersenneforum.org/showpost.ph...94&postcount=5

Kind Regards,
flouran

Last fiddled with by flouran on 2009-08-17 at 05:26

 2009-08-17, 05:43 #9 Carl Fischbach     Oct 2007 2·17 Posts Iv'e reinvented the wheel again, I was totally unfamiliar with the wagstaff prime I'm half asleep here.
 2009-08-17, 06:34 #10 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 100000000101012 Posts Where is Dr. Bob when you need him?
 2009-08-17, 06:48 #11 kar_bon     Mar 2006 Germany 54108 Posts other primes (2^n+1)/3 for n= 61, 79, 101, 127, 167, 191, 199, 313, 347 (limit n=500) see here

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 2 2016-05-06 08:13 Sam Kennedy Factoring 9 2012-12-18 17:30 flouran Information & Answers 6 2009-07-20 20:00 Mr. P-1 Puzzles 5 2007-10-10 16:16 grandpascorpion Puzzles 20 2007-07-15 15:11

All times are UTC. The time now is 22:04.

Thu Jul 9 22:04:26 UTC 2020 up 106 days, 19:37, 0 users, load averages: 0.99, 1.19, 1.34