Zeckendorf's theorem shows that every positive integer can be uniquely represented as a sum of non-adjacent Fibonacci numbers. In this challenge, you have to compute the sum of two numbers in Zeckendorf representation.

Let Fn be the n-th Fibonacci number where

F1 = 1,
F2 = 2  and
for all k > 2, Fk = Fk - 1 + Fk - 2.

The Zeckendorf representation Z(n) of a non-negative integer n is a set of positive integers such that

n = Σi ∈ Z(n) Fi  and
i ∈ Z(n) i + 1 ∉ Z(n).

(in prosa: the Zeckendorf representation of a number n is a set of positive integers such that the Fibonacci numbers for these indices sum up to n and no two adjacent integers are part of that set)

Notably, the Zeckendorf representation is unique. Here are some examples for Zeckendorf representations:

Z(0) = ∅ (the empty set)
Z(1) = {1}
Z(2) = {2}
Z(3) = {3} ({1, 2} is not the Zeckendorf representation of 3)
Z(10) = {5, 2}
Z(100) = {3, 5, 10}

In this challenge, Zeckendorf representations are encoded as bit sets where the least significant bit represents if 1 is part of the set, etc. You may assume that the Zeckendorf representations of both input and output fit into 31 bits.

Your task is to compute Z(n + m) given Z(n) and Z(m). The solution with the shortest length in octets wins.

You can find a reference implementation written in ANSI C here. It can also be used to generate Zeckendorf representations or compute a number from its Zeckendorf representation.

Here are some pairs of sample input and output, where the first two columns contain the input and the third column contains the output:

73865           9077257         9478805
139808          287648018       287965250
34              279004309       279004425
139940          68437025        69241105
272794768       1051152         273846948
16405           78284865        83888256
9576577         4718601         19013770
269128740       591914          270574722
8410276         2768969         11184785
16384           340             16724
  • 4
    \$\begingroup\$ Could you please elaborate the Input/Output? \$\endgroup\$ – flawr Aug 5 '15 at 19:02
  • \$\begingroup\$ @flawr Please have a look at the provided reference implementation. You can use it to generate your own sample input. \$\endgroup\$ – FUZxxl Aug 5 '15 at 19:13
  • 3
    \$\begingroup\$ I'd be happy if you could document here exactly what you want and provide some examples, as I am, and perhaps others are too, not fluent in C. \$\endgroup\$ – flawr Aug 5 '15 at 20:12
  • \$\begingroup\$ I disagree with the uniqueness argument. Since the Fibonacci sequence starts with 1, 1, 2 you can clearly decompose 3 into F0 + F2 = 1 + 2 = 3. F0 and F2 are not adjacent. \$\endgroup\$ – orlp Aug 5 '15 at 21:11
  • 1
    \$\begingroup\$ @orlp The Fibonacci sequence defined here starts with F1=1 and F2=2. So the way I read it, F0 from your definition is not part of the sequence used here. \$\endgroup\$ – Reto Koradi Aug 5 '15 at 21:47

CJam, 76 74 70 63 59 bytes


Try it online in the CJam interpreter or verify all test cases at once.


We start by defining a minor variation of the sequence in the question:

G-2 = 0
G-1 = 1
Gk = Gk-1 + Gk-2 whenever k is a non-negative integer

This way, the bit 0 (LSB) of the bit arrays input or output corresponds to the Fibonacci number G0 and, in general, the bit k to Gk.

Now, we replace each set bit in Z(n) and Z(m) by the index it encodes.

For example, the input 53210 = 10000101002 gets transformed into [2 4 9].

This yields two arrays of integers, which we can concatenate to form a single one.

For example, if n = m = 100, the result is A := [2 4 9 2 4 9].

If we replace each k in A by Gk and add the results, we obtain n + m = 200, so A is a way to decompose 200 into Fibonacci numbers, but certainly not the one from Zeckendorf's theorem.

Keeping in mind that Gk + Gk+1 = Gk+2 and Gk + Gk = Gk + Gk-1 + Gk-2 = Gk+1 + Gk-2, we can substitute consecutive and duplicated indexes by others (namely, (k, k + 1) by k + 2 and (k, k) by (k + 1, k - 2)), repeating those substitutions over and over until the Zeckendorf representation is reached.1

