mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-03-30, 11:37   #1
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

5×31 Posts
Default Primes of the form a^(2^n)+b^(2^n)

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
Code:
> 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?

Last fiddled with by YuL on 2012-03-30 at 12:01
YuL is offline   Reply With Quote
Old 2012-03-30, 12:51   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×3×739 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2012-03-30, 12:52   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by YuL View Post
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.
wblipp is offline   Reply With Quote
Old 2012-03-30, 13:11   #4
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

5·31 Posts
Default

Quote:
Originally Posted by LaurV View Post
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)
>>

Last fiddled with by YuL on 2012-03-30 at 13:13
YuL is offline   Reply With Quote
Old 2012-03-30, 13:31   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by YuL View Post
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.

Last fiddled with by R.D. Silverman on 2012-03-30 at 13:31
R.D. Silverman is offline   Reply With Quote
Old 2012-03-30, 15:26   #6
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

5×31 Posts
Default

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...
YuL is offline   Reply With Quote
Old 2012-03-30, 15:55   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·29·109 Posts
Default

These look rather random numbers; are they the smallest values of a+b with a^2048+b^2048 prime or something?
fivemack is offline   Reply With Quote
Old 2012-03-30, 18:29   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

56278 Posts
Default

Quote:
Originally Posted by YuL View Post
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.
ATH is offline   Reply With Quote
Old 2012-03-30, 18:37   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×33×132 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2012-03-30, 19:07   #10
literka
 
literka's Avatar
 
Mar 2010

2468 Posts
Default

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

Last fiddled with by literka on 2012-03-30 at 19:07
literka is offline   Reply With Quote
Old 2012-03-30, 20:12   #11
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

5·31 Posts
Default

Quote:
Originally Posted by fivemack View Post
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).
YuL is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primes of the form (b+-1)*b^n+-1 and b^n+-(b+-1) sweety439 sweety439 162 2020-05-15 18:33
Search primes of form 2*n^n ± 1 JeppeSN And now for something completely different 27 2018-04-12 14:20
Primes of the form n+-phi(n) carpetpool carpetpool 3 2017-01-26 01:29
Infinitely many primes of a form? PawnProver44 Homework Help 1 2016-03-15 22:39
Primes of the form 2.3^n+1 Dougy Math 8 2009-09-03 02:44

All times are UTC. The time now is 14:12.

Sun Oct 25 14:12:38 UTC 2020 up 45 days, 11:23, 1 user, load averages: 1.51, 1.53, 1.58

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.