20211103, 23:37  #1 
Bemusing Prompter
"Danny"
Dec 2002
California
11×13×17 Posts 
an idea to extend P1 stage 1 to find more factors
For the first stage, the P1 algorithm uses the highest power of each prime less than or equal to B1 when computing the product of the primes. However, this means we'll miss factors where k has a repeated factor greater than sqrt(B1).
102646067 and 105144859 are two examples with such factors. P1 cannot normally find these without the nowunsupported BrentSuyama extension. So my idea is to add an option to increase the power of each prime by 1 (or more) up to a percentage of the given value. For example, B1=1000000+50000 means that we do the first stage as normal, and then multiply E (or m) again by each prime up to 50000. I just don't know how successful this method may be as there is no data on how many known factors there are where k has a repeated factor greater than the square root of the suggested B1 value. James could probably run some database queries on his website and find out for us. Last fiddled with by ixfd64 on 20211103 at 23:44 
20211104, 03:19  #2 
Jun 2003
1010010001110_{2} Posts 
It is not worth it. You're better off just adding new primes into B1 (i.e. extend B1).

20211104, 04:27  #3 
"University student"
May 2021
Beijing, China
3×5×13 Posts 
It's not worth it, and now people are suggesting to use smaller bounds for P1 (1 test saved if a factor is found, or B1=400000 B2=1800000) to eliminate exponents as quickly as possible.
Last fiddled with by Zhangrc on 20211104 at 04:27 
20211104, 09:26  #4  
"Mihai Preda"
Apr 2015
2537_{8} Posts 
Quote:
I suggest using bounds of at least B1=1M,B2=20M. (I use B1=3M and B2=60M myself). 

20211104, 13:54  #5  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
13707_{8} Posts 
Quote:
The bounds stated may be ok for Gpuowl 7.x, with its innovative dualuse of singlycomputed powers of 3, for both P1 stage 1 and PRP performed together, but not other software, or earlier versions of Gpuowl, for which those bounds likely cost more total computing time than skipping P1 entirely on the exponent. See https://mersenneforum.org/showpost.p...07&postcount=3 for a prime95 test & analysis vs. # of testssaved. Current # of tests saved on average appears to be ~1.048 at ~107M. Last fiddled with by kriesel on 20211104 at 14:04 

20211104, 17:16  #6  
"Robert Gerbicz"
Oct 2005
Hungary
2×3^{2}×5×17 Posts 
Quote:
In the general way: for a given T=prod(q_i) exponent the effective score=log2(T)/sum(1/q_i), where smaller score is better. Since this is a 1st stage idea, let B=B1. What you all forget that if you include q^e for a possible extended 1st stage in (B,B'), then the extra effort for q^e in (B,B') means only a qth exponentiation in the method [because in any case you'd process q^(e1) in the usual way because q^(e1)<B], and not q^eth exponentiation, but gives you the largish 1/q>1/B' probability to find a divisor with the P1 method. My suggestion is to use B'=2*B, in fact a slightly smaller. To convince you quickly: The effective score=log2(T)/sum(1/q^e), where T is the exponent. You stopped at B, and at that point you've score=log2(B)*B=besteff. Include all primepowers, but not primes from the (B,2*B) interval, so choose B'=2*B. For a single primepower the effective score is at most log2(sqrt(2*B))*2*B=0.5*(log2(B)+0.5)*2*B= =(log2(B)+0.5)*B, almost good, there is a fractional error bit. So shrink it a little: For a fixed B choose B'=c*B (where c depends on B and e!), then log2(sqrt(c*B))*c*B=0.5*(log2(B)+log2(c))*c*B<log2(B)*B=besteff for any c<2 if B is "large". In general the best bound for fixed B and e>1 let B'=U, at an equal effective score you would see: log2(U^(1/e))*U=log2(B)*B or the same log(U)*U/e=log(B)*B, because you can change to natural logarithm (and here e>1 is an integer). Example: for B=10^5 and e=2 this gives U=189482 (as expected close to 2*B for e=2), if we use this same bound for all e>1 in (B,U) then: log2(T)=1062.02 (used the product of primepowers's core part). sum(1/q^e)=0.000954325 and effective score=1112854.2 what is smaller than the base score: log2(B)*B=1660964.05 ps. as said for e>2 you have to use an even larger bound, and that could be higher than 2*B, so for smallish primes you have to include more primes, q^2 or more, the analysis is still correct, because in these cases the algorithm picked up the smaller primepower for a smaller e'<e integer. 

