Project Euler 110 - Diophantine Reciprocals II

Official link:

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

  1. Product of first 15 primes = 614889782588491410

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

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

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