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)
- 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.