Задача 175
Дроби, связанные с количеством различных способов записи числа в виде суммы степеней двойки
Определим f(0)=1 и f(n) как число способов записи n в виде суммы степеней двойки, где каждая степень встречается не более двух раз.

К примеру, f(10)=5, т.к. число 10 можно выразить 5 различными способами:
10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1

Можно показать, что для каждой дроби p/q (p>0, q>0) существует по крайней мере одно целое числоn, для которого
f(n)/f(n-1)=p/q.

К примеру, наименьшее значение n, при котором f(n)/f(n-1)=13/17, равно 241.
В двоичной форме записи это число 241 равно 11110001.
Читая это число от старшего бита к младшему, встречаем 4 единицы, 3 нуля и 1 единицу. Последовательность 4,3,1 будем называть сокращенным двоичным разложением числа 241.

Найдите сокращенное двоичное разложение для наименьшего значения n, при котором
f(n)/f (n-1)=123456789/987654321.

Ответ запишите в виде целых чисел, разделенных запятыми (без пробелов).
Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net