19
2
Challenge
In this task you would be given an integer N (less than 106), find the minimum way in which you could sum to N using only Fibonacci numbers - this partition is called Zeckendorf representation.
You could use any Fibonacci number more than once and if there is more than one representation output any.
For example if the input is 67 then one possible output could be using the Fibonacci numbers 1,3,8,55 which is also the minimum number of Fibonacci numbers that could be used to get the sum 67.
The input N is given on a single line, the inputs are terminated by EOF.
Examples
Given in the format input: output
0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2
Constraints
- The number of inputs would not exceed 106 values.
- Your program should not run more than 5 seconds for all inputs.
- You can use any language of your choice.
- Shortest solution wins!
Spoiler: Compute the Zeckendorf representation of a number and use that. – FUZxxl – 2015-03-02T14:33:32.967
"Your program should not run more than 5 seconds for all inputs." on what hardware? And how are you going to fund us to procure that hardware for testing? – Iszi – 2014-01-19T06:13:51.723
Relevant OEIS entry: A014417
– ბიმო – 2018-06-30T23:46:19.047"You could any Fibonacci number..." eh? "The number of inputs would not exceed 10^6 values." So we will never need to add more than 10^6 numbers together? Do you mean the sum of the inputs would not exceed 10^6? – mellamokb – 2011-05-26T22:01:14.453
7Spoilers: 1) The greedy algorithm (subtract largest Fibonacci number until input is zero) produces optimal solutions. 2) An optimal solution need not use a Fibonacci number twice (which follows from 1). 3) An optimal solution, for N <= 1000000, will have no more than 14 terms. – Joey Adams – 2011-05-26T23:28:47.817
6@Joey: More generally, the greedy algorithm decomposes positive integers into sums of distinct Fibonacci numbers such that consecutive Fibonacci numbers are not used (this is called Zeckendorf's theorem). – Nabb – 2011-05-27T11:14:22.327
1Spoiler 4: 29 terms of the Fibonacci sequence starting at 0 1 is sufficient. – Peter Taylor – 2011-05-27T15:12:14.023
@Nabb:Thanks for explaining the mathematics part. – Quixotic – 2011-05-27T19:05:05.473