20211104, 18:09  #7  
"Robert Gerbicz"
Oct 2005
Hungary
2772_{8} Posts 
Quote:
log2(T)=187.0 sum(1/q^e)=0.00018 and effective score=995837.4 what is smaller than the base score: log2(B)*B=1660964.05 

20211105, 08:02  #8 
Jun 2003
1010010001110_{2} Posts 
Does this look right?
Code:
merit(p, n) = log(p) * (p1) * p^(n1); find_count(p, t)=my(m); for(i=2, oo, m=merit(p, i); if(m > t, return(i1))); old_find_count(p, B1)=floor(log(B1)/log(p)); B1 = 1000000; last_prime = precprime(B1); target_merit = merit(last_prime, 1); forprime(p=2, last_prime, c = find_count(p, target_merit); print(p, ":", c, ":", old_find_count(p, B1)); if(c == 1, break())) Code:
2:25:19 3:15:12 5:10:8 7:8:7 11:6:5 13:6:5 17:5:4 19:5:4 23:4:4 29:4:4 31:4:4 37:4:3 41:4:3 43:4:3 47:3:3 53:3:3 59:3:3 61:3:3 67:3:3 71:3:3 73:3:3 79:3:3 83:3:3 89:3:3 97:3:3 101:3:2 103:3:2 107:3:2 109:3:2 113:3:2 127:3:2 131:3:2 137:3:2 139:3:2 149:2:2 151:2:2 157:2:2 163:2:2 167:2:2 173:2:2 179:2:2 181:2:2 191:2:2 193:2:2 197:2:2 199:2:2 211:2:2 223:2:2 227:2:2 229:2:2 233:2:2 239:2:2 241:2:2 251:2:2 257:2:2 263:2:2 269:2:2 271:2:2 277:2:2 281:2:2 283:2:2 293:2:2 307:2:2 311:2:2 313:2:2 317:2:2 331:2:2 337:2:2 347:2:2 349:2:2 353:2:2 359:2:2 367:2:2 373:2:2 379:2:2 383:2:2 389:2:2 397:2:2 401:2:2 409:2:2 419:2:2 421:2:2 431:2:2 433:2:2 439:2:2 443:2:2 449:2:2 457:2:2 461:2:2 463:2:2 467:2:2 479:2:2 487:2:2 491:2:2 499:2:2 503:2:2 509:2:2 521:2:2 523:2:2 541:2:2 547:2:2 557:2:2 563:2:2 569:2:2 571:2:2 577:2:2 587:2:2 593:2:2 599:2:2 601:2:2 607:2:2 613:2:2 617:2:2 619:2:2 631:2:2 641:2:2 643:2:2 647:2:2 653:2:2 659:2:2 661:2:2 673:2:2 677:2:2 683:2:2 691:2:2 701:2:2 709:2:2 719:2:2 727:2:2 733:2:2 739:2:2 743:2:2 751:2:2 757:2:2 761:2:2 769:2:2 773:2:2 787:2:2 797:2:2 809:2:2 811:2:2 821:2:2 823:2:2 827:2:2 829:2:2 839:2:2 853:2:2 857:2:2 859:2:2 863:2:2 877:2:2 881:2:2 883:2:2 887:2:2 907:2:2 911:2:2 919:2:2 929:2:2 937:2:2 941:2:2 947:2:2 953:2:2 967:2:2 971:2:2 977:2:2 983:2:2 991:2:2 997:2:2 1009:2:1 1013:2:1 1019:2:1 1021:2:1 1031:2:1 1033:2:1 1039:2:1 1049:2:1 1051:2:1 1061:2:1 1063:2:1 1069:2:1 1087:2:1 1091:2:1 1093:2:1 1097:2:1 1103:2:1 1109:2:1 1117:2:1 1123:2:1 1129:2:1 1151:2:1 1153:2:1 1163:2:1 1171:2:1 1181:2:1 1187:2:1 1193:2:1 1201:2:1 1213:2:1 1217:2:1 1223:2:1 1229:2:1 1231:2:1 1237:2:1 1249:2:1 1259:2:1 1277:2:1 1279:2:1 1283:2:1 1289:2:1 1291:2:1 1297:2:1 1301:2:1 1303:2:1 1307:2:1 1319:2:1 1321:2:1 1327:2:1 1361:2:1 1367:2:1 1373:2:1 1381:2:1 1399:1:1 
20211106, 15:54  #9 
"Robert Gerbicz"
Oct 2005
Hungary
2·3^{2}·5·17 Posts 
I'm not sure what your code is doing, anyway, for a fixed B bound and e>1, solve the
x*log(x)/e=B*log(B) equation, say binary search is fine since x*log(x) is monotone increasing (on [exp(1),inf) interval ). And put all q^e (for q prime) to the smooth set, where q is in the [B,U] interval, and U is the solution of the above equation. You could argue that smooth number's factors is not that random, and that is true, say more than half of them is even. So ran some tests, that is in some way deeper and at once lighter. General method let the antique pm1 way, and the improved is the improved. Since we want a comparison we have to adjust the B limit, lowering that in such a way that the exponent will be smaller, but we find more smooth numbers. Let B=1000, but for simplicity we use the same U bound for all e>1, the algorithm will include 1024,1331,1369,1681 [these are 2^10, 11^3, 37^2, 41^2] and exclude 991 and 997. Here 2*11*37*41<991*997 gives that the exponent is smaller what used in the general method. In the [1e13,2e13] interval with a simple backtracking it is possible to find all smooth numbers (for these 2 methods) The general method found 12988813875 smooth numbers. The improved found 13058081975 smooth numbers, so slightly more. You could say that the included 2^10 was the booster, so repeat the search for B=1024 (here B is included in the set), the method will include 1331,1369,1681,1849 [these are 11^3, 37^2, 41^2, 43^2] and exclude 1019 and 1021. [Notice that in this case, basically 1024 would be also dropped out due to the smaller B limit, but ofcourse the improved method would pick up it, in other words: you would drop out some nonprimes also, but all of those will reappear in the set.] Again 11*37*41*43<1019*1021, so the exponent is smaller. The general method found 13691324851 smooth numbers. The improved found 13809957083 smooth numbers, slightly more. In both cases we got a roughly ~0.5% gain over the general method using primepowers out of order. [the gain is smaller for larger B !] ps. you could still say that this is not a fair test, because p1 is even for p>2, so it won't be a random smooth number. But it is proven that for any M the p mod M is equally distributed in the mod M reduced residue classes. Last fiddled with by R. Gerbicz on 20211106 at 16:15 
20211122, 14:57  #10 
Jun 2003
5262_{10} Posts 
Sorry, I meant to reply to this earlier but somehow slipped my mind.
Anyway, the code computes a cost function of including p^n in the product. It is basically log(p) (i.e proportional to the bits) / probability of p^n dividing a random P1. i.e. more bits = costlier. Less probable = less useful. This comes out as log(p) * (p1) * p^(n1) > what I call as the merit function. The code then finds the largest n for each p such that merit(p^n) doesn't exceed the target merit, which is just the cost for a single instance of the largest prime under B1. For comparison, it also prints the count as per the regular method. Last fiddled with by axn on 20211122 at 14:57 
20211123, 02:11  #11 
"Tucker Kao"
Jan 2020
Head Base M168202123
2^{5}·3·7 Posts 
Do these type of factors show up with the chance of 1% or more? If not, then the extra time spent may not worth the additional factors found in the long run. The P1 stages were sped up after Prime95 v30.5, so the larger bounds become more possible for the newer PCs.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to use PP1 method to find factors?  Miszka  PrimeNet  2  20210424 08:36 
Find factors for non base2 candidates  pepi37  GMPECM  2  20170307 20:13 
Best Way to find large factors  mahnouman  Information & Answers  19  20130222 06:11 
new idea on an older one just can't find thread  science_man_88  Miscellaneous Math  2  20110101 18:18 
How to find factors I found with TF?  edorajh  PrimeNet  3  20041001 19:16 