Talk:Euclid-Mullin sequence

Question re Pollard's Rho

Suppose for some large number 'n' Pollard's Rho returns a factor 'f'.

Is it safe to assume that the smallest prime factor of 'n' will be 'f' or, if 'f' is not prime, the smallest prime factor of 'f'? This is what the Java entry seems to be assuming and is able to find the first 27 Euclid-Mullin numbers quite quickly as a result. The Perl and Sidef entries are also able to find the first 27 but they're calling library functions so I don't know what underlying techniques are being used.

Previously, I'd assumed that it wasn't safe to assume this and that you should also check prime factors of 'n/f' to see whether there's an even smaller one. However, the trouble with this is that when looking for the 20th E-M number, Pollard's Rho quickly finds that "1313797957" is a factor but is then unable (at least in a reasonable time) to factorize the remainder of "1088109629419974537540264093827255854360603780152501082413223".

As far as my Wren GMP entry is concerned, I've found a way around this though it still takes over 9 minutes to find the first 27. If I make the same assumption as the Java entry, the runtime comes down to 45 seconds so I thought it was worth asking whether anyone knows whether this is a safe assumption (given the way PR works) or it just happens to come up with the correct answers for this particular task. --PureFox (talk) 13:05, 21 July 2023 (UTC)

I suppose it depends on the implementation, but in general, no, you shouldn't rely on the assumption that factors will be found in magnitude order. Smaller factors are much more likely to be found earlier, but you can't rely on that being the case in general. --Thundergnat (talk) 13:57, 21 July 2023 (UTC)

Yeah, it's a pity but I'm sure you're right that we can't rely on a simple implememtation finding factors in magnitude order, so thanks for confirming that. Much as I love PR, you're stuffed on time if there are no smallish factors as seems to be the case with the above 61 digit number. I'll try and get my 9 minute version (which avoids a second round of PR) into shape for posting. --PureFox (talk) 15:14, 21 July 2023 (UTC)

Managed to reduce the runtime to 6 minutes 17 seconds - basically I'm just using trial division to see if there's a smaller factor rather than risk getting stuck on a second round of PR. Not exactly efficient but good enough for now. --PureFox (talk) 09:23, 23 July 2023 (UTC)

Looks like the 27th element is the first where Pollard's Rho doesn't find the lowest factor? --Tigerofdarkness (talk) 14:04, 24 July 2023 (UTC)

Yes, it's the first one where the number PR returns (169920526093) is non-prime. However, its prime factors are [159227, 1067159], the first one of these is found quite quickly by trial division and the 'n/f' calculation fails to find an even smaller one.

Incidentally, I've tried to factorize the 61 digit number in isolation but so far without success. I thought Fermat's method might work if the factors were close together but it didn't and ECM still hadn't found a factor after 17 minutes when I aborted it. --PureFox (talk) 16:06, 24 July 2023 (UTC)