Primes of the form a^(2^n)+b^(2^n)

[YuL]

Let's consider numbers of the form a^(2^n)+b^(2^n)
where (a,b) is a couple of integers such that a>b>1 and gcd(a,b)=1
and n integer >= 1.
Is there a primality test which could be applied to such numbers?
I've done a search on the internet but I did not find an answer, I was able
to get my hands on a paper by Anders Björn and Hans Riesel but it
only deals with factors of such number (for a,b <= 12).

Example: 150^2048+7^2048 is PRP

> pfgw64 -f -q"150^2048+7^2048"
PFGW Version 3.6.2.64BIT.20120309.Win_Dev [GWNUM 27.4]

150^2048+7^2048 is 3-PRP! (1.5978s+0.3911s)

It took primo 39h (primo 4.0.0.alpha14, Intel Core 2 Duo E6600, 4 tasks)
to produce a primality certificate for that 4457 digits number.
Was it the only way I can prove the number prime?
Has anybody out there been interested in this form of numbers?

[LaurV]

Isn't this a subset of GF(a,b)? And you wouldn't need to go so high to make the point: 3^2+2^2=13, prime, 2^4+3^4=97 prime, etc.

[wblipp]

Originally Posted by YuL

Let's consider numbers of the form a^(2^n)+b^(2^n)
where (a,b) is a couple of integers such that a>b>1 and gcd(a,b)=1
and n integer >= 1.

Note that for n=1 you have all primes that are 1 mod 4. That makes it unlikely you will find a powerful primality test.

[YuL]

Originally Posted by LaurV

Isn't this a subset of GF(a,b)? And you wouldn't need to go so high to make the point: 3^2+2^2=13, prime, 2^4+3^4=97 prime, etc.

Yes, quoted from here:
<<
There are two different definitions of generalized Fermat numbers, one of which is more general than the other. Ribenboim (1996, pp. 89 and 359-360) defines a generalized Fermat number as a number of the form a^(2^n)+1 with a>2, while Riesel (1994) further generalizes, defining it to be a number of the form a^(2^n)+b^(2^n)
>>

[R.D. Silverman]

Originally Posted by YuL

Let's consider numbers of the form a^(2^n)+b^(2^n)
where (a,b) is a couple of integers such that a>b>1 and gcd(a,b)=1
and n integer >= 1.
Is there a primality test which could be applied to such numbers?

AKS, APR-CL, ECPP come to mind.

[YuL]

OK, so this basically confirms that ECPP using Primo is the way to go, I've already proven a few:
8100^1024+203^1024
78^2048+41^2048
150^2048+7^2048
53^4096+2^4096

but 72^8192+43^8192 is 15216 digits long, I wonder how long would it take to produce the certificate, based on the ones I have already done I estimated it would take 4 months, I'm still thinking whether I will start the fight against that behemoth...

[fivemack]

These look rather random numbers; are they the smallest values of a+b with a^2048+b^2048 prime or something?

[ATH]

Originally Posted by YuL

but 72^8192+43^8192 is 15216 digits long, I wonder how long would it take to produce the certificate, based on the ones I have already done I estimated it would take 4 months, I'm still thinking whether I will start the fight against that behemoth...

Look in this (long) thread:

http://www.mersenneforum.org/showthread.php?t=10761

Cybertronic seems like an expert on Primo, but he is not just starting it and letting it run, he is doing it a lot of manual work running one primo on each core and then combining the proof somehow, which he tries to explain in that thread.

He did 11,467 digits in 5months and 8,724 digits in 1030hours ~ 43 days, and he says runtime follows digits^3.75, so 15,216 should be like 14-15months, and he also estimates 17,000 digits at 18months.

[Batalov]

Primo on linux is already doing all the Luhn-ification on N threads. No need for manual interventions anymore.

Also, consider all already known GFNs (e.g. http://www.primenumbers.net/prptop/s...096%2Bb%5E4096 off the top of my head ...and there are other sites, of course) before searching for more of these PRPs.

[literka]

Of course, every prime factor of a Fermat number is of the form a^2+b^2. So, for n=1.
I know only one factor of a Fermat number of the form a^4+b^4 (i.e. for n=2). It is 641=5^4+2^4 - factor of F5.
I know only one prime factor of Fermat number of the form a^4+b^2. Factor of F18:
13631489=5^4+3692^2

[YuL]

Originally Posted by fivemack

These look rather random numbers; are they the smallest values of a+b with a^2048+b^2048 prime or something?

I listed them of the top of my head, but I am almost sure that
- for n=11 the smallest prime is 22^2048+3^2048<2750 digits> the next one being 43^2048+2^2048<3346 digits>
- for n=11 the smallest prime such that either a or b =7 is 150^2048+7^2048<4457 digits>
- for n=12 the smallest prime is 53^4096+2^4096<7063 digits>
and (surprisingly) the next one also has a=53: 53^4096+48^4096<7063 digits> (actually the latter is PRP and the ECPP proof is in progress).