Thought Process

This was a very simple problem, all you need as a hint is to let x = 2^t.

The equation becomes: x^2 - x - k = 0, which we can easily solve with our quadratic formula, which gives us t = log2(1 + sqrt(1 + 4k)) - 1.

In our case we need 2^t to be an integer, which means that sqrt(1 + 4k) must be an integer and hence 1 + 4k must be a square.

1. Loop through squares, a^2

   1. If a^2 - 1 is divisible by 4, we have found a suitable k

      1. Using k compute t

         1. If t is an integer we have found a perfect partition

         2. Otherwise we have just found a regular partition

Keep track of the perfect and regular partitions until you reach the desired fraction.