19
\$\begingroup\$

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!
\$\endgroup\$
  • \$\begingroup\$ "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? \$\endgroup\$ – mellamokb May 26 '11 at 22:01
  • 7
    \$\begingroup\$ Spoilers: 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. \$\endgroup\$ – Joey Adams May 26 '11 at 23:28
  • 6
    \$\begingroup\$ @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). \$\endgroup\$ – Nabb May 27 '11 at 11:14
  • 1
    \$\begingroup\$ Spoiler 4: 29 terms of the Fibonacci sequence starting at 0 1 is sufficient. \$\endgroup\$ – Peter Taylor May 27 '11 at 15:12
  • \$\begingroup\$ @Nabb:Thanks for explaining the mathematics part. \$\endgroup\$ – Quixotic May 27 '11 at 19:05

15 Answers 15

16
\$\begingroup\$

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 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 ­– 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:

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.

\$\endgroup\$
  • \$\begingroup\$ You could add a fourth point to the list: the solution doesn't give the output in the correct format :P I'm using 7 characters on string literals alone. BTW Do you return the list [0] for input 0? It looks to me that you return the empty list. It's an irritating special case. \$\endgroup\$ – Peter Taylor May 27 '11 at 6:11
  • \$\begingroup\$ @Peter Taylor: You're right, I missed that. I got terms and term counts mixed up. I'll post a fix soon. \$\endgroup\$ – Joey Adams May 27 '11 at 6:51
5
\$\begingroup\$

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/

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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]))
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can you put the n=input() at the end of the previous line? \$\endgroup\$ – mbomb007 Feb 26 '15 at 22:10
  • \$\begingroup\$ I suppose so. :\ \$\endgroup\$ – st0le Feb 27 '15 at 18:55
  • \$\begingroup\$ You can also save a character by removing the space after print \$\endgroup\$ – mbomb007 Feb 27 '15 at 19:07
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

EXCEL : 89 chars in unique code:

enter image description here

\$\endgroup\$
1
\$\begingroup\$

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)))
\$\endgroup\$
  • \$\begingroup\$ Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line))) could be shortened to io.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l))) to save 40-ish characters. \$\endgroup\$ – Gareth May 31 '11 at 14:13
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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;
            }
}
\$\endgroup\$
1
\$\begingroup\$

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)
>
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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")
\$\endgroup\$
0
\$\begingroup\$

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);
    }
}
}
\$\endgroup\$
  • \$\begingroup\$ This is code golf, so make sure to golf your answer. \$\endgroup\$ – KSFT Feb 27 '15 at 13:51
  • 1
    \$\begingroup\$ Welcome to PPCG! As KSFT said, this is a code-golf challenge. Please show some effort in answering this question in as few bytes of code as possible. At the very least, you can remove unnecessary whitespace and use single-letter class/method/variable names. After doing this, please also include the byte count in your answer. \$\endgroup\$ – Martin Ender Feb 27 '15 at 14:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.