mersenneforum.org Assuming the goal is mega-primes, is base-3 better
 Register FAQ Search Today's Posts Mark Forums Read

 2008-12-26, 08:30 #1 jasong     "Jason Goatcher" Mar 2005 66638 Posts Assuming the goal is mega-primes, is base-3 better I'm running the base-3 challenge at the moment, just for the heck of it, and it's amazing how dense it is with primes. I know that for a given k and n, base-2 is the fastest to run. But if a person's goal is simply to "find big-ass primes," would it not be better to concentrate on base-3? I mean, think about it. ALL primes, except 2 and 3, are of the form 6k+/-1. And when k is even and b is 3, those are the ONLY numbers you get.(yes, I realize 6k+/-1 is a necessary but not sufficent condition) I think this is something that needs to be seriously considered.
2008-12-26, 10:19   #2
axn

Jun 2003

149B16 Posts

Quote:
 Originally Posted by jasong I know that for a given k and n, base-2 is the fastest to run. But if a person's goal is simply to "find big-ass primes," would it not be better to concentrate on base-3?
A small correction. It is not just "for a given k and n" -- it is "for a given number of approximately same size". That is to say, if N=k*2^n and M=k*3^m are approximately same number of digits, then the base-2 number will be much faster than the base-3 number because of the current state-of-the-art in FFT (i.e IBDWT which is only implemented for base-2).

In addition, the base 3 series grows faster than the base-2 series.

Quote:
 Originally Posted by jasong I mean, think about it. ALL primes, except 2 and 3, are of the form 6k+/-1. And when k is even and b is 3, those are the ONLY numbers you get.
This works equally well for base-2, all it needs is k be a multiple of 3. In fact, that is the key principle behind the heavy weight k's being used by 15K and RPS projects. So this is not an important consideration.

 Similar Threads Thread Thread Starter Forum Replies Last Post Joe O Sierpinski/Riesel Base 5 5 2016-08-21 17:47 Joe O Sierpinski/Riesel Base 5 1 2016-03-14 04:30 odicin Sierpinski/Riesel Base 5 16 2013-01-09 20:18 Joe O Sierpinski/Riesel Base 5 36 2010-12-31 04:05 gd_barnes Sierpinski/Riesel Base 5 2 2008-07-01 04:09

All times are UTC. The time now is 05:49.

Thu Jan 27 05:49:11 UTC 2022 up 188 days, 18 mins, 1 user, load averages: 1.52, 1.62, 1.65