View Single Post
Old 2011-03-10, 23:42   #6
zerothbase
 
Mar 2011

10102 Posts
Default

Below are the liars under signed int (2^31-1) for 11000544, 31481107, using the code in the attached java file.

Having no liars up to a high value is a generally a good indicator that it has few liars beyond that. But I wasn't really searching for "fewest Liars under 2^31". For example, there could be a pair that fails to see that 25 is composite (which my search would filter out immediately), but might have very few liars other than this up to a large value.

Since this list is relatively short, it provide a fairly fast way to see if a number < 2^31 is prime:
1) If it is in the list, then it is composite.
2) Else return miller_rabin(value, [11000544, 31481107])

Though certainly not as fast as Worley's http://www.mersenneforum.org/showthread.php?p=182647, which only uses 1 miller rabin and a quick hash of the number.

316349281, 346305403, 368113411, 464305843, 478614067, 545738203, 574870753,
656824033, 659830621, 670567301, 688360333, 807115753, 808562791, 855073301,
903136901, 939369001, 970355431, 970560533, 972471151, 977770531, 1032101461,
1092902533, 1101623381, 1138289041, 1142300503, 1250656621, 1261099531,
1266482017, 1397169091, 1414892161, 1487387611, 1515175087, 1611615151,
1618435171, 1671276601, 1671603667, 1728960133, 1789167931, 1804182257,
1966146451, 1970097001, 1991063449, 2147022749
Attached Files
File Type: txt sprpLiars.java.txt (1.7 KB, 268 views)
zerothbase is offline   Reply With Quote