9
\$\begingroup\$

Let us define the Fibonacci sequence as 

F(1) = 1

F(2) = 2

F(n) = F(n - 2) + F(n - 1)

So we have the infinite sequence 1,2,3,5,8,13,... It is well known that any positive integer can be written as a sum of some Fibonacci numbers. The only caveat is that this summation might not be unique. There is always at least one way to write a number as a sum of Fibonacci numbers but there may be many many more.

Your challenge is to write a complete program which using stdin takes in a positive integer between one and one million inclusive, and then outputs using stdout all possible summations of Fibonacci numbers which sum up to the input. In a summation, the Fibonacci numbers must not repeat and that includes the number 1. In any summation, if 1 is present, it must be present only once because in my definition of the sequence above 1 appears only once. Summations with only term are valid so if the input number is a Fibonacci number itself, then the number itself is a valid summation and must be printed. If multiple sums, then between any two sums there must be a blank line to easily distinguished between them.

Here are some samples.

./myfib 1
1

There is only one such sum and it has only term so that's all that is printed.

./myfib 2
2

Note here that 1+1 is not a valid sum because 1 repeats.

./myfib 3
1+2

3

Two sums and they are both printed with a blank line in between.

./myfib 10
2+8

2+3+5

./myfib 100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55

True code-golf. The shortest code in any language wins. Please post your code with some test cases (besides the one I gave above). In the case of ties, I pick the one with the highest upvotes after waiting at least for two weeks and probably longer. So the community please feel free to upvote any solutions you like. The cleverness/beauty of the code matters much more than who posts first.

Happy coding!

Improve this question
\$\endgroup\$
6
  • 2
    \$\begingroup\$ ...I'm just going to bruteforce this :P If I post an answer, don't expect it to perform well :) \$\endgroup\$
    – Doorknob
    Dec 18, 2013 at 2:34
  • \$\begingroup\$ Well it is code-golf not fastest-code. :-D \$\endgroup\$
    – Fixed Point
    Dec 18, 2013 at 2:35
  • 1
    \$\begingroup\$ I wrote it, and it actually runs fast :P \$\endgroup\$
    – Doorknob
    Dec 18, 2013 at 2:53
  • \$\begingroup\$ Not quite a duplicate, but closely related to codegolf.stackexchange.com/q/2677/194 \$\endgroup\$
    – Peter Taylor
    Dec 18, 2013 at 11:22
  • 1
    \$\begingroup\$ @shiona Since I didn't specify, pick your favorite one. :-) \$\endgroup\$
    – Fixed Point
    Dec 25, 2013 at 0:48

12 Answers 12

Reset to default
9
\$\begingroup\$

GolfScript, 54 characters

~1.{3$)<}{.@+}/<[[]]{{+}+1$%+}@/\{~)+{+}*!}+,{'+'*n.}/

Test it online or have a look at the examples:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Ruby, 118 114 (array output) or 138 134 (correct output)

i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
p (1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}

Sample run:

c:\a\ruby>fibadd
100
[[3, 8, 89], [1, 2, 8, 89], [3, 8, 34, 55], [1, 2, 3, 5, 89], [1, 2, 8, 34, 55], [3, 8, 13, 21, 55], [1, 2, 3, 5, 34, 55], [1, 2, 8, 13, 21, 55], [1, 2, 3, 5, 13, 21, 55]]

Change gets to $*[0] if you want command line arguments (>fibadd 100), +1 character though.

With the correct output:

i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
$><<(1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}.map{|o|o*?+}*'

'

Sample runs:

c:\a\ruby>fibadd
100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55
c:\a\ruby>fibadd
1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610
c:\a\ruby>obfcaps
12804
2+5+21+233+1597+10946

2+5+8+13+233+1597+10946

2+5+21+89+144+1597+10946

2+5+21+233+610+987+10946

2+5+21+233+1597+4181+6765

2+5+8+13+89+144+1597+10946

2+5+8+13+233+610+987+10946

2+5+8+13+233+1597+4181+6765

2+5+21+34+55+144+1597+10946

2+5+21+89+144+610+987+10946

2+5+21+89+144+1597+4181+6765

2+5+21+233+610+987+4181+6765

2+5+8+13+34+55+144+1597+10946

2+5+8+13+89+144+610+987+10946

2+5+8+13+89+144+1597+4181+6765

2+5+8+13+233+610+987+4181+6765

2+5+21+34+55+144+610+987+10946

2+5+21+34+55+144+1597+4181+6765

2+5+21+89+144+233+377+987+10946

2+5+21+89+144+610+987+4181+6765

2+5+21+233+610+987+1597+2584+6765

2+5+8+13+34+55+144+610+987+10946

2+5+8+13+34+55+144+1597+4181+6765

2+5+8+13+89+144+233+377+987+10946

2+5+8+13+89+144+610+987+4181+6765

2+5+8+13+233+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+10946

2+5+21+34+55+144+610+987+4181+6765

