an idea to extend P-1 stage 1 to find more factors

[ixfd64]

For the first stage, the P-1 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. P-1 cannot normally find these without the now-unsupported Brent-Suyama 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.

[axn]

It is not worth it. You're better off just adding new primes into B1 (i.e. extend B1).

[Zhangrc]

It's not worth it, and now people are suggesting to use smaller bounds for P-1 (1 test saved if a factor is found, or B1=400000 B2=1800000) to eliminate exponents as quickly as possible.

[preda]

Originally Posted by Zhangrc

It's not worth it, and now people are suggesting to use smaller bounds for P-1 (1 test saved if a factor is found, or B1=400000 B2=1800000) to eliminate exponents as quickly as possible.

P-1 only "eliminates" an exponent if a factor is found.

I suggest using bounds of at least B1=1M,B2=20M. (I use B1=3M and B2=60M myself).

[kriesel]

Originally Posted by preda

P-1 only "eliminates" an exponent if a factor is found.

I suggest using bounds of at least B1=1M,B2=20M. (I use B1=3M and B2=60M myself).

P-1 completion to above modest bounds eliminates a primality test or more than one if a factor is found. If a factor is not found, and bounds sufficient for the server's threshold were used, it eliminates the P-1 phase of testing an exponent. If bounds were so low they did not meet the server's threshold, and no factor was found, P-1 will be assigned again on the same exponent (unless a primality test is reported in first I think).

The bounds stated may be ok for Gpuowl 7.x, with its innovative dual-use of singly-computed powers of 3, for both P-1 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 P-1 entirely on the exponent. See https://mersenneforum.org/showpost.p...07&postcount=3 for a prime95 test & analysis vs. # of tests-saved. Current # of tests saved on average appears to be ~1.048 at ~107M.

[R. Gerbicz]

Originally Posted by axn

It is not worth it. You're better off just adding new primes into B1 (i.e. extend B1).

Originally Posted by Zhangrc

It's not worth it

Today multiple times I felt the same, but currently I think that this is a working idea, even in P+1/ecm ! Would give a tiny speedup. Let me check my suggestion.
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 q-th exponentiation in the method [because in any case you'd process q^(e-1) in the usual way because q^(e-1)<B], and not q^e-th exponentiation, but gives you the largish 1/q>1/B' probability to find a divisor with the P-1 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.

[R. Gerbicz]

Originally Posted by R. Gerbicz

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

correction:
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

[axn]

Does this look right?

merit(p, n) = log(p) * (p-1) * p^(n-1);
find_count(p, t)=my(m); for(i=2, oo, m=merit(p, i); if(m > t, return(i-1)));
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()))

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

[R. Gerbicz]

Originally Posted by axn

Does this look right?

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 non-primes 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 p-1 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.

[axn]

Originally Posted by R. Gerbicz

I'm not sure what your code is doing

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 P-1. i.e. more bits = costlier. Less probable = less useful. This comes out as log(p) * (p-1) * p^(n-1) -> 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.

[tuckerkao]

Originally Posted by ixfd64

102646067 and 105144859 are two examples with such factors. P-1 cannot normally find these without the now-unsupported Brent-Suyama extension.

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 P-1 stages were sped up after Prime95 v30.5, so the larger bounds become more possible for the newer PCs.