Consider numbers of the form a^2^n + b^2^n. For each exponent n, we give the first 20 prime numbers of that form in ascending order. Primes of this form is known as Generalized Fermat Primes, which is confusingly a generalization of another form (b restricted to 1) also known as Generalized Fermat Primes.
a^2^0 + b^2^0 : [1,1] [2,0] [2,1] [3,0] [3,2] [4,1] [5,0] [4,3] [5,2] [6,1] [7,0] [6,5] [7,4] [8,3] [9,2] [10,1] [11,0] [7,6] [8,5] [9,4] [10,3]
a^2^1 + b^2^1 : [1,1] [2,1] [3,2] [4,1] [5,2] [6,1] [5,4] [7,2] [6,5] [8,3] [8,5] [9,4] [10,1] [10,3] [8,7] [11,4] [10,7] [11,6] [13,2] [10,9] [12,7]
a^2^2 + b^2^2 : [1,1] [2,1] [3,2] [4,1] [4,3] [5,2] [5,4] [6,1] [7,2] [7,4] [7,6] [8,3] [8,5] [9,2] [9,8] [10,7] [11,2] [11,4] [11,6] [10,9] [13,4]
a^2^3 + b^2^3 : [1,1] [2,1] [4,1] [6,5] [10,3] [12,7] [13,2] [13,8] [14,3] [15,8] [16,9] [16,13] [17,4] [19,4] [18,17] [20,7] [20,17] [21,2] [21,8] [22,3] [22,5]
a^2^4 + b^2^4 : [1,1] [2,1] [4,3] [6,5] [7,6] [8,7] [12,5] [13,8] [13,10] [14,5] [15,14] [16,11] [17,10] [17,14] [18,7] [18,11] [19,16] [21,8] [21,10] [22,9] [22,15]
a^2^5 + b^2^5 : [1,1] [9,8] [11,10] [13,12] [18,13] [19,10] [23,22] [29,2] [29,22] [30,1] [33,4] [34,5] [37,18] [37,30] [37,34] [38,11] [38,29] [38,31] [39,4] [39,32] [40,3]
a^2^6 + b^2^6 : [1,1] [11,8] [13,6] [16,7] [17,14] [29,12] [32,3] [32,27] [37,2] [38,7] [38,23] [39,4] [41,10] [49,6] [51,14] [52,3] [53,2] [55,4] [55,36] [58,21] [60,47]
a^2^7 + b^2^7 : [1,1] [27,20] [32,31] [38,37] [44,25] [45,38] [47,10] [47,14] [47,24] [53,10] [54,47] [62,11] [66,65] [68,31] [69,40] [77,38] [78,53] [84,13] [85,6] [87,82] [88,21]
a^2^8 + b^2^8 : [1,1] [14,5] [14,9] [16,3] [34,25] [38,13] [43,34] [50,17] [52,25] [54,31] [65,54] [68,49] [70,9] [73,44] [76,73] [77,12] [83,26] [83,48] [86,85] [87,86] [88,85]
a^2^9 + b^2^9 : [1,1] [13,2] [29,22] [35,24] [38,35] [44,3] [46,1] [60,59] [68,61] [89,62] [92,89] [96,17] [99,94] [115,8] [115,18] [116,99] [117,10] [119,54] [124,19] [136,25] [143,68]
a^2^10 + b^2^10 : [1,1] [47,26] [56,39] [67,28] [68,59] [72,47] [80,43] [82,79] [84,71] [103,32] [104,9] [114,97] [115,6] [119,86] [128,93] [134,49] [144,125] [146,107] [149,122] [157,22] [162,53]
a^2^11 + b^2^11 : [1,1] [22,3] [43,2] [78,41] [82,9] [101,18] [106,29] [109,18] [150,1] [150,7] [163,78] [188,15] [209,142] [211,190] [236,101] [254,109] [259,76] [263,88] [264,71] [271,2] [281,52]
a^2^12 + b^2^12 : [1,1] [53,2] [53,48] [122,69] [137,10] [153,40] [155,66] [215,98] [221,198] [228,211] [251,174] [260,77] [269,142] [281,188] [310,169] [311,30] [312,311] [317,74] [330,47]
a^2^13 + b^2^13 : [1,1] [72,43] ... [257,52]
Exponents 0 through 11 took 2.5 hours total. The largest prime in that batch, 281^2048 + 52^2048, has size 16660 bits.
The short list for exponent 12 is the result of 24 hours of computing. The largest prime on that line, 330^4096 + 47^4096, has size 34269 bits.
The first two primes for exponent 13 took 12 hours to find. 72^8192 + 43^8192 has size 50545 bits. The third listed prime, 257^8192 + 52^8192 (65583 bits), was found when we accidentally started searching at the wrong start point. There is an unsearched gap indicated by ellipses.
We also searched for primes of the form (a^2^n + b^2^n)/2. For exponents greater than 0, this requires both a and b to be odd, a parity combination not possible above.
(a^2^0 + b^2^0)/2 : [2,2] [3,1] [4,0] [3,3] [4,2] [5,1] [6,0] [5,5] [6,4] [7,3] [8,2] [9,1] [10,0] [7,7] [8,6] [9,5] [10,4] [11,3] [12,2] [13,1] [14,0]
(a^2^1 + b^2^1)/2 : [2,0] [3,1] [5,1] [5,3] [7,3] [7,5] [9,1] [9,5] [11,1] [11,5] [13,3] [13,5] [11,9] [13,7] [15,1] [15,7] [17,3] [17,5] [15,11] [19,1] [19,5]
(a^2^2 + b^2^2)/2 : [3,1] [5,1] [5,3] [7,1] [9,5] [9,7] [11,1] [11,7] [11,9] [13,1] [13,3] [13,5] [13,11] [15,7] [15,11] [17,1] [17,3] [17,5] [17,7] [17,11] [17,13]
(a^2^3 + b^2^3)/2 : [5,3] [9,1] [11,3] [13,1] [13,9] [17,3] [19,17] [23,3] [25,19] [27,7] [27,11] [29,5] [29,17] [29,23] [29,27] [31,5] [31,7] [31,11] [31,27] [31,29] [33,1]
(a^2^4 + b^2^4)/2 : [3,1] [7,5] [9,1] [11,7] [13,5] [15,13] [17,3] [19,3] [23,5] [23,19] [25,11] [25,13] [27,5] [27,25] [29,1] [31,23] [31,25] [31,27] [35,9] [35,13] [35,31]
(a^2^5 + b^2^5)/2 : [3,1] [9,1] [11,7] [21,1] [21,19] [25,7] [31,11] [33,13] [33,29] [35,29] [39,35] [41,7] [43,3] [43,19] [47,37] [49,3] [49,37] [51,25] [53,3] [53,23] [53,29]
(a^2^6 + b^2^6)/2 : [3,1] [19,11] [33,19] [35,1] [41,17] [41,37] [43,29] [51,1] [51,49] [55,27] [59,51] [61,19] [65,17] [71,23] [75,23] [75,37] [81,67] [83,61] [85,1] [89,49] [91,81]
(a^2^7 + b^2^7)/2 : [49,9] [51,7] [59,23] [67,11] [67,35] [69,43] [69,53] [71,39] [73,11] [87,37] [89,17] [91,85] [99,61] [113,1] [113,15] [121,89] [121,113] [125,3] [127,27] [127,115] [131,37]
(a^2^8 + b^2^8)/2 : [7,3] [21,5] [37,11] [37,17] [45,23] [51,23] [57,35] [61,53] [75,37] [75,43] [81,59] [89,63] [95,31] [101,83] [103,11] [107,63] [111,35] [111,89] [115,61] [121,7] [121,13]
(a^2^9 + b^2^9)/2 : [35,9] [41,17] [51,13] [67,15] [81,37] [83,37] [89,83] [101,3] [113,91] [115,79] [123,47] [123,85] [127,51] [127,107] [131,51] [135,79] [137,31] [149,87] [155,39] [155,43] [159,13]
(a^2^10 + b^2^10)/2 : [67,57] [77,15] [79,7] [93,85] [95,61] [117,29] [151,33] [181,71] [181,155] [183,37] [185,147] [191,111] [193,11] [199,55] [211,29] [211,113] [215,21] [223,73] [223,83] [229,93] [229,185]
(a^2^11 + b^2^11)/2 : [75,49] [109,69] [109,81] [167,75] [193,155] [195,41] [227,53] [249,107] [259,223] [275,39] [281,107] [299,35] [311,117] [333,287] [335,239] [349,259] [351,239] [353,125] [409,357] [431,39] [431,167]
This list took 3.5 hours. The largest prime has size 17923 bits.
Haskell source code here. We use Data.List.Ordered.mergeBy to merge infinite lists to generate numbers in order for primality testing. The code is generalized to handle an arbitrary number of terms, a^2^n + b^2^n + c^2^n + ..., though we only investigated 2 terms. The tricky bit of code, in the cchildren function, avoids generating the same number multiple times. This saves an exponential amount of work.
Update (2020-06-28): minor wordsmithing.
No comments :
Post a Comment