# Fibonacci Encoding

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
• Sandbox – pxeger Mar 31 at 11:39
• I almost made a Jelly built-in for this when making primorial and factorial base built-ins, ah well. – Jonathan Allan Mar 31 at 11:51
• Tip: this website gives the encoding for any positive integer, but with the bits in reverse, and without the final 1 – pxeger Mar 31 at 11:56
• This is, by the way, the inverse of this question – pxeger Mar 31 at 15:09
• 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)? – Jonathan Allan Apr 1 at 12:21

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

• Wow. How does this work? – Razetime Mar 31 at 14:30
• @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. – Etheryte Mar 31 at 14:32
• @Etheryte well done! I was wondering how long it would take someone to work this out haha – pxeger Mar 31 at 14:32
• – Shaggy Mar 31 at 15:40
• @Shaggy Nice, I'd urge you to post a separate answer since it's sufficiently different from my code. Good golfing! – Etheryte Mar 31 at 19:02

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

• A competitive answer in C? +1. – emanresu A Mar 31 at 21:19

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

# 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?:
Ḥ           -       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!

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

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

# Scala, 69 bytes

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


Try it online!

Outputs a String (reversed)

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!

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

# Japt, 12 bytes

Based off Etheryte's solution, posted with permission.

_øB ªU´}f¤ÔÄ


Try it

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

# 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! • You can shorten your definition of v as such: v=1:scanl(+)2v. Try it online! – Delfad0r Mar 31 at 14:15 • Not sure how helpful this is, but if you use Haskell (Lambdabot), you can exclude the import Data.List from your code section. – user Mar 31 at 14:32 # 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  # 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)  # 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! ### 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! # 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 • Welcome to Code Golf! Nice first answer. – Redwolf Programs Apr 6 at 1:31 # 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! • Shorter way to check that there are no 1s next to each other: o¬V& Try it online! – Leo Apr 6 at 1:11 # 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.

# Charcoal, 38 bytes

ＮθＦ²⊞υ⊕ιＷ‹⌈υθ⊞υΣ…⮌υ²←1ＦΦ⮌υκ«←Ｉ¬›ιθ≧﹪ιθ


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.

Ｎθ


Input n.

Ｆ²⊞υ⊕ι


Start with 1 and 2 from the Fibonacci sequence.

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


Keep pushing terms until one exceeds n.

←1


Print the final 1.

ＦΦ⮌υκ«


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

←Ｉ¬›ιθ


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

≧﹪ιθ


Subtract the term from n if it is smaller.

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