Summation under Zeckendorf Representation
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
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.
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.