 mersenneforum.org > Math Primes of the form a^(2^n)+b^(2^n)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2012-03-30, 11:37 #1 YuL   Feb 2012 Paris, France 7·23 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 33×347 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

236110 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

7·23 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 101000012 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 638310 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

307410 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...
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.   2012-03-30, 18:37 #9 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 24AD16 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

2418 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).   Thread Tools Show Printable Version Email this Page 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 05:00.

Wed Apr 14 05:00:34 UTC 2021 up 5 days, 23:41, 0 users, load averages: 2.09, 2.69, 2.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.