Nega-Zeckendorf representation

Question

Background

Zeckendorf representation is a numeral system where each digit has the value of Fibonacci numbers (1, 2, 3, 5, 8, 13, ...) and no two consecutive digits can be 1.

Nega-Zeckendorf representation is an extension to this system that allows encoding of all integers, not just positive ones. Its base values are nega-Fibonacci numbers (regular Fibonacci numbers with alternating sign; 1, -1, 2, -3, 5, -8, 13, -21, ..., also derived by extending regular Fibonacci sequence to negative indices).

Donald Knuth proved that every integer has a unique representation as a sum of non-consecutive nega-Fibonacci numbers (0 is an empty sum). Therefore, the corresponding nega-Zeckendorf representation is unique for every integer. 0 is represented as an empty list of digits.

Challenge

Given an integer (which can be positive, zero, or negative), compute its nega-Zeckendorf representation.

The output must consist of zeros and ones, either as numbers or characters. Output in either least-significant first or most-significant first order is acceptable (the latter is used in the test cases).

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

-10 = 101001
-9 = 100010
-8 = 100000
-7 = 100001
-6 = 100100
-5 = 100101
-4 = 1010
-3 = 1000
-2 = 1001
-1 = 10
0 = (empty)
1 = 1
2 = 100
3 = 101
4 = 10010
5 = 10000
6 = 10001
7 = 10100
8 = 10101
9 = 1001010
10 = 1001000

-11 = (-8) + (-3) = 101000
12 = 13 + (-1) = 1000010
24 = 34 + (-8) + (-3) + 1 = 100101001
-43 = (-55) + 13 + (-1) = 1001000010
(c.f. negafibonacci: 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, ...)

Answer 1

Jelly, 17 bytes

0BUJNÆḞḋƲ=ʋ1#ḢȯRB

Try it online!

+3 bytes (ḢȯR) to output [] instead of 0

I'm sure this can be beaten by some clever mathematical trick; this just counts up in binary, converts from nega-Zeckendorf and stops when it equals the input

How it works

0BUJNÆḞḋƲ=ʋ1#ḢȯRB - Main link. Takes n on the left
          ʋ       - Group the previous 4 links into a dyad f(k, n):
 B                -   Convert k to binary
  U               -   Reverse the bits
        Ʋ         -   Group the previous 4 links into a monad g(bin(k)):
   J              -     Indices
    N             -     Negate
     ÆḞ           -     nth Fibonacci number
       ḋ          -     Dot product with bin(k)
         =        -   Does g(bin(k)) equal n?
0          1#     - Find the first integer k such that f(k, n) is true
             Ḣ    - Extract k
              ȯR  - If k = 0, replace with []
                B - Convert to binary

Answer 2

Python 3, 89, 87 bytes

f=lambda n,a=-1,b=1,i=0:0<b*n<=b*b-i%2and f"1{f(n+a):0>{i}}"or n and f(n,b,a-b,i+1)or""

Try it online!

Old version

Uses the fact that each negative term in the negbonacci equals minus the sum of all preceding positive terms and, similarly, each positive term is 1 minus the sum of all preceding negative terms. This is used to set up a direct recursion.

Test bed "borrowed" from @Noodle9.

Answer 3

05AB1E, 19 18 bytes

∞bõš.ΔRSƶÅfāÉ·<*OQ

Try it online or verify all test cases.

Explanation:

∞                  # Push an infinite positive list: [1,2,3,4,5,...]
 b                 # Convert each to a binary string
  õš               # Prepend an empty string (for edge case 0)
    .Δ             # Find the first value which is truthy for:
      R            #  Reverse the binary string
       S           #  Convert it to a list of bits
        ƶ          #  Multiply each by its 1-based index
         Åf        #  Get the n'th Fibonacci number for each
           ā       #  Push a list in the range [1,length] (without popping)
            É      #  Check for each whether it's odd: [1,0,1,0,1,...]
             ·     #  Double each: [2,0,2,0,2,...]
              <    #  Subtract each by 1: [1,-1,1,-1,1,...]
               *   #  Multiply it to the Fibonacci numbers at the same positions
                O  #  Sum them together
                 Q #  And check if it's equal to the (implicit) input-integer
                   # (after which the found result is output implicitly)

Answer 4

JavaScript (ES6), 74 bytes

Output format: least-significant first.

f=(n,k)=>(g=(k,a,b)=>k&&k%2*a+g(k>>1,b-a,a,s+=k%2))(k,1,s='')^n?f(n,-~k):s

Try it online!

Answer 5

Ruby, 137 129 119 bytes

n=->x{x<2?x:n[x-2]-n[x-1]}
z=->x,u=0{i,y=0,u.to_s(2)
y.bytes.sum{|b|b%2*n[y.size+i-=1]}!=x||y=~/11+/?z[x,u+1]:y[0..-2]}

Try it online!

• Saved 8 Bytes thanks to @ovs suggestion to use =~(find) instead of match

• probably not the golfiest but at least I solved this complicated task.

