// ////////////////////////////////////////////////////////
// # Title
// Writing 1/2 as a sum of inverse squares
//
// # URL
// https://projecteuler.net/problem=152
// http://euler.stephan-brumme.com/152/
//
// # Problem
// There are several ways to write the number `1/2` as a sum of inverse squares using distinct integers.
//
// For instance, the numbers { 2,3,4,5,7,12,15,20,28,35 } can be used:
//
// `dfrac{1}{2} = dfrac{1}{2^2} + dfrac{1}{3^2} + dfrac{1}{4^2} + dfrac{1}{5^2} + dfrac{1}{7^2} + dfrac{1}{12^2} + dfrac{1}{15^2} + dfrac{1}{20^2} + dfrac{1}{28^2} + dfrac{1}{35^2}`
//
// In fact, only using integers between 2 and 45 inclusive, there are exactly three ways to do it, the remaining two being:
// { 2,3,4,6,7,9,10,20,28,35,36,45 } and { 2,3,4,6,7,9,12,15,28,30,35,36,45 }.
//
// How many ways are there to write the number `1/2` as a sum of inverse squares using distinct integers between 2 and 80 inclusive?
//
// # Solved by
// Stephan Brumme
// September 2017
//
// # Algorithm
// This problem would be extremely easy if we had less numbers. Nevertheless, the search works always the same:
// - try each combination of input values
// - use backtracking to add (and ignore) terms step-by-step:
// - if not all terms added yet but the sum already exceeds 1/2 then go back
// - if not all terms added yet but the sum is so small that it stays below 1/2 even if add all of the not-yet-analyzed values then go back
// ==> that's essentially how the function ''search()'' works
//
// Unfortunately this concept can solve the problem for `n = 45`. Therefore I have to find a clever way how I can skip some numbers.
// - the first observation is that the final denominator has to be 2 (and the numerator must be 1)
// - each denominator can be factored into prime numbers, they all "have to be gone", except for a single 2 of course
//
// If I have a (partial) sum `dfrac{a}{b}` then adding a single term `dfrac{1}{x^2}`:
// (1) `dfrac{a}{b} + dfrac{1}{x^2} = dfrac{a x^2 + b}{b x^2}`
//
// If `b` is coprime to `x^2` (which implies coprime to `x`) then I need to add at least one more term to get rid of `x^2`.
// That's a very helpful observation because adding `1 / 41^2` now is impossble - there is just no other term that also has prime factor 41.
// So the 41 would be stuck in the denominator - which is not allowed, there must be a single 2 at the end.
// The same can be said for all prime numbers `p > 80/2` which removes { 41,43,47,53,59,61,67,71,73,79 } from the list of candidates.
//
// Manual calculation showed that even 37 is "forbidden": the only remaining number with the same prime factor is 74.
// `1 / 37^2 + 1 / 74^2 = 5/5476` but `5476 = 2^2 * 37^2` (I asked Wolfram Alpha). So the 37 is still left in the denominator ...
// Then I wrote code to check for each prime number any combination of its multiples, e.g. for `p = 11` I checked all `2^7 = 128` combinations of { 11,22,33,44,55,66,77 }.
// and looked for a combination where the sum is not a multiple of the prime anymore ("sum mod prime != 0").
// This check is too slow for the primes 2 and 3 because there are `2^{floor{80/2}} = 2^40` or `2^{floor{80/3}} = 2^26` combinations.
// I just assumed that any number which has only prime factors 2 and/or 3 is "relevant".
//
// The output was astonishing: 11 and all prime numbers above 13 are "forbidden".
// The list of candidates can be reduced to all numbers whose prime factors are { 2,3,5,7,13 } and contains these 39 numbers:
// { 2,3,4,5,6, 7,8,9,10,12, 13,14,15,16,18, 20,21,24,27,28, 30,32,35,36,39, 40,42,45,48,52, 54,56,60,63,64, 65,70,72,80 }
//
// Looking at `2^39 approx 55 * 10^10` different combinations is a lot but manageable.
// Especially the optimizations mentioned at the beginning reduce this number considerably and I found the correct result in a bit more than 1 minute.
//
// Then I remembered the "trick" from problem 266 which I solved a few weeks ago:
// if pre-compute the sum of each subset of the highest numbers (''x > 40'' turns out to be a good choice) and store them in a container ''lastNumbers''
// then I can stop my search after reaching that threshold and lookup in ''lastNumbers'' how often the difference `dfrac{1}{2} - current` can be found.
// Now the program finishes after 0.3 seconds !
//
// # Note
// I kept track of the numbers actually used in all sums and it turns out 8 numbers were "useless": { 16,27,32,48,54,64,65,80 }
// With this "optimal" input set the program becomes twice as fast and finishes after 0.13 seconds.
//
// The "optimal" input set reveals an interesting pattern if I write down the prime factorization:
//{ `2^4`, `3^3`, `2^5`, `2^4 * 3`, `2 * 3^3`, `2^6`, `5 * 13`, `2^4 * 5` }
// I don't fully understand why all multiples of `2^4` and `3^3` are "useless" - but apparently there is a good reason.
//
// The ''Fraction'' class is part of my [toolbox](../toolbox/#fractions) and can add fractions, reduce them, etc.
// Some numbers becomes huge (before being reduced to a proper fraction) and I need GCC's 128 bit integer to find the correct result.
// That means my code doesn't compile with Visual C++.
//
// I could remove the ''members'' containers because it's only useful during debugging (to print exactly which solutions were found).
// But this problem was surprisingly hard and I just glad I solved it so I leave the code "as is". Well, I added a few comments afterwards.
// With over 300 lines it's one of my longest solutions, see [Code Metrics](../performance/#codemetrics).
//
// # Alternative
// If you multiply all fractions by `lcm(2,3,4,...,80)` then you don't need fractions at all.
//
// # Hackerrank
// The result doesn't need to be 1/2, it can be any number.
// And the number of terms can be changed which causes some problems because then even my 128 bit integers overflow.
// In the end about one third of all test cases are correct, one third times out and one third causes overflows.
#include
#include
#include
#include
#include