2+5+21+89+144+233+377+987+4181+6765

2+5+21+89+144+610+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+10946

2+5+8+13+34+55+144+610+987+4181+6765

2+5+8+13+89+144+233+377+987+4181+6765

2+5+8+13+89+144+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+4181+6765

2+5+21+34+55+144+610+987+1597+2584+6765

2+5+21+89+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+4181+6765

2+5+8+13+34+55+144+610+987+1597+2584+6765

2+5+8+13+89+144+233+377+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+1597+2584+6765

That last one (12804) only took about 3 seconds!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 89 85 chars

Shortened to 85 chars thanks to David Carraher.

i=Input[];#~Row~"+"&/@Select[If[#>i,Subsets@{##},#0[#+#2,##]]&[2,1],Tr@#==i&]//Column

Mathematica has a built-in function Fibonacci, but I don't want to use it.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Very compact. Nice. \$\endgroup\$
    – Dr. belisarius
    Dec 18, 2013 at 19:31
  • 1
    \$\begingroup\$ 76 chars if you don't mind printing as a list of sums:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &] \$\endgroup\$
    – DavidC
    Dec 19, 2013 at 1:01
  • 1
    \$\begingroup\$ 84 chars: i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &] // Column \$\endgroup\$
    – DavidC
    Dec 19, 2013 at 12:05
3
\$\begingroup\$

Scala, 171

def f(h:Int,n:Int):Stream[Int]=h#::f(n,h+n)
val x=readInt;(1 to x).flatMap(y=>f(1,2).takeWhile(_<=x).combinations(y).filter(_.sum==x)).foreach(z=>println(z.mkString("+")))
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You can save a few bytes by using val f:Stream[Int]=1#::f.scanLeft(2)(_+_) for the fibonacci sequence. \$\endgroup\$
    – corvus_192
    Oct 29, 2020 at 10:14
  • \$\begingroup\$ Also, please specify "Scala 2.10" as the programming language if you want to use readInt without an import. \$\endgroup\$
    – corvus_192
    Oct 29, 2020 at 10:20
  • \$\begingroup\$ You can also save a lot by using the infix operator syntax for methods: 1 to x flatMap(y=>f(1,2)takeWhile(_<=x)combinations(y)filter(_.sum==x))map(z=>println(z mkString "+")) \$\endgroup\$
    – corvus_192
    Oct 29, 2020 at 10:26
2
\$\begingroup\$

Python 206 181 characters

import itertools as a
i,j,v,y=1,2,[],input()
while i<1000000:v,i,j=v+[i],j,i+j
for t in range(len(v)+1):
 for s in a.combinations(v,t):
  if sum(s)==y:print "+".join(map(str,s))+"\n"

Sample Run:

25
1+3+21

1+3+8+13

1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Get rid of all those extra spaces.You can use one tab or space chars to indent code. Also writing the loop codes in single line when possible is shorter i.e while i<1000000:v+=[i];i,j=j,i+j \$\endgroup\$
    – Wasi
    Dec 23, 2013 at 16:23
  • \$\begingroup\$ Some suggestions (I didn't want to just plagiarize your answer and post my shortened version): import itertools as z, remove the newlines after the colons, put the y=input() in with the x,y,v line, and remove the extra space after the final if statement. \$\endgroup\$
    – SimonT
    Dec 23, 2013 at 20:28
  • \$\begingroup\$ I've included your suggestions in the code. Thanks :) \$\endgroup\$
    – batman
    Dec 24, 2013 at 13:34
2
\$\begingroup\$

C#, 376 bytes

class A{IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}static void Main(){new A().C(int.Parse(Console.ReadLine()));}}

Ungolfed:

class A
{
    IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}
    void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}
    static void Main(){new A().C(int.Parse(Console.ReadLine()));}
}

The method B returns an IEnumerable that represents the entire (infinite) Fibonacci set. The second method, given a number n, looks at the first n Fibonacci numbers (huge overkill here), finds all possible subsets (the power set), and then filters down to subsets whose sum is exactly n, and then prints.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL (75)

I←⎕⋄{⎕←⎕TC[2],1↓,'+',⍪⍵}¨S/⍨I=+/¨S←/∘F¨↓⍉(N⍴2)⊤⍳2*N←⍴F←{⍵,+/¯2↑⍵}⍣{I<⊃⌽⍺}⍳2

Less competitive than I'd like, mostly because of the output format.

Output:

⎕:
      100

 3 + 8 + 89 

 3 + 8 + 34 + 55 

 3 + 8 + 13 + 21 + 55 

 1 + 2 + 8 + 89 

 1 + 2 + 8 + 34 + 55 

 1 + 2 + 8 + 13 + 21 + 55 

 1 + 2 + 3 + 5 + 89 

 1 + 2 + 3 + 5 + 34 + 55 

 1 + 2 + 3 + 5 + 13 + 21 + 55

