_{This problem is a programming version of Problem 175 from projecteuler.net}

Define and to be the number of ways to write as a sum of powers of 2 where no power occurs more than twice.

For example, since there are five different ways to express 10:

It can be shown that for every fraction (, ) there exists at least one integer such that .

For instance, the smallest for which is .

The binary expansion of is .

Reading this binary number from the most significant bit to the least significant bit there are one's, zeroes and one. We shall call the string the Shortened Binary Expansion of .

Find the Shortened Binary Expansion of the smallest for which