14
\$\begingroup\$

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, ...)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ This stack overflow question contains a possible algorithm. \$\endgroup\$
    – att
    Oct 27, 2021 at 6:32
  • 1
    \$\begingroup\$ 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]; \$\endgroup\$
    – alephalpha
    Oct 27, 2021 at 12:26
  • \$\begingroup\$ Is it acceptable to output 0 for 0? \$\endgroup\$
    – Jakque
    Oct 27, 2021 at 21:29
  • \$\begingroup\$ @Jakque No. \$\endgroup\$
    – Bubbler
    Oct 27, 2021 at 22:12

12 Answers 12

4
\$\begingroup\$

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

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

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

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!

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

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)
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 60 bytes

NθF²⊞υ±ιW∧θ⁼›θ§υ±³›θ§υ±¹⊞υ↨…⮌υ²±¹W›Lυ²¿⁼›θ§υ±³›θ⊟υ0«1≧⁺§υ±¹θ

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

Nθ

Input the integer.

F²⊞υ±ι

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

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

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

⊞υ↨…⮌υ²±¹

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

W›Lυ²

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

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

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.

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

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

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

\$\endgroup\$
1
  • \$\begingroup\$ 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,)),"")) \$\endgroup\$ Jan 10, 2022 at 16:21
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.