def dec_to_fib(n)
    # Minimum amount of 1s
    a=[1,1];a=[a[0]+a[1]]+a while a.inject(:+)<n
    a.inject(""){|s,c|v=(c<=n) ? 1:0;n-=c*v;s+v.to_s}
end
 
def dec_to_fib2(n)
    # Maximum amount of 1s
    a=[1,1];a=[a[0]+a[1]]+a while a.inject(:+)<n
    a.inject(""){|s,c|v=(c-1<n) ? 1:0;n-=c*v;s+v.to_s}
end 
 
def fib_to_dec(s)
    a=[1,1];a=[a[0]+a[1]]+a while a.length<s.length
    (0..s.length-1).inject(0){|n,i|n+s[i].to_i*a[i]}
end
 
for i in Array[8, 16, 32, 9024720]
	print i, " (minimal) -> ", dec_to_fib(i) , "\n"
	print i, " (maximal) -> ", dec_to_fib2(i), "\n"
end
 

ZGVmIGRlY190b19maWIobikKICAgICMgTWluaW11bSBhbW91bnQgb2YgMXMKICAgIGE9WzEsMV07YT1bYVswXSthWzFdXSthIHdoaWxlIGEuaW5qZWN0KDorKTxuCiAgICBhLmluamVjdCgiIil7fHMsY3x2PShjPD1uKSA/IDE6MDtuLT1jKnY7cyt2LnRvX3N9CmVuZAoKZGVmIGRlY190b19maWIyKG4pCiAgICAjIE1heGltdW0gYW1vdW50IG9mIDFzCiAgICBhPVsxLDFdO2E9W2FbMF0rYVsxXV0rYSB3aGlsZSBhLmluamVjdCg6Kyk8bgogICAgYS5pbmplY3QoIiIpe3xzLGN8dj0oYy0xPG4pID8gMTowO24tPWMqdjtzK3YudG9fc30KZW5kIAoKZGVmIGZpYl90b19kZWMocykKICAgIGE9WzEsMV07YT1bYVswXSthWzFdXSthIHdoaWxlIGEubGVuZ3RoPHMubGVuZ3RoCiAgICAoMC4ucy5sZW5ndGgtMSkuaW5qZWN0KDApe3xuLGl8bitzW2ldLnRvX2kqYVtpXX0KZW5kCgpmb3IgaSBpbiBBcnJheVs4LCAxNiwgMzIsIDkwMjQ3MjBdCglwcmludCBpLCAiIChtaW5pbWFsKSAtPiAiLCBkZWNfdG9fZmliKGkpICwgIlxuIgoJcHJpbnQgaSwgIiAobWF4aW1hbCkgLT4gIiwgZGVjX3RvX2ZpYjIoaSksICJcbiIKZW5kCg==