mersenneforum.org > Math Primes of the form a^(2^n)+b^(2^n)
 Register FAQ Search Today's Posts Mark Forums Read

 2012-03-30, 11:37 #1 YuL     Feb 2012 Paris, France 5×31 Posts 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
 2012-03-30, 12:51 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 2·13·337 Posts 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.
2012-03-30, 12:52   #3
wblipp

"William"
May 2003
New Haven

2·32·131 Posts

Quote:
 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.

2012-03-30, 13:11   #4
YuL

Feb 2012
Paris, France

9B16 Posts

Quote:
 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)
>>

Last fiddled with by YuL on 2012-03-30 at 13:13

2012-03-30, 13:31   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.

Last fiddled with by R.D. Silverman on 2012-03-30 at 13:31

 2012-03-30, 15:26 #6 YuL     Feb 2012 Paris, France 100110112 Posts 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...
 2012-03-30, 15:55 #7 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2·3,181 Posts These look rather random numbers; are they the smallest values of a+b with a^2048+b^2048 prime or something?
2012-03-30, 18:29   #8
ATH
Einyen

Dec 2003
Denmark

56008 Posts

Quote:
 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...

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.

 2012-03-30, 18:37 #9 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,127 Posts 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.
 2012-03-30, 19:07 #10 literka     Mar 2010 26·3 Posts 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
2012-03-30, 20:12   #11
YuL

Feb 2012
Paris, France

9B16 Posts

Quote:
 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).

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 162 2020-05-15 18:33 JeppeSN And now for something completely different 27 2018-04-12 14:20 carpetpool carpetpool 3 2017-01-26 01:29 PawnProver44 Homework Help 1 2016-03-15 22:39 Dougy Math 8 2009-09-03 02:44

All times are UTC. The time now is 17:16.

Thu Oct 1 17:16:49 UTC 2020 up 21 days, 14:27, 0 users, load averages: 1.52, 1.72, 1.67