After a factor is found it keeps on going

[jocelynl]

Hi George,

When I use FactorOverride, even if a factor is found, prime95 keep on going up to the override. I don't know if it's a bug or if it was intentionnally added. I heard of someone reporting 2 factors on the same number. I'm using 23.4.1


Joss

[S80780]

Hi, Joss!

AFAIK, this is due to the fact that Prime95 doesn't go through the factor - candidates in their natural order. So, if a factor is found, Prime95 checks smaller left-overs to ensure that there aren't any factors below that.
Nevertheless, finding a factor below e.g. 2^60 should ensure that Prime95 won't look for factors between 2^60 and 2^61.

Benjamin

[cheesehead]

In the Prime95 module source code commonb.c, where it determines that trial factoring has found a factor is this comment:

Originally Posted by source code commonb.c

/* We used to continue factoring to find a smaller factor in a later pass. */
/* However, there was a bug - restarting from the save file skipped the */
/* further factoring AND the time it takes to search for smaller factors */
/* is getting longer and longer as we factor deeper and deeper. Therefore, */
/* in version 20 I've elected to no longer search for smaller factors. */
/* The one exception is users that are using FactorOverride to locate */
/* small factors. */

Following that comment, there's a test on the FactorOverride value. If FactorOverride is 60 or less, then the program drops into the former default behavior of continuing until all 16 passes for that bit limit are done. For FactorOverride = 61 or greater, or if FactorOverride has not been specified, there is no such continuation.

[markr]

I'm not sure prime95 is working like that. For example, if I factor M29900009 from a very low limit to a FactorOverride of 60 or less, prime95 reports a 44-bit factor 8938129290407. But if FactorOverride is 61 or more, it reports a 33 bit factor 7415202233 as well, which is the one in nofactor.

I stumbled across this because I became interested in hunting for missed factors, like in this thread. I experimented with looking for gaps in the distribution of known factors. Unfortunately large sections have many exponents where a factor is known but a smaller factor has been missed, which distorts the distribution. So I wanted to see if it was feasible to fix that first, at least up to a low bit-level.

[1997rj7]

Yes, it appears to work exactly the opposite of what the comment says. If FactorOverride is 60 or less, it stops upon finding a factor, but if it is 61 or greater, it continues to check all lower possible factors in that bit range.

[Prime95]

I'll fix it next release. Thanks

[markr]

Thanks, George!