APL (Dyalog Extended), 39 bytes

⊥1↓⍧|/⌽(+/g[⍸⌽+/⊤⎕]),↑,\⌽g←(2+/,)⍣38⍨⍳2 

Try it online!

Changed into a full program taking one argument of length 2, and also changed the Fibonacci generator. Thanks to @ngn for lots of ideas.

Uses ⎕IO←0 so that ⍳2 evaluates to 0 1.

Fibonacci generator (new)

Note that the last two numbers are inaccurate, but it doesn't change the output of the program.

(2+/,)⍣38⍨⍳2 → 0 1 ((2+/,)⍣38) 0 1 Step 1 0 1 (2+/,) 0 1 → 2+/ 0 1 0 1 → (0+1) (1+0) (0+1) ⍝ 2+/ evaluates sums for moving window of length 2 → 1 1 1 Step 2 0 1 (2+/,) 1 1 1 → 2+/ 0 1 1 1 1 → 1 2 2 2 Step 3 0 1 (2+/,) 1 2 2 2 → 2+/ 0 1 1 2 2 2 → 1 2 3 4 4 

Zeckendorf to plain (partial)

⍸⌽+/⊤⎕ ⎕ ⍝ Take input from stdin, must be an array of 2 numbers ⊤ ⍝ Convert each number to base 2; each number is mapped to a column +/ ⍝ Sum in row direction; add up the counts at each digit position ⌽ ⍝ Reverse ⍸ ⍝ Convert each number n at index i to n copies of i 

---

APL (Dyalog Extended), 47 bytes

g←1↓(1,+\⍤,)⍣20⍨1 {⊥1↓⍧|/⌽⍵,↑,\⌽g}+⍥{+/g[⍸⌽⊤⍵]} 

Try it online!

Changed Part 1 of the previous answer to reuse the Fibonacci numbers. Also, drop the duplicate 1 to save some bytes in other places.

Part 1 (new)

{+/g[⍸⌽⊤⍵]} ⊤⍵ ⍝ Argument to binary digits ⍸⌽ ⍝ Reverse and convert to indices of ones g[ ] ⍝ Index into the Fibonacci array of 1,2,3,5,... +/ ⍝ Sum 

---

