14
\$\begingroup\$

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
\$\endgroup\$
  • 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
4
\$\begingroup\$

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: assing 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

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
9
+200
\$\begingroup\$

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.
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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
4
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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] &
\$\endgroup\$

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.