This problem is the same as Problem 108, except we now need to find the first value of n that has more than 4 million solutions in the equation...
Using the same method that I employed for 108 doesn't work that well because it takes so long to complete that I'd have grown old and died before I got the answer. It was clear from the outset that I needed a better solution.
I started from the idea that...
Here are the facts that I used to work out my solution...
- If d(n2) is the number of divisors of n2, then [d(n2) + 1] / 2 is the number of different solutions to n2 = ab and hence also the number of different solutions to the equation that we are trying to solve.
- Since n2 is a square number, we know that it must have an odd number of divisors.
- If n2 has a prime factorisation p1s1 . p2s2 . p3s3 ... then d(n2) = (s1+1) . (s2 + 1) . (s3 + 1) ...
- The exponents in the prime factorisation of n2 are each [prime factor of d(n2) - 1]
This means that we can work out n2 for a given number of solutions by doing the prime factorisation of d(n2) and then using each of the prime factors as the exponents in the formula n2 = p1s1 . p2s2 . p3s3 ...
So here's the plan...
- Since we are looking for values of n that have more than 4 million solutions, we are interested in values of d(n2) that are i) odd and ii) greater than 8 million.
- For d(n2) in the range 8000001 to *randomly guessed upper limit* take each of the odd values.
- For each value in the range find the prime factorisation.
- Assuming that the values of pi in n2 = p1s1 . p2s2 . p3s3 ... are the sequential prime numbers (2,3,5,7...) and getting the values for si by subtracting 1 from each of the factors found in step 3, calculate n2.
- Try to calculate the square root of n2.
- Curse the world and everything in it when you discover that some values of n2 are too large to convert to a float in order to find the square root.
- Reason that since we're looking for the relatively small values of n then it is likely that if a value is too large to calculate then it probably isn't the one that we are looking for.
- Modify code so that it only tries to calculate the square root if n2 is less than *randomly guessed very large number*.
- Realise that since n has to be small enough to fit in the answer box on the Project Euler problem page, it must be less than 1027 so n2 < 1052.
- Congratulate self on cleverness.
- Get the answer.
- Read the discussion thread for this problem and bang your head against the table when you realise that you've devised an overly complicated, hacked together method for achieving what some other people have done in a freaking spreadsheet in half an hour of their spare time.
Yes, I have the answer. No, it isn't a pretty solution. It relies on a whole load of guesswork that could be done away with if I had the wits to do a proper analysis of the problem. How do I know that there isn't some value of n that is less than my answer but has more solutions than those I've checked for? Well, I don't. In fact, my first few guesses for the limit in step 2 were far too low and this wasted hours of my time. Also, how do I know that the bases in the prime factorisation of n2 are the sequential prime numbers (2,3,5,7...) and not something like (2,3,7,11...)? All I can say is that it seemed like a good idea at the time.