APL (Dyalog Extended), 52 bytes

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}+⍥({+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤) 

Try it online!

How it works

No fancy algorithm to do addition in Zeckendorf because APL isn't known for operation on individual elements in an array. Instead, I went ahead to convert the two inputs from Zeckendorf to plain integers, add them, and convert it back.

Part 1: Zeckendorf to plain integer

{+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤ ⍝ Zeckendorf to plain integer ⊤ ⍝ Convert the input to array of binary digits (X) { ( ≢⊤⍵) } ⍝ Take the length L of the binary digits and ⌽⍳ ⍝ generate 1,2..L backwards, so L..2,1 {+∘÷⍣( )⍨1} ⍝ Apply "Inverse and add 1" L..2,1 times to 1 ⍝ The result looks like ..8÷5 5÷3 3÷2 2 (Y) ⊥ ⍝ Mixed base conversion of X into base Y Base | Digit value ------------------------------- 13÷8 | (8÷5)×(5÷3)×(3÷2)×2 = 8 8÷5 | (5÷3)×(3÷2)×2 = 5 5÷3 | (3÷2)×2 = 3 3÷2 | 2 = 2 2÷1 | 1 = 1 

Part 2: Add two plain integers

+⍥z2i ⍝ Given left and right arguments, ⍝ apply z2i to each of them and add the two 

Part 3: Convert the sum back to Zeckendorf

"You may assume that the Zeckendorf representations of both input and output fit into 31 bits" was pretty handy.

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1} ⍝ Convert plain integer N to Zeckendorf (1,+\⍤,)⍣20⍨1 ⍝ First 41 Fibonacci numbers starting with two 1's ⌽ ⍝ Reverse ↑,\ ⍝ Matrix of prefixes, filling empty spaces with 0's ⌽⍵, ⍝ Prepend N to each row and reverse horizontally |/ ⍝ Reduce by | (residue) on each row (see below) ⍧ ⍝ Nub sieve; 1 at first appearance of each number, 0 otherwise 1↓¯1↓ ⍝ Remove first and last item ⊥ ⍝ Convert from binary digits to integer 

The Fibonacci generator

(1,+\⍤,)⍣20⍨1 → 1 ((1,+\⍤,)⍣20) 1 ⍝ Expand ⍨ → Apply 1 (1,+\⍤,) x 20 times to 1 First iteration 1(1,+\⍤,)1 → 1,+\1,1 ⍝ Expand the train → 1,1 2 ⍝ +\ is cumulative sum → 1 1 2 ⍝ First three Fibonacci numbers Second iteration 1(1,+\⍤,)1 1 2 → 1,+\1,1 1 2 ⍝ Expand the train → 1 1 2 3 5 ⍝ First five Fibonacci numbers ⍣20 ⍝ ... Repeat 20 times 

This follows from the property of Fibonacci numbers: if Fibonacci is defined as

$$ F_0 = F_1 = 1; \forall n \ge 0, F_{n+2} = F_{n+1} + F_n $$

then

$$ \forall n \ge 0, \sum_{i=0}^{n} F_i = F_{n+2} - 1 $$

So cumulative sum of \$ 1,F_0, \cdots, F_n \$ (Fibonacci array prepended with a 1) becomes \$ F_1, \cdots, F_{n+2} \$. Then I prepend a 1 again to get the usual Fibonacci array starting with index 0.

Fibonacci to Zeckendorf digits

Input: 7, Fibonacci: 1 1 2 3 5 8 13 Matrix 0 0 0 0 0 0 13 7 0 0 0 0 0 8 13 7 0 0 0 0 5 8 13 7 0 0 0 3 5 8 13 7 0 0 2 3 5 8 13 7 0 1 2 3 5 8 13 7 1 1 2 3 5 8 13 7 Reduction by residue (|/) - Right side always binds first. - x|y is equivalent to y%x in other languages. - 0|y is defined as y, so leading zeros are ignored. - So we're effectively doing cumulative scan from the right. 0 0 0 0 0 0 13 7 → 13|7 = 7 0 0 0 0 0 8 13 7 → 8|7 = 7 0 0 0 0 5 8 13 7 → 5|7 = 2 0 0 0 3 5 8 13 7 → 3|2 = 2 0 0 2 3 5 8 13 7 → 2|2 = 0 0 1 2 3 5 8 13 7 → 1|0 = 0 1 1 2 3 5 8 13 7 → 1|0 = 0 Result: 7 7 2 2 0 0 0 Nub sieve (⍧): 1 0 1 0 1 0 0 1's in the middle are produced when divisor ≤ dividend (so it contributes to a Zeckendorf digit). But the first 1 and last 0 are meaningless. Drop first and last (1↓¯1↓): 0 1 0 1 0 Finally, we apply base 2 to integer (⊥) to match the output format. 

CJam, 76 74 70 63 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
G_k = G_k-1 + G_k-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 G₀ and, in general, the bit k to G_k.

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

For example, the input 532₁₀ = 1000010100₂ 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 G_k 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 G_k + G_k+1 = G_k+2 and G_k + G_k = G_k + G_k-1 + G_k-2 = G_k+1 + G_k-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.¹

Special case has to be taken for resulting negative indexes. Since G_-2 = 0, index -2 can simply be ignored. Also, G_-1 = 0 = G₀, 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. 

---

¹ _{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(b:d:(a:e):r) x(a:b:((c:d:e):r))=x((c:a):b:e:((d:s head r):s tail 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.

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.)

Ruby, 85 73 65 bytes

->*a{r=(0..2*a.sum).select{|r|r^r*2==r*3};r[a.sum{|w|r.index w}]} 

Try it online!

How?

First get an upper bound for the encoded sum: (a+b)*2 is ok.

Now filter out all non-zeckendorf numbers from (0..limit).

We have a lookup table, it's downhill from here.

Python 3, 207 bytes

def s(n): p=1 while n>=2*p: p*=2 return n if n<=p else s(n+p//2)if n>=3*p/2 else s(m)if (m:=s(n-p)+p)!= n else n a=lambda n,m:(b:=n&m)>-1 and s(a(a(a(s((n|m)-b%4),b//4*2),b//4),b%4*2+b%4//2))if m else n 

Try it Online! (Verify all test cases)

Explanation

This program directly manipulates the binary translations of the Zeckendorf representations. The function a(n,m) performs the main calculations, and s(n) is a helper function that gets rid of adjacent numbers contained in the Zeckendorf representation.

Let's start with the function s(n) (expanded for clarity):

def s(n): p=1 #This finds the highest digit of the binary form of n. while n>=2*p: p*=2 if n<=p: #If n is a power of two (i.e, our number is already a Fibonnaci number)... return n #Then return it normally. This also works for zero. (A) if n>=3*p/2: #If n's first digit is followed by a 1 (i.e, it starts with 11X) return s(n+p//2) #Then replace that with 100X (B) m = s(n-p)+p #Otherwise, apply s to the rest of the number (C) if m==n: #If this is out final result, we're done! (D) return n return s(m) #Otherwise, reapply it. (E) 

For example, the number 107 (1101011 in binary, representing 1+2+5+13+21=42), undergoes the following process:

1+2+5+13+21 [1101011] -> 1+2+5+34 [10001011] (B) 1+2+5+34 [10001011] (C) 1+2+5 [1011] (C) 1+2 [11] -> 3 [100] (B) ->3+5 [1100] (A/E) (E): 3+5 [1100] -> 8 [10000] (B) ->8+34 [10010000] (A/E) (E): 8+34 [10010000] (C) ->8+34 [10010000] (A/E) 

Try it Online! (s with detailed output)

Here is an expanded version of a(n,m):

def a(n,m): if m==0: return n b=n&m t=s((n|m)-b%4) #(A) t=a(t,b//4*2) #(B) t=a(t,b//4) #(C) return s(a(t,b%4*2+b%4//2)) #(D) 

This function converts the two Zeckendorf representations into four binary numbers which are easier to combine. Line (A) is the bitwise OR of the two binary Zeckendorf representations--these correspond to one copy of each Fibonacci number in either group. (B) and (C) are the bitwise AND of the two numbers right-shifted 1 and 2 times, respectively. We know that when the corresponding Fibonacci numbers for (B) and (C) are added together, they will be equivalent to the bitwise AND of our n and m because F(n)=F(n-1)+F(n-2).

For example, let's say that we have the binary numbers n=101001 (corresponding to 1+5+13) and m=110110 (2+3+8+13). Then we will have (A)=111111 (1+2+3+5+8+13), which is converted to 1010100 (3+8+21) by our function s, (B)=10000 (8), and (C)=1000 (5). We can check that (1+5+13)+(2+3+8+13)=(3+8+21)+(8)+(5)=45. This process repeats with ((3+8+21)+(8))+(5)=((3+8+21)+(5)+(3))+(5), etc.

The one difficulty with this system is that it doesn't work for the Fibonacci numbers 1 and 2, since they don't obey the property F(n)=F(n-1)+F(n-2) (they're the lowest two numbers)! Because of that, whenever 1 or 2 is contained in both n and m, they are removed from A, B, and C, then their sum placed in D under the property that 1+1=2 and 2+2=1+3. For example, if we add 1+3 (101) + 1+3+5 (1101), we get:

(A): 3+5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 2 (10)

Notice that the 3 and 5 were placed into A, the duplicate 3 was split into 2+1 in B and C, and duplicate 1s were removed from A, B, and C, added together, and put into D. Similarly, if we add 2+3 (110) + 2+3+5 (1110), we get:

(A): 3+5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 1+3 (101)

Try it online! (a with detailed output)

Wolfram Language (Mathematica), 218 bytes

Fold[#+##&,Total@PadLeft@IntegerDigits[#,2]//.{{p=n_/;n>1,r=y___}:>{0,n,y},{q=x___,i_,p,j_,k_,r}:>{x,i+1,n-2,j,k+1,y},{q,i_,p,j_}:>{x,i+1,n-2,j+1},{q,i_,p}:>{x,i+1,n-2},{1,1,r}:>{1,0,0,y},{q,i_,1,1,r}:>{x,i+1,0,0,y}}]& 

Try it online!

Simply pattern matching.

Ungolfed:

FromDigits[Total@PadLeft@IntegerDigits[#, 2] //. {{n_ /; n > 1, y___} :> {0, n, y}, {x___, i_, n_ /; n > 1, j_, k_, y___} :> {x, i + 1, n - 2, j, k + 1, y}, {x___, i_, n_ /; n > 1, j_} :> {x, i + 1, n - 2, j + 1}, {x___, i_, n_ /; n > 1} :> {x, i + 1, n - 2}, {1, 1, y___} :> {1, 0, 0, y}, {x___, i_, 1, 1, y___} :> {x, i + 1, 0, 0, y}}, 2] &