Special case has to be taken for resulting negative indexes. Since G-2 = 0, index -2 can simply be ignored. Also, G-1 = 0 = G0, so any resulting -1 has to be replaced by 0.

For our example A, we obtain the following (sorted) representations, the last being the Zeckendorf representation.

[2 2 4 4 9 9] → [0 3 4 4 9 9] → [0 5 4 9 9] → [0 6 9 9] → [0 6 7 10] → [0 8 10]

Finally, we convert back from array of integers to bit array.


2             e# Push a 2 we'll need later.
q~            e# Read and evaluate the input.
{             e# For each integer I in the input:
  32{         e#   Filter [0 ... 31]; for each J:
    2\#       e#     Compute 2**J.
    I&        e#     Compute its logical AND with I.
  },          e#   Keep J if the result in truthy (non-zero).
}fI           e#
+             e# Concatenate the resulting arrays.
32_,*         e# Repeat [0 ... 31] 32 times.
{             e# For each K:
  WUer        e#   Replace -1's with 0's.
  $           e#   Sort.
  Kf-         e#   Subtract K from each element.
  [UU]/[-2X]* e#   Replace subarrays [0 0] with [-2 1].
  2,/2a*      e#   Replace subarrays [0 1] with [2].
  Kf+         e#   Add K to each element.
}fK           e#
f#            e# Replace each K with 2**K.
1b            e# Cast all to integer (discards 2**-2) and sum.

1 The implementation attempts substituting 32 times and does not check if the Zeckendorf representation has in fact been reached. I do not have a formal proof that this is sufficient, but I've tested all possible sums of 15-bit representations (whose sums' representations require up to 17 bits) and 6 repetitions was enough for all of them. In any case, augmenting the number of repetitions to 99 is possible without incrementing the byte count, but it would cripple performance.


Haskell, 325 396 bytes

EDIT: new version:

s f[]=[]
s f l=f l
x(a:b:((c:d:e):r))=x((c:a):b:e:((d:s head r):s tail r))
x(a:r)=a:x r
w l|x l/=l=w.x$l|True=l
t n x=take n$repeat x
j 0=[]
j n=t(mod(n)2)1:j(div(n)2)
i n=[[],[]]++j n++t(32-(l$j n))[]
u(a:r)=2*u r+l a
o(_:a:r)=u r+l a
z a b=o$w$zipWith(++)(i a)(i b)

z does the job.

  • \$\begingroup\$ Some stuff can get shortened straight away - for example function has the highest precedence, so you can gut rid of parents around function applications, and also guards don't need parents either - guards stop where the = is, so parents there aren't needed, and so on and so forth, and note that : associates to the right and you can cut some there. But, anyways, congrats! Looks greatly complicated. Can't wait to figure out how this works! \$\endgroup\$ – proud haskeller Aug 10 '15 at 19:52
  • \$\begingroup\$ @proudhaskeller Uselessly complicated, though, see my edit. Shall I explain the basic idea? It might be better another way, but I tried to do as much pattern matching as possible at first. Ah, by parents you mean parentheses: golf'd that! \$\endgroup\$ – Leif Willerts Aug 10 '15 at 22:25
  • \$\begingroup\$ chillax, it's on of your first times here. If you stay long, you will grow much better. Be sure to check the Haskell golfing tips question for some insight codegolf.stackexchange.com/questions/19255/… \$\endgroup\$ – proud haskeller Aug 10 '15 at 22:29
  • \$\begingroup\$ @proudhaskeller edit arrived... \$\endgroup\$ – Leif Willerts Aug 10 '15 at 22:32

ES6, 130 bytes

(n,m)=>{for(a={},s=0,i=x=y=1;i<<1;i+=i,z=y,y=x,x+=z)s+=((n&i)+(m&i))/i*(a[i]=x);for(r=0;i;i>>>=1)s>=a[i]?(s-=a[i],r|=i):0;return r}

I originally tried to compute the sum in-place (effectively along the lines of the CJam implementation) but I kept running out of temporaries, so I just converted the numbers to and back from real integers.

(Yes, I can probably save a byte by using eval.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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