17
\$\begingroup\$

Fibonacci coding is a universal code, which can encode positive integers of any size in an unambiguous stream of bits.

To encode an integer \$ n \$:

  • Find the largest Fibonacci number less than or equal to \$ n \$; subtract this number from \$ n \$, keeping track of the remainder
  • If the number subtracted was the \$ i \$th Fibonacci number \$ F(i) \$, put a \$ 1 \$ at index \$ i−2 \$ in the code word (counting the left most digit as index \$ 0 \$)
  • Repeat the previous steps, substituting the remainder for \$ n \$, until a remainder of \$ 0 \$ is reached
  • Append a final \$ 1 \$

Alternately explained:

  • Find the Zeckendorf representation of \$ n \$ (the list of unique non-consecutive Fibonacci numbers which sum to it)
  • For all the Fibonacci numbers up to and including \$ n \$, excluding \$ 0 \$ and the first \$ 1 \$, append a bit \$ 0 \$ or \$ 1 \$ according to whether or not they appear in \$ n \$'s Zeckendorf representation
  • Strip any trailing \$ 0 \$s and append a final \$ 1 \$

Your task is to, given a positive integer, output the bits of its Fibonacci coding.

Test Cases

Input    Output
-------------------------------------------
1        11
2        011
3        0011
4        1011
11       001011
12       101011
13       0000011
14       1000011
65       0100100011
610      000000000000011
8967     00001010101010010011
8039213  0010010010100010001001001000001011

(if your code cannot compute this high in reasonable time, that is fine)

Rules

  • Output should be as a string or array of \$ 1 \$s-and-\$ 0 \$s or booleans (but not just any truthy or falsey value)
  • You may output the bits in reverse if that is more convenient (although this behaviour must be consistent)
  • You may use any sensible I/O format
  • Standard loopholes are forbidden
  • This is , so the shortest code in bytes wins
\$\endgroup\$
6
  • \$\begingroup\$ Sandbox \$\endgroup\$ – pxeger Mar 31 at 11:39
  • 7
    \$\begingroup\$ I almost made a Jelly built-in for this when making primorial and factorial base built-ins, ah well. \$\endgroup\$ – Jonathan Allan Mar 31 at 11:51
  • 2
    \$\begingroup\$ Tip: this website gives the encoding for any positive integer, but with the bits in reverse, and without the final 1 \$\endgroup\$ – pxeger Mar 31 at 11:56
  • \$\begingroup\$ This is, by the way, the inverse of this question \$\endgroup\$ – pxeger Mar 31 at 15:09
  • \$\begingroup\$ It seems to me to be a sensible output but could you confirm that we may produce an integer as output (representing the reverse of the bits in the examples)? \$\endgroup\$ – Jonathan Allan Apr 1 at 12:21

19 Answers 19

18
\$\begingroup\$

Japt, 13 bytes

@!X¤øB}iU
¤ÔÄ

Explanation:

@!X¤øB}iU 
@     }iU // Get the U-th (input) number
 !        // which doesn't have
    øB    // "11" in its
  X¤      // binary representation

¤ÔÄ
¤         // Take that number's binary representation,
 Ô        // reverse it
  Ä       // and add one to the end.

Try it here.

\$\endgroup\$
5
  • \$\begingroup\$ Wow. How does this work? \$\endgroup\$ – Razetime Mar 31 at 14:30
  • 8
    \$\begingroup\$ @Razetime This completely ignores the challenges description of how to find the numbers and uses the fact that it's a continuous encoding instead. I've added an explanation for the verbatim code too. \$\endgroup\$ – Etheryte Mar 31 at 14:32
  • 3
    \$\begingroup\$ @Etheryte well done! I was wondering how long it would take someone to work this out haha \$\endgroup\$ – pxeger Mar 31 at 14:32
  • 3
    \$\begingroup\$ 12 bytes? \$\endgroup\$ – Shaggy Mar 31 at 15:40
  • \$\begingroup\$ @Shaggy Nice, I'd urge you to post a separate answer since it's sufficiently different from my code. Good golfing! \$\endgroup\$ – Etheryte Mar 31 at 19:02
8
\$\begingroup\$

C (gcc), 51 50 bytes

k;f(n){for(k=0;n-=!(++k&k/2););n=log2(k);k+=2<<n;}

Try it online!

Uses the formula from Etheryte's Japt answer.
Returns the Fibonacci code word for input \$n\$ in reversed binary.

Explanation