Explanation:

  • I←⎕: read input, store in I.
  • ⍳2: starting with the list 1 2,
  • {⍵,+/¯2↑⍵}: add the sum of the last two elements to the list,
  • ⍣{I<⊃⌽⍺}: until I is smaller than the last element of the list.
  • F←: store in F (these are the fibonacci numbers from 1 to I).
  • N←⍴F: store the amount of fibonacci numbers in N.
  • ↓⍉(N⍴2)⊤⍳2*N: get the numbers from 1 to 2^N, as bits.
  • S←/∘F¨: use each of these as a bitmask on F, store in S.
  • I=+/¨S: for each sub-list in S, see if the sum of it is equal to I.
  • S/⍨: select these from S. (Now we have all lists of fibonacci numbers that sum to I.)
  • {...}¨: for each of these:
    • ,'+',⍪⍵: add a + in front of each number,
    • 1↓: take the first + back off,
    • ⎕TC[2]: add an extra newline,
    • ⎕←: and output.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell - 127

After many iterations I ended up with the following code:

f=1:scanl(+)2f
main=getLine>>=putStr.a f "".read
a(f:g)s n|n==f=s++show f++"\n\n"|n<f=""|n>f=a g(s++show f++"+")(n-f)++a g s n

I could have saved maybe one character by cheating and adding an extra "0+" in front of every output line.

I want to share another version (length 143) I came up with while trying to golf the previous solution. I've never abused operators and tuples quite this much before:

f=1:scanl(+)2f
main=getLine>>=(\x->putStr$f€("",read x))
o%p=o++show p;(f:g)€t@(s,n)|n==f=s%f++"\n\n"|n<f=""|n>f=g€(s%f++"+",n-f)++g€t

Test cases, 256:

256
2+3+5+13+34+55+144

2+3+5+13+89+144

2+3+5+13+233

2+8+13+34+55+144

2+8+13+89+144

2+8+13+233

2+21+34+55+144

2+21+89+144

2+21+233

and 1000:

1000
2+3+8+21+34+89+233+610

2+3+8+55+89+233+610

2+3+8+144+233+610

2+3+8+377+610

2+3+8+987

5+8+21+34+89+233+610

5+8+55+89+233+610

5+8+144+233+610

5+8+377+610

5+8+987

13+21+34+89+233+610

13+55+89+233+610

13+144+233+610

13+377+610

13+987

Some efficiency data since someone had this stuff:

% echo "12804" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  0.09s user 0.00s system 96% cpu 0.100 total
% echo "128040" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  2.60s user 0.01s system 99% cpu 2.609 total
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

CJam, 42 40 bytes

-2 bytes by converting each list from base 1 to calculate its sum instead of using :+. (This saves no bytes by itself, but this method works on the empty set, so it no longer needs to be discarded from the list of lists.)

XY{_2$+}qi:T*]La\{1$f++}/{1bT=},{'+*}%N*

Try it online!

This takes a long time to calculate for large numbers because it generates input + 2 Fibonacci numbers (to ensure that every number less than or equal to the input is included)...but hey, it saves 4 bytes over using a proper while loop.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 19 bytes (Non-competing)

ÅFævy©O¹Qi®'+ý}})ê»

Try it online!

Calculates all possible sums for any given n. Example output for 1000:

1+1+3+8+144+233+610
1+1+3+8+21+34+89+233+610
1+1+3+8+377+610
1+1+3+8+55+89+233+610
1+1+3+8+987
13+144+233+610
13+21+34+89+233+610
13+377+610
13+55+89+233+610
13+987
2+3+8+144+233+610
2+3+8+21+34+89+233+610
2+3+8+377+610
2+3+8+55+89+233+610
2+3+8+987
5+8+144+233+610
5+8+21+34+89+233+610
5+8+377+610
5+8+55+89+233+610
5+8+987
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You need 2 newlines between each line of output. \$\endgroup\$
    – Shaggy
    Oct 29, 2020 at 10:21
0
\$\begingroup\$

Japt, 21 bytes

õ!gM Åà f@¶Xxîq+ÃqR²

Try it

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Husk, 22 20 bytes

ṁȯeøJ'+msufo=¹ΣṖt↑İf

Try it online!

-2 bytes with an empty list trick.

Explanation

moJ'+msufo=¹ΣṖt↑İf
               ↑İf Take input number of fibonacci numbers
              t    remove first 1
             Ṗ     get it's powerset
        fo         filter the sublists by the following:
          =¹Σ      sum equals input?
       u           uniquify it
mo                 map each sublist to
     ms            it's elements as strings
  J'+              Joined by '+'
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You need 2 newlines between each line of output. \$\endgroup\$
    – Shaggy
    Oct 29, 2020 at 10:00
  • \$\begingroup\$ @Shaggy Should work now. (I kinda followed the 05AB1E answer on the output) \$\endgroup\$
    – Razetime
    Oct 29, 2020 at 10:03
  • \$\begingroup\$ I've let them know, too, so. \$\endgroup\$
    – Shaggy
    Oct 29, 2020 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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