20191014, 18:34  #12  
Oct 2018
2^{3}×3 Posts 
Quote:
10^165+21577 = 17108947285676514420334234847252924689159316004710883657633087494814496425420952639 * 58448949739718509083458755076513200009214119314533674765349840106126322183596397943 Using the factory approach, each SNFS factorization took about 20 CPU hours to complete for batch smoothness checking and postprocessing. I estimate that this is about 36 times faster than regular SNFS runs. However, I already had the relations needed, and had sieved more extensively than would be required for these factorizations since I obtained the relations aiming for 220 digit numbers. On the other hand, the relations can be used find the smallest brilliant number in the 164169 digit range with similar difficulty, so even if I had to sieve it should still be worth it. 

20191014, 21:38  #13 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5×587 Posts 
The relations need to be used for a fair few factorizations to be worth it but the factory approach is certainly a good approach at times.
I suspect that a siever for just the one polynomial would speed things up a bit getting the initial relations. I am upto 18 factorizations in the 150s for digits and am seeing similar runtimes. The difference for me is that I am varying the rational polynomial. What proportion of raw relations are turning into relations for the new polynomial for you? I am getting around 10%. 
20191015, 17:17  #14  
Oct 2018
2^{3}×3 Posts 
Quote:


20191015, 18:15  #15  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·5·587 Posts 
Quote:
Your numbers do make me wonder whether I should experiment again with lowering the lp bounds. I also have very high fb bounds as I found that produced relations more efficiently. 

20191015, 19:41  #16  
Oct 2018
2^{3}×3 Posts 
Quote:
The somewhat limited tests I did suggested that using the same lbpr/a bounds or using a bound that is 1 bigger on the batch checked side gave roughly the same performance, with a slight advantage for the same bound. Using a bound on the batch side that was 2 above the other side did improve the speed, but also required a lot more relations to be found to build a matrix, which in the end made it slower. You may want to do some testing of different bounds for your numbers. The alim/rlim bounds used by NFS_factory can also be played with, I tend to find that an alim/rlim that is in between 1/4 to 1/16 of 2^(lbp(r or a)) provides good speed without loosing many relations. 

