yaworsw/euler-manager

---
:id: 175
:name: Fractions involving the number of different ways a number can be expressed
  as a sum of powers of 2
:url: https://projecteuler.net/problem=175
:content: "\r Define f(0)=1 and f(<var>n</var>) to be the number of ways to write
  <var>n</var> as a sum of powers of 2 where no power occurs more than twice.   \n
  \ \nFor example, f(10)=5 since there are five different ways to express 10:  \n10
  = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1  \n  \nIt can be shown that for every
  fraction <var>p/q</var> (<var>p</var>\\>0, <var>q</var>\\>0) there exists at least
  one integer <var>n</var> such that  \n f(<var>n</var>)/f(<var>n</var>-1)=<var>p/q</var>.
  \ \n  \nFor instance, the smallest <var>n</var> for which f(<var>n</var>)/f(<var>n</var>-1)=13/17
  is 241.  \nThe binary expansion of 241 is 11110001.  \nReading this binary number
  from the most significant bit to the least significant bit there are 4 one's, 3
  zeroes and 1 one. We shall call the string 4,3,1 the Shortened Binary Expansion
  of 241.  \n  \nFind the Shortened Binary Expansion of the smallest <var>n</var>
  for which  \n f(<var>n</var>)/f(<var>n</var>-1)=123456789/987654321.  \n  \nGive
  your answer as comma separated integers, without any whitespaces.\n"