mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2009-08-17, 03:55   #1
Carl Fischbach
 
Carl Fischbach's Avatar
 
Oct 2007

2×17 Posts
Default 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.
Carl Fischbach is offline   Reply With Quote
Old 2009-08-17, 04:26   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

25·173 Posts
Default

Quote:
Originally Posted by Carl Fischbach View Post
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.
retina is offline   Reply With Quote
Old 2009-08-17, 04:34   #3
axn
 
axn's Avatar
 
Jun 2003

23·3·193 Posts
Default

Stop calling primes named after other people by your own name!
axn is offline   Reply With Quote
Old 2009-08-17, 04:39   #4
Carl Fischbach
 
Carl Fischbach's Avatar
 
Oct 2007

2×17 Posts
Default

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.
Carl Fischbach is offline   Reply With Quote
Old 2009-08-17, 04:39   #5
flouran
 
flouran's Avatar
 
Dec 2008

15018 Posts
Default

Quote:
Originally Posted by axn View Post
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
flouran is offline   Reply With Quote
Old 2009-08-17, 04:58   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

126408 Posts
Default

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.
retina is offline   Reply With Quote
Old 2009-08-17, 05:20   #7
Carl Fischbach
 
Carl Fischbach's Avatar
 
Oct 2007

3410 Posts
Default

I'm not making any claims beyond what Iv'e tested, the proof you want
is beyond my scope.
Carl Fischbach is offline   Reply With Quote
Old 2009-08-17, 05:22   #8
flouran
 
flouran's Avatar
 
Dec 2008

72·17 Posts
Default

Quote:
Originally Posted by Carl Fischbach View Post
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
flouran is offline   Reply With Quote
Old 2009-08-17, 05:43   #9
Carl Fischbach
 
Carl Fischbach's Avatar
 
Oct 2007

2·17 Posts
Default

Iv'e reinvented the wheel again, I was totally unfamiliar with the wagstaff
prime I'm half asleep here.
Carl Fischbach is offline   Reply With Quote
Old 2009-08-17, 06:34   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100000000101012 Posts
Default

Where is Dr. Bob when you need him?
Uncwilly is online now   Reply With Quote
Old 2009-08-17, 06:48   #11
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

54108 Posts
Default

other primes (2^n+1)/3 for n=
61, 79, 101, 127, 167, 191, 199, 313, 347 (limit n=500)

see here
kar_bon is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
Large Prime Variation of QS Sam Kennedy Factoring 9 2012-12-18 17:30
Integral Variation flouran Information & Answers 6 2009-07-20 20:00
Fischbach Representations. Mr. P-1 Puzzles 5 2007-10-10 16:16
Variation on a Martin Gardner puzzle 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.