idea about 10 million digit search(possibly dumb)

[jasong]

A while back I did a little math involving numbers involving exponents that are 2^n where n is a whole number. There was a webpage that gave the approximate time to test a number b^(2^n)+/-1, and I noticed, compared to other projects, as the number of digits increased the length of the test didn't increase as quickly. This got me to thinking about alternative ways of generating possible primes in less time.

Has anyone done any serious experimention(I apologize if this is seen as a conceited question) with the equation k*b^n+/-c to try and find a pattern that's faster than, say, 2^n-1 for numbers more than 10 million digits? Also, why is it all '-' 1 in the main search for primes? I know it's "Mersenne" forum, meaning 2^n-1, but how high has 2^n+1 gotten?

Sorry if these questions seem impertinent, but I thought I'd ask.

[Citrix]

There are 2 forms of 2^n+1

(2^n+1)/3 --> Has not gone very far yet. Alex (akruppa) is trying to prove some primes.

for the Gaussian mersenne, you should contact Jean Penne, he is sieving such numbers right now. According to the top 5000 primes database, this has been tested to 2^1000000+1.

[xilman]

Originally Posted by jasong

Also, why is it all '-' 1 in the main search for primes? I know it's "Mersenne" forum, meaning 2^n-1, but how high has 2^n+1 gotten?

It is straightforward to show that if 2^n+1 is prime, n must be a power of 2.

The Fermat numbers, F_n = 2^2[sup]n[/sup]+1, are prime for n=0 through 4 inclusive and composite as far as n=32. Many others with n>32 are known to be composite and it's generally believed that no more are prime.

Note that the smallest Fermat number which is unknown whether it is prime or composite is F₃₃. This number is much larger than the smallest uncharacterized Mersenne number. It has over two billion digits.


Paul

[Citrix]

Originally Posted by xilman

It is straightforward to show that if 2^n+1 is prime, n must be a power of 2.

The Fermat numbers, F_n = 2^2[sup]n[/sup]+1, are prime for n=0 through 4 inclusive and composite as far as n=32. Many others with n>32 are known to be composite and it's generally believed that no more are prime.

Note that the smallest Fermat number which is unknown whether it is prime or composite is F₃₃. This number is much larger than the smallest uncharacterized Mersenne number. It has over two billion digits.


Paul

There is also generalized fermats on the +1 side, to which you can contribute.

But nothing is as fast as mersenne numbers to test, because of George Woltan's Coding skills and because of special properties of mersenne numbers.

There are also Cullen numbers to which you can contribute if you like but they are of the form n*2^n+1.

[ewmayer]

Originally Posted by Citrix

But nothing is as fast as mersenne numbers to test, because of George Woltan's Coding skills and because of special properties of mersenne numbers.

Actually, using a given FFT-based big-integer multiply implementation, Fermat number testing will generally be a tad faster - I typically see timings around 10-15% faster than for a similar-sized Mersenne using my own code, which uses the same underlying FFT code for both classes of number. The reason is the the Fermat-mod DWT-based multiply has a simpler structure, which leads to appreciably less work to do in the round-and-carry phase and the dyadic multiply that takes place between the forward and inverse FFTs (more on the latter below). Of course both the round-and-carry and dyadic-mul steps are O(N) operations whereas the FFT is O(N*log N) so one would expect this speedup to asymptotically approach zero as the numbers get large, but interestingly, in practice I've not observed that to be the case

I think this may be due to the fact that the Fermat-mod FFT dyadic multiply step is cache-friendlier, since when doing Fermat-mod DWT one can structure things as a right-angle transform so as to use a genuine complex FFT, rather than a complex/real FFT as required for Mersenne-mod, which needs additional complex/real wrapper operations surrounding the dyadic multiply step. Like the carry step these complex/real wrappers are formally O(N), but they involve (j, N-j) index pair correlations which are very difficult to implement in a cache-friendly manner. I believe it's the less-nice cache behavior that is responsible for the aforementioned speed difference persisting even at very large runlengths.

But one could say that no other class if numbers is significantly faster to test than the Mersennes, and certainly there is none that is asymptotically faster.

[biwema]

After passing ~M38000000 it is more efficient to find 10M digits primes of the form k*2^n+1 or k*2^n-1 (Riesel, Sierpinski, also proth searches with the same exponent and variable mantissa (fatser sieving)).

There is also a huge range of Gerneral Fermat numbers (as Ernst suggested) with slightly more than 10M digits.
Starting around
3441463500^1048576 +1 or
11843670820000000000^524288 +1
gives many candidates with exactly 10 Million digits.