# 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

# K (ngn/k), 45 43 42 41 bytes

{2/<':(+/F@&+/'|2\x){y!x}\|F:64(+':1,)/0}


Try it online!

@Bubbler's algorithm

{ } function with argument x

64( )/0 do 64 times, using 0 as initial value:

• 1, prepend 1

• +': add each prior (leave the first element intact)

F: assign to F for "fibonacci sequence"

| reverse

(..){y!x}\.. starting with the value on the left, compute cumulative remainders (left-to-right) for the list on the right. the value on the left is the plain sum of the inputs without zeckendorf representation:

• 2\x binary encode the inputs. this will be an nbits-by-2 matrix

• | reverse

• +/' sum each

• & where are the 1s? - list of indices. if there are any 2s, the corresponding index is repeated twice.

• F@ array indexing into F

• +/ sum

<': less than each prior (the first of the result will always be falsey)

2/ binary decode

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

# 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] &