20180320, 16:24  #67 
Feb 2017
Nowhere
1011111001100_{2} Posts 
I looked at the exponent e = 2^14. Rather than compute the gcd's of pairs of numbers a^e + b^e  which would have been a godawful amount of computation  I did the following: I used my list of primes p == 1 (mod 2^15) up to 2^26, and went through all the pairs [a,b] with a < b, a+b odd, gcd(a,b) = 1, and b < 201. For each prime p, I simply counted the number of pairs for which a^e + b^e was divisible by p (employing Batalov's b/a trick). This took seconds, not minutes.
What I found was, the first prime on my list, p = 65537, divided over 2,000 of the numbers a^e + b^e  nearly a quarter of them. The number of a^e + b^e divisible by p decreased rapidly with p, but IIRC was at least 2 for the first 120 primes on the list, at least 3 for the first 103 primes on the list, and at least 4 for the first 63 primes on the list. 
20180321, 14:26  #68  
Feb 2017
Nowhere
2^{2}×1,523 Posts 
Once upon a time, long long ago  here in fact  I posted the following ineptlywritten script, along with its running time:
Quote:
? k=1;v=vector(s);f=0;for(j=2,200,forstep(i=f+1,j1,2,if(gcd(i,j)==1,v[k]=[i,j];k++));f=!f) time = 23 ms. Half the steps, half the time... For e = 2^14 I also looked at how many p == 1 (mod 2*e), p < 2^26, divide the numbers a^e + b^e. The champion pair was (116,127); 116^e + 127^e is divisible by 65537, 1146881, 1179649, 17367041, and 46497793. 

20180322, 18:15  #70 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·1,997 Posts 
a(17) > 412
and sieved to a<=600 up to 52 bits (and higher in some ranges) 
20180323, 15:34  #72  
Feb 2017
Nowhere
2^{2}·1,523 Posts 
Quote:
It occurred to me that, for a given N, odd (pseudo)primes of the form a^(2^N) + b^(2^N) are of two types: smaller number is odd, and smaller number is even. I computed the smallest of both types up to the limit N = 10, without doing any sieving, because it would have taken me longer to set up the sieving, than it took the clunky testallpairs scripts to run. (Pressing on to N = 11 and higher, though, it would definitely be worth the effort of doing a LOT of sieving.) My default assumption is that the minimal [a, b] are of each type (approximately) equally often as the upper bound for N increases. I have no idea how much larger the minimal pair of the other type may be compared to the minimal pair; whether there may be several pairs of the same type as the minimal pair which smaller than the minimal pair of the other type; etc. N = 1: [1, 2], [2, 3] N = 2; [1, 2], [2, 3] N = 3; [1, 2], [2, 13] N = 4; [1, 2], [6, 7] N = 5; [8, 9], [13, 18] N = 6; [8, 11], [7, 16] N = 7; [20, 27], [31, 32] N = 8; [5, 14], [34, 43] N = 9; [2, 13], [35, 38] N = 10; [26, 47], [39, 56] N = 11; [3, 22], ?? N = 12; [2, 53], ?? N = 13; [43, 72], ?? N = 14; [109, 216], ?? N = 15; [179, 260], ?? N = 16; [57,124], ?? Finally, the "two types" issue doesn't occur for the (pseudo)primes (a^(2^N) + b^(2^N))/2 with a and b both odd. 

20180323, 17:42  #73  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·1,997 Posts 
Quote:
Trend value's estimate is very easy. Nearly all candidates will have an equal chance to be prime which only depends on their size which is almost exactly the same in bits. So, one will have to try on the order of ~γ * 2^{m} pairs, and you have ~0.2 * a^2 pairs up to a, hence: a(m) ~ 1.15 * 2^{m/2} Plot the values and you will find great concordance with this estimate. 

20180324, 04:15  #74  
Jun 2003
3^{4}×67 Posts 
Quote:
This one uses explicit k values in cmdline (instead of bits). Also reads/writes files instead of stdin/stdout. Reads sieve.txt for candidates, appends factor.txt for factors, and at the end of the range, writes sieve.txt back with survivors. It also self starts  if you give starting k as 1, it will generate the initial sieve itself instead of reading from file (but in this case, a third parameter maxa needs to be specified to define the sieve region). The algorithm is O(maxa), and so it is best to just sieve as large a region as you want from the start (rather than trying to increase it later). EDIT: Right now, hard coded to N=17. Change the NN #define, and you're set. Last fiddled with by axn on 20180324 at 04:20 

20180324, 08:22  #75 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5×1,997 Posts 
Neat!
...Now time for a quick cuda sieve facelift, based on gfnsieve? ^_^ 
20180324, 13:48  #76 
"Jeppe"
Jan 2016
Denmark
2×7×13 Posts 
For both a and b odd, the first primes are (as others already found but did not post):
Code:
(3^1+1^1)/2 (3^2+1^2)/2 (3^4+1^4)/2 (5^8+3^8)/2 (3^16+1^16)/2 (3^32+1^32)/2 (3^64+1^64)/2 (49^128+9^128)/2 (7^256+3^256)/2 (35^512+9^512)/2 (67^1024+57^1024)/2 
20180324, 13:53  #77 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Is there a prime of the form......  PawnProver44  Miscellaneous Math  9  20160319 22:11 
OEIS A071580: Smallest prime of the form k*a(n1)*a(n2)*...*a(1)+1  arbooker  And now for something completely different  14  20150522 23:18 
Smallest prime with a digit sum of 911  Stargate38  Puzzles  6  20140929 14:18 
Smallest floor of k for cullen prime  Citrix  Prime Cullen Prime  12  20070426 19:52 
Smallest tenmilliondigit prime  Heck  Factoring  9  20041028 11:34 