20191016, 13:52  #17 
Feb 2017
Nowhere
1000111001001_{2} Posts 
Basedependence of "brilliant numbers" definition
It occurred to me that "same number of digits" is basedependent. Obviously, this requirement is most stringent in base two.
It is intuitively obvious that, if k is "sufficiently large", the smallest "2brilliant" number n > 2^{2k} is n = p_{1}*p_{2}, where p_{1} = nextprime(2^{k}) and p_{2} = nextprime(p_{1} + 1). Numerical evidence suggests that "sufficiently large" is k > 3. This notion "obviously" applies to any base. For n > 2^{2k+1}, again we want n = p_{1}*p_{2} with 2^{k} < p_{1} < p_{2} < 2^{k+1}, but (as with base ten) it is less clear how to find n, p_{1}, and p_{2}. Accordingly, I ran a fairly crude numerical search of the odd numbers greater than 2^{2k+1}, k = 3 to 63, stopping at the first product of two primes, each greater than 2^{k}. The following list gives the exponent 2k + 1, n  2^{2k+1}, and the PariGP factorization matrix of n. I was a bit surprised at the size of some of the values of n  2^{2k+1}, so wonder whether my Pari script was writ right... Code:
7 15 [11, 1; 13, 1] 9 15 [17, 1; 31, 1] 11 125 [41, 1; 53, 1] 13 57 [73, 1; 113, 1] 15 113 [131, 1; 251, 1] 17 21 [337, 1; 389, 1] 19 429 [647, 1; 811, 1] 21 51 [1289, 1; 1627, 1] 23 401 [2837, 1; 2957, 1] 25 269 [5039, 1; 6659, 1] 27 119 [9721, 1; 13807, 1] 29 191 [18269, 1; 29387, 1] 31 675 [37369, 1; 57467, 1] 33 51 [67057, 1; 128099, 1] 35 39 [132949, 1; 258443, 1] 37 57 [282577, 1; 486377, 1] 39 521 [586073, 1; 938033, 1] 41 341 [1413851, 1; 1555343, 1] 43 1281 [2270137, 1; 3874697, 1] 45 1127 [4365811, 1; 8059069, 1] 47 63 [8784509, 1; 16021099, 1] 49 2297 [19843693, 1; 28369213, 1] 51 2489 [36136003, 1; 62314579, 1] 53 1017 [69174331, 1; 130210139, 1] 55 213 [181835063, 1; 198139987, 1] 57 4131 [349671787, 1; 412144169, 1] 59 125 [556552567, 1; 1035770539, 1] 61 2309 [1187585461, 1; 1941622801, 1] 63 243 [2615800777, 1; 3526022363, 1] 65 1535 [4857360493, 1; 7595377819, 1] 67 1305 [10139465009, 1; 14554412137, 1] 69 89 [17779879213, 1; 33200214877, 1] 71 473 [47103200093, 1; 50127873197, 1] 73 1109 [72915393059, 1; 129530028839, 1] 75 2303 [186832042207, 1; 202207990753, 1] 77 615 [315191534401, 1; 479440946087, 1] 79 4041 [727484000851, 1; 830895124979, 1] 81 149 [1316039169143, 1; 1837218599507, 1] 83 2771 [2867130304021, 1; 3373200912199, 1] 85 1437 [5090617697353, 1; 7599397269173, 1] 87 2333 [12230412371077, 1; 12652272075193, 1] 89 3207 [21878940590537, 1; 28290676007887, 1] 91 1541 [38708587650571, 1; 63962036045359, 1] 93 2261 [97760550454823, 1; 101303851791011, 1] 95 303 [196374395910281, 1; 201727323327991, 1] 97 2207 [322078061207713, 1; 491981119217983, 1] 99 3465 [640081175054807, 1; 990226435045279, 1] 101 3117 [1549139962041103, 1; 1636586275339523, 1] 103 731 [2268096368906497, 1; 4471240702490587, 1] 105 1127 [6307702154395399, 1; 6430997883918241, 1] 107 1065 [9492414486632183, 1; 17093572668757471, 1] 109 561 [20445713817512341, 1; 31744409273739053, 1] 111 6933 [38103702052774607, 1; 68133758385777883, 1] 113 5775 [92393237434978633, 1; 112395603892306199, 1] 115 6213 [148781711772666527, 1; 279190058867906203, 1] 117 11865 [329199181328154989, 1; 504720269360232733, 1] 119 915 [723643575703419121, 1; 918427275812431043, 1] 121 9039 [1519592015934525539, 1; 1749453776864524069, 1] 123 1205 [3219958684779060871, 1; 3302472176598431203, 1] 125 2129 [4797828529468030733, 1; 8865530646597221717, 1] 127 16529 [10321673526145015591, 1; 16483875703828264327, 1] 
20191121, 17:36  #18 
Oct 2018
2^{3}·3 Posts 
And after another 100 SNFS factorizations, I am happy to report that
10^16527557 = 16829650665340802699068436862241855809551030170255430771254420510677298883957782921 * 59418939815513387837458599415060937929709419123971038475447675105632084607269190083 The factorization factory approach really saves some time here. 
20191121, 20:04  #19  
(loop (#_fork))
Feb 2006
Cambridge, England
2^{4}×3×7×19 Posts 
Quote:
He says 2^121+7961 and 2^97+809 rather than your cases, but he is wrong  his claimed prime factors are composite! Last fiddled with by fivemack on 20191121 at 20:08 

20191122, 15:37  #20  
Feb 2017
Nowhere
29×157 Posts 
Quote:
p2 = precprime(2^k) and p1 = precprime(p2  1). But p1*p2 is way less than 2^{2k}, probably by something of order at least k*2^{k}. However, if you relax the requirement to p2 < 2*p1 you can get numbers much closer to 2^{2k}, in line with the results for odd exponents. Here are results using this condition for even exponents from 16 to 128. The list below gives the exponent 2k, 2^{2k}  n, and the PariGP factorization matrix of n. I could easily edit my scripts to run for exponents up to 292. They would no doubt take quite a bit longer to run, though. Code:
16 63 [233, 1; 281, 1] 18 81 [503, 1; 521, 1] 20 15 [911, 1; 1151, 1] 22 215 [1787, 1; 2347, 1] 24 9 [4093, 1; 4099, 1] 26 65 [6029, 1; 11131, 1] 28 209 [12589, 1; 21323, 1] 30 137 [27779, 1; 38653, 1] 32 83 [57139, 1; 75167, 1] 34 53 [125627, 1; 136753, 1] 36 3 [242819, 1; 283007, 1] 38 167 [440441, 1; 624097, 1] 40 503 [825709, 1; 1331597, 1] 42 705 [2014013, 1; 2183723, 1] 44 447 [3486391, 1; 5045959, 1] 46 225 [8388593, 1; 8388623, 1] 48 1893 [15847327, 1; 17761669, 1] 50 365 [30198439, 1; 37283381, 1] 52 599 [48808127, 1; 92271511, 1] 54 177 [100343501, 1; 179527307, 1] 56 1529 [251449199, 1; 286569193, 1] 58 2157 [473845213, 1; 608279599, 1] 60 227 [863718871, 1; 1334834219, 1] 62 827 [1792742921, 1; 2572419037, 1] 64 173 [3183958073, 1; 5793651691, 1] 66 291 [7036439239, 1; 10486408507, 1] 68 1149 [13204545659, 1; 22351992473, 1] 70 515 [30101795611, 1; 39219973319, 1] 72 2043 [57702385861, 1; 81840055873, 1] 74 377 [110289293923, 1; 171271981709, 1] 76 2283 [195288552673, 1; 386903700661, 1] 78 2411 [428192780231, 1; 705830338243, 1] 80 159 [865222140329, 1; 1397243278073, 1] 82 1025 [2178243141013, 1; 2220001609283, 1] 84 5319 [3743220029701, 1; 5167426162597, 1] 86 3297 [8279539254449, 1; 9344874162383, 1] 88 1523 [17258876427671, 1; 17931932656123, 1] 90 3575 [25852344457321, 1; 47885020305569, 1] 92 1655 [68900966313353, 1; 71867789700097, 1] 94 1823 [127334241902017, 1; 155551565177633, 1] 96 3633 [226915003627547, 1; 349153477062749, 1] 98 7547 [504322581218419, 1; 628392742778663, 1] 100 3053 [852649093227773, 1; 1486720164598351, 1] 102 9095 [1606031568230581, 1; 3157224615764789, 1] 104 1889 [3982579711458899, 1; 5092781833165573, 1] 106 425 [6574033780821821, 1; 12340922045652259, 1] 108 5445 [14319028682673241, 1; 22663447420222771, 1] 110 131 [35367428524858559, 1; 36702533058668227, 1] 112 2283 [67641744679950409, 1; 76761722854760557, 1] 114 411 [118121996814495551, 1; 175828279187967323, 1] 116 479 [247584777165748307, 1; 335548698460328251, 1] 118 3527 [561114038083576319, 1; 592227205865651143, 1] 120 527 [879069357141345137, 1; 1512085462866600577, 1] 122 8345 [1889325481702291343, 1; 2814185292387577513, 1] 124 13247 [3682723456895302243, 1; 5774978268525276683, 1] 126 797 [8526816808278793903, 1; 9976828826396094989, 1] 128 1967 [16247245438514871883, 1; 20944003597944230483, 1] 

20191122, 16:19  #21 
Jun 2003
4,969 Posts 

20191122, 19:51  #22  
Feb 2017
Nowhere
1000111001001_{2} Posts 
Quote:
I did however run across examples in tables with repeated prime factors. It seems I have run afoul of existing terminology defining "kbrilliant" numbers as products of k prime factors, all of the same length. For different bases, the term "base b kbrilliant" is apparently the appropriate term. And this does mean that all factors have the same number of baseb digits. I also had it all bollixed up about which powers of the base to look at. For base b 2brilliant numbers, it seems you always want numbers close to odd powers of b. Numbers just greater have an even number of digits; those just less, an odd number of digits. The following table lists the odd exponent i, the least k for which n = 2^i  k is a base2 2brilliant number (two distinct prime factors) with i binary digits, and the PariGP factorization matrix for n. For odd i less than 9, no numbers of the required kind exist. I am using a bound of 2*i^2 for k. I note that for i = 91, k is nearly 1.75*i^2, and for i = 113, k is over 1.84*i^2. It is possible that for some larger i, the least k might exceed my bound. Code:
9 19 [17, 1; 29, 1] 11 27 [43, 1; 47, 1] 13 55 [79, 1; 103, 1] 15 25 [137, 1; 239, 1] 17 43 [283, 1; 463, 1] 19 151 [557, 1; 941, 1] 21 51 [1399, 1; 1499, 1] 23 45 [2357, 1; 3559, 1] 25 403 [4373, 1; 7673, 1] 27 279 [11119, 1; 12071, 1] 29 51 [22717, 1; 23633, 1] 31 267 [46271, 1; 46411, 1] 33 171 [76493, 1; 112297, 1] 35 421 [136273, 1; 252139, 1] 37 213 [297391, 1; 462149, 1] 39 187 [712321, 1; 771781, 1] 41 373 [1286533, 1; 1709263, 1] 43 769 [2217443, 1; 3966773, 1] 45 201 [5591617, 1; 6292343, 1] 47 181 [8578639, 1; 16405573, 1] 49 1299 [18463483, 1; 30489911, 1] 51 1081 [37587401, 1; 59908367, 1] 53 171 [93220117, 1; 96622913, 1] 55 1261 [154304077, 1; 233492191, 1] 57 1111 [288358229, 1; 499778309, 1] 59 4005 [630854771, 1; 913777273, 1] 61 2241 [1452810757, 1; 1587159923, 1] 63 499 [2298974999, 1; 4011949691, 1] 65 1095 [5949183623, 1; 6201437119, 1] 67 987 [11322007447, 1; 13034256803, 1] 69 1251 [24083972587, 1; 24509902103, 1] 71 4111 [37656657113, 1; 62702943449, 1] 73 1113 [78259949419, 1; 120684117941, 1] 75 4177 [170344641589, 1; 221779396819, 1] 77 2589 [336730384093, 1; 448773661631, 1] 79 2167 [736399146137, 1; 820835973233, 1] 81 3105 [1504976355301, 1; 1606571180147, 1] 83 1219 [2370550533719, 1; 4079814549131, 1] 85 5481 [5445117332089, 1; 7104645110159, 1] 87 571 [12151712952499, 1; 12734213317543, 1] 89 3543 [20667822274579, 1; 29948487625811, 1] 91 14487 [44287089457829, 1; 55905233531509, 1] 93 2013 [72818547054119, 1; 136002717919141, 1] 95 771 [168927433481341, 1; 234503540607617, 1] 97 703 [377528015377169, 1; 419720705681201, 1] 99 5005 [778215345985117, 1; 814460037808399, 1] 101 10533 [1175739633767197, 1; 2156345782384727, 1] 103 1161 [2568128689638119, 1; 3948869401577713, 1] 105 3331 [5099766108348349, 1; 7954250909840449, 1] 107 2959 [11959245418571939, 1; 13567685179972571, 1] 109 1863 [22842198789725741, 1; 28413950569801789, 1] 111 1615 [36566779302877591, 1; 70997459408822263, 1] 113 23553 [94092055716457949, 1; 110366317729980811, 1] 115 15865 [199648814215779179, 1; 208057208010182357, 1] 117 411 [365157478894991609, 1; 455018749652654029, 1] 119 747 [596963533949333113, 1; 1113324282130885757, 1] 121 2233 [1572613511877682669, 1; 1690470017897573251, 1] 123 7011 [2477236125782494633, 1; 4292616216760676309, 1] 125 289 [5766628885980996871, 1; 7376111191847811433, 1] 127 5751 [11502175072681465387, 1; 14792087790818572571, 1] Last fiddled with by Dr Sardonicus on 20191122 at 19:55 Reason: awk 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Could a Distributed Computing approach help find the smallest Brier number?  jasong  Math  5  20070529 13:30 
10^119+x brilliant number  Citrix  Prime Sierpinski Project  12  20060519 22:21 
smallest number used in a mathematical proof?  ixfd64  Lounge  22  20060201 17:06 
Can you find the smallest number?  Fusion_power  Puzzles  8  20031118 19:36 
Smallest untested number?  wirthi  Math  10  20031005 13:02 