Project Euler 110 - Diophantine Reciprocals II
Official link: https://projecteuler.net/problem=110
This is a harder version of Problem 108
Note: I am unhappy with my solution as I just completely brute forced the problem
Thought Process
Same as Problem 108
This problem cannot be brute forced in the same way as Problem 108, and to be honest I was unable to come up with an elegant solution. I did a 14 times nested loop (Yes, I know it's disgusting) limiting each exponent by the fact that
Product of first 15 primes = 614889782588491410
log(614889782588491410, 2) ~ 60, This means that 2^60 is the largest exponent of 2 but this only have 121 divisors so we need other factors
log(614889782588491410, 2*3) ~ 23, let's assume maximum is 2^59 * 3^22 (which is too big but doesn't matter) way to little divisors again so we need another factors
log(614889782588491410, 2*3*5) ~ 12, same as before. By doing this for all 15 exponents and setting up breaks should we go over our current minimum (start at 614889782588491410) I can solve the problem ~ 80 seconds
Interactive Code
No interactive code for this problem, my very ugly code is given below