k;f(n){                           // function taking an integer n > 0
       for(k=0;             ;);   // loop over values of integer k
                                  // starting at 1 (because of the bump)  
               n                  // until n is zero
                -=!(       )      // subtracting 1 from n when...
                    ++            // (bump k at the start of each loop)
                      k&k/2       // ...there's no 2 consecutive 1 bits in k  
                                  // k is now the nth integer without   
                                  // any 2 consecutive 1 bits
       n=log2(k);                 // get the number of bits in k by
                                  // converting  its log2 to an int   
       k+=2<<n;                   // add a 1 bit just above k's most   
                                  // significant bit and return k   
}
\$\endgroup\$
1
  • 3
    \$\begingroup\$ A competitive answer in C? +1. \$\endgroup\$ – emanresu A Mar 31 at 21:19
6
\$\begingroup\$

Haskell, 76 bytes

1#2
(u#v)x|x<v=["11"|x==u]|z<-u+v=map('0':)(v#z$x)++map("10"++)(z#(z+v)$x-u)

Try it online!

Outputs a string of 0's and 1's wrapped in a singleton list (e.g. ["001011"]).

How?

  • (u#v)x: we want this function to return a list of all the possible Fibonacci encodings for x using only Fibonacci numbers greater or equal than u; we further assume that u and v are consecutive fibonacci numbers (with u<v). It is well known that, if such an encoding exists, than it is unique (this follows from the uniqueness of the Zeckendorff representation), so the length of the list (u#v)x will be at most 1. For instance, (3#5)11==["1011"], since 11=3+8.
  • |x<v=["11"|x==u]: if x<v then the encoding only exists if x==u. If this is the case we return ["11"], otherwise we return the empty list.
  • |z<-u+v=: otherwise, let z=u+v be the next Fibonacci number. We have two choices.
    • map('0':)(v#z$x): we try to encode x without using u. In this case, the encoding will be contained in (v#z)x, and we prepend a '0' to denote the fact that we didn't take u.
    • ++map("10"++)(z#(z+v)$x-u): we try to encode x using u. In this case, "10" denotes that we take u and we don't take v. For this choice to be valid, we must also find an encoding of x-u using only Fibonacci numbers from z onwards (notice that z+v is the Fibonacci number after z).
\$\endgroup\$
0
6
\$\begingroup\$

Jelly,  21  12 bytes

Using Etheryte's observation from their Japt answer is much terser and more efficient to boot (it may be possible in even less, let's see...)

1BSƝỊẠƲ#ṪB1;

A monadic Link accepting a positive integer that yields a list of 1s and 0s (in reversed order as allowed in the rules).

Try it online!


A faster 12 byter:

1Ḥ^:3ƲƑ#ṪB1;

Try it online!

How?

1Ḥ^:3ƲƑ#ṪB1; - Link: positive integer, n
1      #     - set k=1 and increment to collect the first n ks for which:
      Ƒ      -   (k) is invariant under?:
     Ʋ       -     last four links as a monad, f(k):
 Ḥ           -       double (k)
  ^          -       (2k) bitwise-XOR with k -> x
    3        -       three
   :         -       (x) integer divide (3)
        Ṫ    - tail
         B   - to binary
          1  - one
           ; - (1) concatenate with (the binary list)

Original 21:

This is (a) extremely inefficient and (b) almost certainly not the right way to get the tersest code, so I'll was planning to come back to it after work...

‘ÆḞ€ḊðŒPS⁼¥Ƈ⁹Ḣ⁸iⱮðṬ;1

A monadic Link accepting a positive integer that yields a list of 1s and 0s.

Try it online!

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6),  46  44 bytes

Based on @Etheryte's insight.

Returns a string of bits in reverse order.

f=(n,k)=>k&k/2||n--?f(n,-~k):1+k.toString(2)

Try it online!

Commented

f = (             // f is a recursive function taking:
  n,              //   n = input
  k               //   k = counter, initially undefined (coerced
) =>              //       to 0 for bitwise operations)
  k & k / 2 ||    // yield a truthy value right away if there are
                  // at least 2 consecutive bits set in k
    n--           // otherwise, yield n and decrement it afterwards
  ?               // if either statement above is truthy:
    f(n, -~k)     //   do a recursive call with k + 1
  :               // else:
    1 +           //   stop and return a leading '1'
    k.toString(2) //   followed by the binary representation of k

JavaScript (Node.js),  109  105 bytes

Based on the challenge description.

Expects a BigInt. Returns a string of bits in reverse order.

f=(n,k=m=0n)=>n?(g=(i,x=0n,y=1n)=>i?g(~-i,z=y,x+y):y)(k)>n?f(n-z,0n,m|=1n<<k-2n):f(n,-~k):1+m.toString(2)

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3.8 (pre-release), 51 bytes

Another based on Etheryte's Japt answer

f=lambda n,k=0:-n*f'1{k-1:b}'or f(n-(k&k//2<1),k+1)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Scala, 69 bytes

Based on Etheryte's amazing answer

"1"+Stream.from(0).map(_.toBinaryString).filter(!_.contains("11"))(_)

Try it online!

Outputs a String (reversed)

Original answer, 123 bytes

n=>(f.takeWhile(n>=_):\(n,1::Nil)){case(x,n->c)=>if(x>n)(n,0::c)else(n-x,1::c)}._2
def f:Stream[Int]=1#::f.scanLeft(2)(_+_)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Stax, 16 bytes

âî}g♥▼«zΩ╥;QbB]╔

Run and debug it

Based on Etheryte's observation, which shaved a off a ton of bytes. Check out their answer!

Explanation

Z{|B.11#!}{ge|B'1s+
Z                   push 0 under the input(counter)
           ge       generator: find the first n elements, return the last
          {         empty block: get the next element by incrementing
 {       }          filter:
  |B                base2 string
    .11#!           has 0 occurrences of "11"?
               '1s+ prepend a 1 to it(r'1+ also works for valid output)

Stax, 29 bytes

é½Æ½┼≥╦◘½}○└╩►à«ôæ→¢ûU«½*≈ø»▀

Run and debug it

Pretty big.

\$\endgroup\$
3
\$\begingroup\$

Japt, 12 bytes

Based off Etheryte's solution, posted with permission.

_øB ªU´}f¤ÔÄ

Try it

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

Wolfram Language (Mathematica), 127 bytes

(f@n_:=(k=1;While[(F=Fibonacci)[++k]<=n];k-1);s=Table[0,f[t=#]];(s[[#]]=1)&/@(f/@NestWhileList[#-F@f@#&,t,#>0&]);RotateLeft@s)&

Try it online!

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

Haskell (GHC), 118 104 bytes

x@(_:v)=1:scanl(+)1x
f n=snd(foldr(\v(x,l)->if v<=x then(x-v,1:l)else(x,0:l))(n,[])$fst$span(<=n)v)++[1]

Try it online!

Original:

Outputs a list of reversed bits.

import Data.List
x@(_:v)=1:scanl(+)1x
f n=1:snd(mapAccumL(\a b->if b<=a then(a-b,1)else(a,0))n$reverse$fst$span(<=n)v)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ You can shorten your definition of v as such: v=1:scanl(+)2v. Try it online! \$\endgroup\$ – Delfad0r Mar 31 at 14:15
  • \$\begingroup\$ Not sure how helpful this is, but if you use Haskell (Lambdabot), you can exclude the import Data.List from your code section. \$\endgroup\$ – user Mar 31 at 14:32
2
\$\begingroup\$

05AB1E, 14 bytes

∞ʒb11å>}s<èb1ì

Try it online!

∞ʒb11å>}s<èb1ì  # full program
         <è     # push the...
        s       # implicit input...
         <è     # -th...
∞               # natural number...
 ʒ     }        # which...
      >         # does not...
     å          # contain...
   11           # literal...
  b             # in binary...
           b    # converted to binary...
            1   # with literal...
             ì  # prepended
                # implicit output
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 43 bytes

n=>(g=p=>n<p||2*g(p+q,q=p)+(n>(n%=p)))(q=1)

Try it online!

It returns an integer whose binary form is reversed Fibonacci Encoding.

// I have a code for base 2 convention
n=>(g=p=>n<p  2*g(       )+(n>(n%=p)))(   )
// I have a code for Fibonacci sequence
n=>(g=p=>       g(p+q,q=p)           )(q=1)
// Boom, Fibonacci base convention
n=>(g=p=>n<p||2*g(p+q,q=p)+(n>(n%=p)))(q=1)
\$\endgroup\$
2
\$\begingroup\$

Red, 135 124 bytes

func[n][i: k: 0 until[i: i + 1 unless find do
b:[enbase/base to#{01}i 2]"11"[k: k + 1]n = k]reverse
rejoin["1"find do b"1"]]

Try it online!

Uses @Etheryte's method

As an excercise - the step by step method:

Red, 153 bytes

func[n][c: charset 1 until[k: 0 a: 0 b: 1 until[k: k + 1
t: a a: b b: t + b b > n]c/(k - 2): 1 0 = n: n - a]replace
enbase/base to#{01}c 2[any"0"end]"1"]

Try it online!

More readable:

f: func[n][
    c: charset 1
    until [
        k: 0
        set [a b] [0 1]
        until [ 
            k: k + 1
            set [a b] reduce [b a + b] 
            b > n
        ]
        c/(k - 2): 1
        0 = n: n - a
    ]
    replace enbase/base to binary! c 2 [any "0" end] "1"
]

charset is short for make bitset!

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

jq (74 bytes)

Since shortness is the goal ...

def f:def i:.,i|([0]+.,[1]+.);nth(.-1;[1]|i|select(index([1,1])|not))+[1];

Example:

65|f #=> [0,1,0,0,1,0,0,0,1,1]

Try it online

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$ – Redwolf Programs Apr 6 at 1:31
2
\$\begingroup\$

Husk, 14 12 bytes

Edit: -2 bytes thanks to Leo

↔:1!fo¬V&mḋN

Try it online!

Based on Etheryte's approach: upvote that!

\$\endgroup\$
1
  • \$\begingroup\$ Shorter way to check that there are no 1s next to each other: o¬V& Try it online! \$\endgroup\$ – Leo Apr 6 at 1:11
1
\$\begingroup\$

Retina 0.8.2, 63 bytes

.+
$*
(\G1|(?>\2?)(\1))*1
$#1$*01¶
+`^(.*).(.*¶)(\1.)¶
$3$2
¶
1

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

(\G1|(?>\2?)(\1))*1

Use a tweaked version of @MartinEnder's answer to Am I a Fibonacci Number? to match Fibonacci numbers that sum to the input.

$#1$*01¶

For each match, generate the bit in the appropriate column.

+`^(.*).(.*¶)(\1.)¶
$3$2

Fold all of the bits together.

¶
1

Replace the final delimiter with a final 1 bit.

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

Charcoal, 38 bytes

NθF²⊞υ⊕ιW‹⌈υθ⊞υΣ…⮌υ²←1FΦ⮌υκ«←I¬›ιθ≧﹪ιθ

Try it online! Link is to verbose version of code. Explanation: Outputs digits in reverse order, but this is the least of Charcoal's problems because it can simply print them backwards.

Nθ

Input n.

F²⊞υ⊕ι

Start with 1 and 2 from the Fibonacci sequence.

W‹⌈υθ⊞υΣ…⮌υ²

Keep pushing terms until one exceeds n.

←1

Print the final 1.

FΦ⮌υκ«

Loop through all the terms except the last in reverse order.

←I¬›ιθ

Print 0 or 1 depending on whether this term is larger than n.

≧﹪ιθ

Subtract the term from n if it is smaller.

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

Mini-Flak (BrainHack), 104 bytes

([{}]((()))){({}(())({{}[()](({}({}))){(()[{}]){(({}{}[()]))}}{}}{}(())){[({})]({}[()](()[()]))}{}{})}{}

Try it online!

Starts at 11 and iteratively computes the encoding of the next number n-1 times.

# Create 11 while computing 1-n.
([{}]((())))

# Repeat
{

  # Add 1 to counter (going up to zero) and allow loop to start
  ({}(())

    # Eventually push number of iterations to reach 00 or 11
    (

      {

        # Remove 1 from stack
        {}[()]

        # Compute sum of two digits, keeping second, and push twice
        (({}({})))

        # If not 00:
        {

          # Subtract value from 1; this makes iteration evaluate to 1
          (()[{}])

          # If top of stack still isn't zero (i.e., digits were 11):
          {

            # Push two zeros: one to exit loop and the other to exit conditional
            (({}{}[()]))

        }}{}

      # Repeat until 00 or 11 found
      }{}

      # Push 1 at position
      (())

    # Push number of leading zeroes to use, plus one
    )

    # That many times:
    {

      # Compute -k: this will make each iteration evaluate to -1
      [({})]

      # Subtract 1 from k...
      ({}[()]

        # while pushing 0 below it
        (()[()])

      )

    }{}

    # Since the push evaluates to a number of iterations, and
    # those iterations all evaluate to -1, this main part of the main
    # loop evaluates to zero.

    # Remove extraneous zero: this is shorter than subtracting 1 earlier
    {}

# Repeat until counter reaches zero, and pop zero
)}{}
\$\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.