# Summation under Zeckendorf Representation

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

• Could you please elaborate the Input/Output? – flawr Aug 5 '15 at 19:02
• @flawr Please have a look at the provided reference implementation. You can use it to generate your own sample input. – FUZxxl Aug 5 '15 at 19:13
• 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. – flawr Aug 5 '15 at 20:12
• 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. – orlp Aug 5 '15 at 21:11
• @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. – Reto Koradi Aug 5 '15 at 21:47

# CJam, 76747063 59 bytes

2q~{32{2\#I&},}fI+32_,*{WUer$Kf-[UU]/[-2X]*2,/2a*Kf+}fKf#1b  Try it online in the CJam interpreter or verify all test cases at once. ### Idea 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. ### Code 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.

EDIT: new version:

s f[]=[]
s f l=f l
x((a:b):(c:d):(e:r))=x(b:d:(a:e):r)
x[]=[]
x(a:r)=a:x r
w l|x l/=l=w.x$l|True=l l=length 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[]=0 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.

• 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! – proud haskeller Aug 10 '15 at 19:52
• @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! – Leif Willerts Aug 10 '15 at 22:25
• 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/… – proud haskeller Aug 10 '15 at 22:29
• @proudhaskeller edit arrived... – 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.)