mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-10-14, 18:34   #12
Branger
 
Oct 2018

2×3×5 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Branger is offline   Reply With Quote
Old 2019-10-14, 21:38   #13
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×33×5×11 Posts
Default

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%.
henryzz is offline   Reply With Quote
Old 2019-10-15, 17:17   #14
Branger
 
Oct 2018

2·3·5 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Branger is offline   Reply With Quote
Old 2019-10-15, 18:15   #15
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×33×5×11 Posts
Default

Quote:
Originally Posted by Branger View Post
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.
henryzz is offline   Reply With Quote
Old 2019-10-15, 19:41   #16
Branger
 
Oct 2018

2·3·5 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Branger is offline   Reply With Quote
Old 2019-10-16, 13:52   #17
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

120278 Posts
Default Base-dependence of "brilliant numbers" definition

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 > 22k is n = p1*p2, where p1 = nextprime(2k) and p2 = nextprime(p1 + 1). Numerical evidence suggests that "sufficiently large" is k > 3. This notion "obviously" applies to any base.

For n > 22k+1, again we want n = p1*p2 with 2k < p1 < p2 < 2k+1, but (as with base ten) it is less clear how to find n, p1, and p2. Accordingly, I ran a fairly crude numerical search of the odd numbers greater than 22k+1, k = 3 to 63, stopping at the first product of two primes, each greater than 2k. The following list gives the exponent 2k + 1, n - 22k+1, and the Pari-GP factorization matrix of n.

I was a bit surprised at the size of some of the values of n - 22k+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]
Dr Sardonicus is offline   Reply With Quote
Old 2019-11-21, 17:36   #18
Branger
 
Oct 2018

2×3×5 Posts
Default

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.
Branger is offline   Reply With Quote
Old 2019-11-21, 20:04   #19
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22×32×179 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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 > 22k is n = p1*p2, where p1 = nextprime(2k) and p2 = nextprime(p1 + 1). Numerical evidence suggests that "sufficiently large" is k > 3. This notion "obviously" applies to any base.

For n > 22k+1, again we want n = p1*p2 with 2k < p1 < p2 < 2k+1, but (as with base ten) it is less clear how to find n, p1, and p2. Accordingly, I ran a fairly crude numerical search of the odd numbers greater than 22k+1, k = 3 to 63, stopping at the first product of two primes, each greater than 2k. The following list gives the exponent 2k + 1, n - 22k+1, and the Pari-GP factorization matrix of n.

I was a bit surprised at the size of some of the values of n - 22k+1, so wonder whether my Pari script was writ right...

Code:
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!

Last fiddled with by fivemack on 2019-11-21 at 20:08
fivemack is offline   Reply With Quote
Old 2019-11-22, 15:37   #20
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

141716 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 22k, in the sense of both factors having the same number of bits, both prime factors have to be less than 2k. They obviously can't both be greater than 2k. And if one of them is greater than 2k 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 22k, probably by something of order at least k*2k.

However, if you relax the requirement to p2 < 2*p1 you can get numbers much closer to 22k, 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, 22k - 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.

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]
Dr Sardonicus is offline   Reply With Quote
Old 2019-11-22, 16:19   #21
axn
 
axn's Avatar
 
Jun 2003

112×43 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Hmm. It seems to me that, for the largest 2-brilliant number less than 22k,
<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.
axn is offline   Reply With Quote
Old 2019-11-22, 19:51   #22
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10100000101112 Posts
Default

Quote:
Originally Posted by axn View Post
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.


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 2019-11-22 at 19:55 Reason: awk
Dr Sardonicus is offline   Reply With Quote
Reply

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 2007-05-29 13:30
10^119+x brilliant number Citrix Prime Sierpinski Project 12 2006-05-19 22:21
smallest number used in a mathematical proof? ixfd64 Lounge 22 2006-02-01 17:06
Can you find the smallest number? Fusion_power Puzzles 8 2003-11-18 19:36
Smallest untested number? wirthi Math 10 2003-10-05 13:02

All times are UTC. The time now is 21:53.


Tue Dec 7 21:53:08 UTC 2021 up 137 days, 16:22, 1 user, load averages: 1.35, 1.41, 1.35

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.