[Question]
  [
## 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](https://en.wikipedia.org/wiki/Zeckendorf's_theorem).
> 
> 
> 
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!
  
[Answer]
## 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 < 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 → 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](http://tigcc.ticalc.org/doc/gnuexts.html#SEC99a) to identify what parameters go where (by default, they go on the stack).
My [TI-89](http://en.wikipedia.org/wiki/TI-89_series), with its 10MHz processor, takes 5 minutes to run this function on 1 ­– 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?](http://meta.codegolf.stackexchange.com/questions/260/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.
[Answer]
## Javascript (142)
Only handles single input at a time. Because multi-line input is useless for JavaScript.
```
k=n=prompt(f=[a=b=1])|0;while((b=a+(a=b))<n)f.push(b);for(i=f.length,g=[];i--;)if(f[i]<=k)g.push(f[i]),k-=f[i];alert(n+': '+(n?g.join('+'):0))
```
<http://jsfiddle.net/EqMXQ/>
[Answer]
# C, 244 characters
```
#define P printf
int f[30];int main(){f[28]=f[29]=1;int i=28;for(;i>0;--i)f[i-1]=f[i+1]+f[i];int x;while(scanf("%i",&x)!=-1){P(x?"%i: ":"0: 0\n",x);if(x>0){int i=0,a=0;while(x>0){while(f[i]>x)++i;if(a++)P("+");P("%i",f[i]);x-=f[i];}P("\n");}}}
```
With whitespace:
```
#define P printf
int f[30];
int main(){
    f[28] = f[29] = 1;
    int i = 28;
    for(; i > 0; --i) f[i-1] = f[i+1] + f[i];
    int x;
    while(scanf("%i",&x) != -1) {
        P(x ? "%i: " : "0: 0\n",x);
        if(x > 0) {
            int i = 0, a = 0;
            while(x > 0) {
                while(f[i] > x) ++i;
                if(a++) P("+");
                P("%i",f[i]);
                x -= f[i];
            }
            P("\n");
        }
    }
}
```
This program will read numbers out of standard input and write to standard output.
[Answer]
## Golfscript, 43 chars
```
~]{:|': '[{0 1{|>!}{.@+}/;|1$-:|}do]'+'*n}%
```
I think this can probably be reduced by 3 to 5 chars with more effort. E.g. the unfold to then throw away the array feels wasteful.
[Answer]
## F# - 282 252 241 characters
```
let mutable d=int(stdin.ReadLine())
let q=d
let rec f x=if x<2 then 1 else f(x-2)+f(x-1)
let s x=
 d<-d-x
 x
printf"%d: %s"q (Core.string.Join("+",[for i in List.filter(fun x->x<d)[for i in 28..-1..0->f i]do if d-i>=0 then yield s i]))
```
[Answer]
## Python - 183 Chars
Majority of the code is handling multiple inputs :(
```
f=lambda a,b,n:b>n and a or f(b,a+b,n)
g=lambda n:n>0and"%d+%s"%(f(0,1,n),g(n-f(0,1,n)))or""
try:
 while 1:
  n=input()
  print "%d: %s"%(n,n<1and"0"or g(n).strip("+"))
except:0
```
[Answer]
# Mathematica 88
```
n = RandomInteger[10000, 10];
Print[k=#,For[i=99;l={},k>0,If[#<=k,k-=#;l~AppendTo~#]&@Fibonacci@i--];":"l~Row~"+"]&/@n
```
Example of output
```
3999: 2584+987+377+34+13+3+1
9226: 6765+1597+610+233+21
7225: 6765+377+55+21+5+2
9641: 6765+2584+233+55+3+1
6306: 4181+1597+377+144+5+2
4507: 4181+233+89+3+1
8848: 6765+1597+377+89+13+5+2
6263: 4181+1597+377+89+13+5+1
2034: 1597+377+55+5
6937: 6765+144+21+5+2
```
[Answer]
EXCEL : 89 chars in unique code:
![enter image description here](https://i.stack.imgur.com/qmhGa.png)
[Answer]
**Scala - 353 chars** (100 chars for handling multiple inputs)
```
def h(m:Int){lazy val f={def g(a:Int,b:Int):Stream[Int]=a #:: g(b,a+b);g(0,1);};if(m==0)println(m+": "+m)else{var s=0;var t= f.takeWhile(_ <= m);var w="";while(s!= m){s+=t.last;w+=t.last+"+";t=t.takeWhile(_<=m-s);};println(m+": "+w.take(w.length-1))}}
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))
```
[Answer]
# Python 3 (170 chars)
```
while 1:
 s=input()
 if not s:break
 s=n=int(s);f=[1];t=[]
 while f[-1]<n:f+=[sum(f[-2:])]
 for i in f[::-1]:
  if s>=i:s-=i;t+=[i]
 print(n,'=','+'.join(map(str,t))or 0)
```
Multiline input, stop on empty line
[Answer]
# C, 151 characters
```
main() {int i=1,n,f[30]={1,1};for(;i++<30;)f[i]=f[i-1]+f[i-2];while(scanf("%d",&n))for(i=30;;--i)if(f[i]<=n){printf("%d\n",f[i]);if(!(n-=f[i]))break;}}
```
readable version:
```
main() {
    int i=1,n,f[30]={1,1};
    for(;i++<30;)f[i]=f[i-1]+f[i-2];
    while(scanf("%d",&n))
        for(i=30;;--i)
            if(f[i]<=n) {
                printf("%d\n",f[i]);
                if (!(n-=f[i])) break;
            }
}
```
[Answer]
# R, 170
```
x=scan();Filter(function(i)cat(unlist(Map(function(d)if(i>=d&&i){i<<-i-d;d},rev(lapply(Reduce(function(f,x)c(f[2],sum(f)),1:94,c(0,1),F,T),head,n=1)))),sep='+',fill=T),x)
```
Handles multiple inputs and cat's the result to STDOUT
```
> x=scan();Filter(function(i)cat(unlist(Map(function(d)if(i>=d&&i){i<<-i-d;d},rev(lapply(Reduce(function(f,x)c(f[2],sum(f)),1:94,c(0,1),F,T),head,n=1)))),sep='+',fill=T),x)
1: 100
2: 200
3: 300
4: 
Read 3 items
89+8+3
144+55+1
233+55+8+3+1
numeric(0)
>
```
[Answer]
# R (460 chars)
Another version using R.  
Reading from file "input", output to the file "output"
```
d=as.list(as.integer(scan("input","",sep="\n")));n=36;f=rep(1,n);for(i in 3:n){f[i]=f[i-2]+f[i-1]};d2=lapply(d,function(x){a=vector("integer");i=1;while(x>0){id=which(f>=x)[1];if(x==f[id]){x=x-f[id];a[i]=f[id]}else{x=x-f[id-1];a[i]=f[id-1]}i=i+1}a});d=mapply(c,d,d2,SIMPLIFY=0);for(i in 1:length(d)){t=d[[i]];l=length(t);if(l==1){d[[i]]=paste(t[1],t[1],sep=": ")}else{d[[i]]=paste(t[1],": ",paste(t[2:l],collapse="+"),sep="")}}lapply(d,write,"output",append=1)
```
"input" example
```
0
47
3788
1646
25347
677
343
3434
```
"output" example
```
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
```
More readable version:
```
dt <- as.list(as.integer(scan(file = "input", what = "", sep = "\n")))
n <- 36
fib <- rep(1, n)
for(i in 3:n){fib[i] <- fib[i-2] + fib[i-1]}
dt2 <- lapply(dt, function(x){answ <- vector(mode = "integer")
                               i <- 1
                               while(x > 0){
                                   idx <- which(fib>=x)[1]
                                   if(x == fib[idx]){
                                       x <- x - fib[idx]
                                       answ[i] <- fib[idx]
                                   } 
                                   else {
                                       x <- x - fib[idx-1]
                                       answ[i] <- fib[idx-1]
                                   }
                                   i <- i + 1
                               }
                               answ})
dt <- mapply(FUN = c, dt, dt2, SIMPLIFY = FALSE)
for(i in 1:length(dt)){
    t1 <- dt[[i]]
    t1.len <- length(t1)
    if(t1.len == 1){
        dt[[i]] <- paste(t1[1], t1[1], sep=": ")
    } else {
        dt[[i]] <- paste(t1[1], ": ", paste(t1[2:t1.len], collapse = "+"), sep="")
    }
}
lapply(dt, write, "output", append=TRUE)
```
[Answer]
## D (196 chars)
Run with `rdmd --eval=…`. This conveniently hides the boilerplate of `import x, y, z;` and `void main() {…}`:
```
int f(int i){return i-->1?f(i--)+f(i):i+2;}int n;foreach(x;std.stdio.stdin.byLine.map!(to!int))writeln(x,": ",x?n=x,reduce!((r,i)=>f(i)<=n?n-=f(i),r~="+"~f(i).text:r)("",29.iota.retro)[1..$]:"0")
```
[Answer]
**Using Java**
```
package org.mindcraft;
import java.util.Scanner;
public class Fibbo {
    public static void main(String[] args) {
    String number = null;
    int tmp, sum;
    int i = 1, j = 1;
    Scanner in = new Scanner(System.in);
    number = in.nextLine();
    String[] arr = number.split(" ");
    for (int it = 0; it < arr.length; it++) {
        tmp = Integer.parseInt(arr[it]);
        String value = tmp+" : ";
        while (tmp > 0) {
            i = 1;
            j = 1;
            for (int k = 0; k < 10000; k++) {
                sum = i + j;
                if (sum > tmp) {
                    //if (value == null) {
                    char ch=value.charAt(value.length()-2);
                    if(ch==':')
                    {
                        value = value+" "+ j + "";
                    } else {
                        value = value + " + " + j;
                    }
                    tmp = tmp - j;
                    break;
                }
                i = j;
                j = sum;
            }
        }
        System.out.println(value);
    }
}
}
```
]