The minimum fibonacci challenge! 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!
Motorola 68000 assembly - 34 bytes

(GNU assembler syntax)

| short min_fib_partition(long N asm("%d2"), long *out asm("%a0"))
min_fib_partition:
    | Generate Fibonacci numbers on the stack (-1, 1, 0, 1, 1, 2, 3, ..., 1134903170).
    moveq #-1, %d0          | A = -1
    moveq #1, %d1           | B = 1
generate_loop:
    move.l %d0, -(%sp)      | Push A to the stack.
    exg.l %d0, %d1          | A' = B
    add.l %d0, %d1          | B' = A + B
    bvc.s generate_loop     | Stop when signed long overflows.

    | Go back up the stack, partitioning N using the greedy algorithm.
    moveq #0, %d0           | Initialize return value (number of terms).
subtract_loop:
    move.l (%sp)+, %d1      | Pop a Fibonacci number F off the stack.
    cmp.l %d1, %d2          | If N &lt; F, continue to smaller Fibonacci number.
    blt.s subtract_loop
    addq.w #1, %d0          | Increment the term count.
    move.l %d1, (%a0)+      | Append F to the output array.
    sub.l %d1, %d2          | N -= F
    bne.s subtract_loop     | Continue if N has not yet reached zero.

    | Clear the stack by searching for that -1.
clear_stack_loop:
    tst.l (%sp)+
    bge clear_stack_loop

done:
    rts


36 &rarr; 34: Made Fibonacci generator stop on overflow rather than by counting, and fixed the 0 case so it outputs [0] rather than [].  However, passing a negative N crashes now.

The comment at the top is the C prototype of this function, using a language extension to identify what parameters go where (by default, they go on the stack).

My TI-89, with its 10MHz processor, takes 5 minutes to run this function on 1 ­&ndash; 1,000,000.

Although the machine code is (currently) fewer bytes than the GolfScript solution, it would probably be unfair to accept this as the shortest solution because:


Machine code is normally not counted as "source code".  Unlike source code, machine code usually has high symbol complexity and, more importantly, is unprintable.  See "Should executable binaries be considered a reasonable solution for code-golf?".
This solution only takes a single number as input, rather than multiple inputs.
This solution is a function, not a program.


If you have a TI-89/92/V200, you can download the full project here (outdated):

https://rapidshare.com/files/154945328/minfib.zip

Good luck coaxing RapidShare to give you the actual file.  Does anyone know of a good host for files this big?  8940 is an awful lot of bytes.