Smallest 10^179+c Brilliant Number (p90 * p90)

[Branger]

Originally Posted by henryzz

Can I suggest looking at the factorization factory if you want to do more of these. A lot of the work can be shared between numbers. I would think that a degree 2 or 3 poly with a common rational poly would make sense here.

As it happens, the relations I had already found were useful here as well, to factor numbers of the form 10^165+c with a degree 3 polynomial. After 90 SNFS factorizations, I am happy to report that

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 3-6 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 164-169 digit range with similar difficulty, so even if I had to sieve it should still be worth it.

[henryzz]

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%.

[Branger]

Originally Posted by henryzz

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%.

I'm using a shared rational polynomial and vary the algebraic one, which may cause some differences to your results. To factor an SNFS-165, about 500M relations needs to be batch smoothness checked, which finds around 9M relations, so I get closer to 2%. These jobs use an lbpr/a of 26, if yours are higher then that may explain the difference.

[henryzz]

Originally Posted by Branger

I'm using a shared rational polynomial and vary the algebraic one, which may cause some differences to your results. To factor an SNFS-165, about 500M relations needs to be batch smoothness checked, which finds around 9M relations, so I get closer to 2%. These jobs use an lbpr/a of 26, if yours are higher then that may explain the difference.

My numbers are quite different. I am processing 1.5B relations and getting out 140M. My large prime bounds are 30a and 32r. My algebraic side is deg8 which meant a larger bound. On the rational side I didn't see that much slowdown by having a very large bound and it got a lot more relations. I suspect I would benefit from a larger algebraic bound given it is deg8(deliberately skewed to make rational easier).
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.

[Branger]

Originally Posted by henryzz

My numbers are quite different. I am processing 1.5B relations and getting out 140M. My large prime bounds are 30a and 32r. My algebraic side is deg8 which meant a larger bound. On the rational side I didn't see that much slowdown by having a very large bound and it got a lot more relations. I suspect I would benefit from a larger algebraic bound given it is deg8(deliberately skewed to make rational easier).
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.

I did do some rather extensive sieving which probably got me a lot more relations having a smaller largest prime. This allows me to reduce the lbpr/a bounds a bit compared to yours. I had hoped that this would make the linalg a bit easier, though the linalg still ends up being a bit more time consuming than the batch smoothness checking.

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.

[Dr Sardonicus]

It occurred to me that "same number of digits" is base-dependent. Obviously, this requirement is most stringent in base two.

It is intuitively obvious that, if k is "sufficiently large", the smallest "2-brilliant" number n > 2^2k is n = p₁*p₂, where p₁ = nextprime(2^k) and p₂ = nextprime(p₁ + 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₁*p₂ with 2^k < p₁ < p₂ < 2^k+1, but (as with base ten) it is less clear how to find n, p₁, and p₂. 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 Pari-GP 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...

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]

[Branger]

And after another 100 SNFS factorizations, I am happy to report that

10^165-27557 =

16829650665340802699068436862241855809551030170255430771254420510677298883957782921 *
59418939815513387837458599415060937929709419123971038475447675105632084607269190083

The factorization factory approach really saves some time here.

[fivemack]

Originally Posted by Dr Sardonicus

It occurred to me that "same number of digits" is base-dependent. Obviously, this requirement is most stringent in base two.

It is intuitively obvious that, if k is "sufficiently large", the smallest "2-brilliant" number n > 2^2k is n = p₁*p₂, where p₁ = nextprime(2^k) and p₂ = nextprime(p₁ + 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₁*p₂ with 2^k < p₁ < p₂ < 2^k+1, but (as with base ten) it is less clear how to find n, p₁, and p₂. 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 Pari-GP 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...

97 2207 [322078061207713, 1; 491981119217983, 1]
121 9039 [1519592015934525539, 1; 1749453776864524069, 1]

https://www.alpertron.com.ar/BRILLIANT2.HTM#twobr mostly agrees with you (his tables are interspersed 'smallest with 2N bits' and 'largest with 2N-1 bits' which are the two non-trivial cases) and goes up to 292

He says 2^121+7961 and 2^97+809 rather than your cases, but he is wrong - his claimed prime factors are composite!

[Dr Sardonicus]

Originally Posted by fivemack

https://www.alpertron.com.ar/BRILLIANT2.HTM#twobr mostly agrees with you (his tables are interspersed 'smallest with 2N bits' and 'largest with 2N-1 bits' which are the two non-trivial cases) and goes up to 292

He says 2^121+7961 and 2^97+809 rather than your cases, but he is wrong - his claimed prime factors are composite!

Hmm. It seems to me that, for the largest 2-brilliant number less than 2^2k, in the sense of both factors having the same number of bits, both prime factors have to be less than 2^k. They obviously can't both be greater than 2^k. And if one of them is greater than 2^k and the other less, the two factors will have different numbers of bits. So, it would appear that the best you can do is

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 Pari-GP 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.

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]

[axn]

Originally Posted by Dr Sardonicus

Hmm. It seems to me that, for the largest 2-brilliant number less than 2^2k,
<snip>
p2 = precprime(2^k) and p1 = precprime(p2 - 1).

I don't think there is any restriction that primes be distinct, so the trivial precprime(2^k)^2 will do.

[Dr Sardonicus]

Originally Posted by axn

I don't think there is any restriction that primes be distinct, so the trivial precprime(2^k)^2 will do.

Every account of the original definition of "brilliant numbers" I have read indicates distinct prime factors. This includes using them for testing factoring programs, which in the case of the square of a prime, would only test whether the program checks for pure powers.

I did however run across examples in tables with repeated prime factors.

It seems I have run afoul of existing terminology defining "k-brilliant" numbers as products of k prime factors, all of the same length. For different bases, the term "base b k-brilliant" is apparently the appropriate term. And this does mean that all factors have the same number of base-b digits.

I also had it all bollixed up about which powers of the base to look at. For base b 2-brilliant 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 base-2 2-brilliant number (two distinct prime factors) with i binary digits, and the Pari-GP 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.

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]