# Nega-Zeckendorf representation

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

• This stack overflow question contains a possible algorithm.
– att
Commented Oct 27, 2021 at 6:32
• An ungolfed Mathematica implementation based on Knuth's proof: m[a_] := Switch[Mod[a, 8], 1 | 5, a - 1, 0, a + 2, 4, a - 3, 2, 4 m[(a - 2)/4] + 1]; p[a_] := Switch[Mod[a, 4], 2, a - 2, 0, a + 1, 1 | 3, 2 m[(a - 1)/2]]; c[n_] := Nest[If[n > 0, p, m], 0, Abs@n]; Commented Oct 27, 2021 at 12:26
• Is it acceptable to output 0 for 0? Commented Oct 27, 2021 at 21:29
• @Jakque No. Commented Oct 27, 2021 at 22:12

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


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

# 05AB1E, 19 18 bytes

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


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)


# 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!

# 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

• y.match(/1{2,}/) can be shortened to y=~/11+/.
– ovs
Commented Oct 30, 2021 at 21:57

# 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!

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


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

# 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!

Outputs most-significant first.

# 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


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

• You can get this down to 228 bytes by using Column() and Row(), and by using int() instead of round() - =LET(q,COLUMN(A:R),d,ROW(1:262143),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(1*MID(y,q,1),TRANSPOSE(-INT((-((1+5^0.5)/2)^(19-q))/5^0.5))),REPLACE(y,1,FIND(1,y)-1,)),"")) Commented Jan 10, 2022 at 16:21

# 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!