n=->x{..} # nega-fib(x)
z=->x,u=0{ # starts from 0
y=u.to_s 2 # binary representation

we convert y to an array of nega+fibs or 0. If that sum is ==x and if no 1's are next to each other we return y with last bit removed, else we try next u

Answer 6

JavaScript (Node.js), 83 bytes

t=>(h=i=>i&i/2|t-(g=(i,p=0,q=1)=>i&&g(i>>1,q,p-q)+i%2*q)(i)?h(++i):i)``.toString(2)

Try it online!

Answer 7

MathGolf, 20 bytes

╘ïâ_h╒m*fh╒¥∞(m*Σk=▼

Outputs in least-significant first order (so the test cases in reversed).

Try it online.

Explanation:

                   ▼ # Do-while false with pop:
╘                    #  Discard everything from the stack
 ï                   #  Push the 0-based loop-index
  â                  #  Convert it to a binary-list
   _                 #  Duplicate it
    h                #  Push the length of this list (without popping)
     ╒               #  Pop and push a list in the range [1,length]
      m*             #  Multiply the integers at the same positions together
        f            #  Get the n'th Fibonacci number for each
         h╒          #  Push a [1,length] ranged list again (without popping)
           ¥         #  Modulo-2 on each
            ∞        #  Double each
             (       #  Subtract each by 1
              m*     #  Multiply the integers at the same positions again
                Σ    #  Sum this list together
                 k=  #  Check whether it's equal to the input-integer
                     # (after which the entire stack is output implicitly as result,
                     # which is the binary-list we've duplicated)

Answer 8

Charcoal, 60 bytes

ＮθＦ²⊞υ±ιＷ∧θ⁼›θ§υ±³›θ§υ±¹⊞υ↨…⮌υ²±¹Ｗ›Ｌυ²¿⁼›θ§υ±³›θ⊟υ0«1≧⁺§υ±¹θ

Try it online! Link is to verbose version of code. Based on the algorithm in the linked Stack Overflow question. Explanation:

Ｎθ

Input the integer.

Ｆ²⊞υ±ι

Start building up the negated nega-Fibonacci sequence with 0, -1.

Ｗ∧θ⁼›θ§υ±³›θ§υ±¹

Until enough terms have been generated to calculate the nega-Zeckendorf representation...

⊞υ↨…⮌υ²±¹

Push the difference between the last two terms to the sequence.

Ｗ›Ｌυ²

While sufficient terms of the sequence remain:

¿⁼›θ§υ±³›θ⊟υ0

If the integer does not fall between the third last and the last term (removing the last term as we go), then output a 0.

«1≧⁺§υ±¹θ

Otherwise output a 1 and add the (originally second) last term to the integer, which brings it closer to zero (since it has the opposite sign; see the linked question to explain why this works).

Answer 9

Python 3, ^{125 97} 93 bytes

f=lambda n,k=0:n-g(k)and f(n,k+1)or bin(k)[2:-1]
g=lambda k,a=0,b=1:k and k%2*a+g(k>>1,b-a,a)

Try it online!

Port of Arnauld's JavaScript answer.

Outputs most-significant first.

Answer 10

Husk, 19 bytes

ḟö=⁰ṁ_z*z*İ_İf↔ΘmḋN

Try it online!

                mḋ  # get the binary digits of each number in
                  N # the infinite list of integers
               Θ    # and prepend an empty list of no digits;
ḟö                  # now, return the first set that satisfies:
              ↔     # the digits reversed
      z*            # zipped by multiplication with
        z*İ_İf      # the negative negafibonacci sequence
                    # (=fibonacci sequence zipped by multiplication
                    # with powers of -1)
    ṁ_              # all negated and summed
  =⁰                # is equal to the input

Answer 11

Excel, 240 bytes

=LET(q,SEQUENCE(1,18),d,SEQUENCE(2^18-1),x,DEC2BIN(INT(d/2^9),9)&DEC2BIN(MOD(d,2^9),9),y,FILTER(x,ISERROR(FIND(11,x))),IF(A1,XLOOKUP(A1,MMULT(MID(y,q,1)*1,TRANSPOSE(-1*ROUND((-((1+5^0.5)/2)^(19-q))/5^0.5,0))),REPLACE(y,1,FIND(1,y)-1,)),""))

Explanation

=LET(q,SEQUENCE(1,18),                              # q = [1..18] horizontal
     d,SEQUENCE(2^18-1),                            # d = [1..2^18-1] vertical
     x,DEC2BIN(INT(d/2^9),9)&DEC2BIN(MOD(d,2^9),9), # x = 18 digit binary representations of d
     y,FILTER(x,ISERROR(FIND(11,x))),               # y = x with all items containing "11" removed
IF(A1,                                    # if A1 <> 0 then
      XLOOKUP(A1,                         #   match A1 to 
              MMULT(                      #   the matrix multiplication of
                MID(y,q,1)*1,             #   the digits of y times
                TRANSPOSE(-1*ROUND((-((1+5^0.5)/2)^(19-q))/5^0.5,0))), 
                                          #   the first 18 digits if the nega-Fibonacci series
              REPLACE(y,1,FIND(1,y)-1,)), #   return the corresponding y with leading zeros removed
      ""))                                # else ""

Lists all valid binary representations upto 18 digits and finds the match to the number in A1. Works for [-4180 .. 2584].

Answer 12

Python 3, 111 bytes

f=lambda x:x<0 or f(x-2)-f(x-1)
g=lambda a,n=0:a-sum(f(i)for i in range(n)if n>>i&1)and g(a,n+1)or bin(n)[2:-1]

Try it online!