Binary Fibonacci

Question

Challenge

You need to generate a program or function that takes in a positive integer N, calculates the first N terms of the Fibonacci sequence in binary, concatenates it into a single binary number, converts that number back to decimal, and then outputs the decimal as an integer.

For example

1 -> [0] -> 0 to decimal outputs 0
3 -> [0, 1, 1] -> 011 to decimal outputs 3
4 -> [0, 1, 1, 10] -> 01110 to decimal outputs 14

You do not need to output the ->, just the number (e.g. if the user types 4, just output 14). The arrows are just to help explain what the program must do.

Test cases

1 -> 0
2 -> 1
3 -> 3
4 -> 14
5 -> 59
6 -> 477
7 -> 7640
8 -> 122253
9 -> 3912117
10 -> 250375522
11 -> 16024033463
12 -> 2051076283353
13 -> 525075528538512
14 -> 134419335305859305
15 -> 68822699676599964537
16 -> 70474444468838363686498
17 -> 72165831136090484414974939
18 -> 147795622166713312081868676669
19 -> 605370868394857726287334099638808
20 -> 4959198153890674493745840944241119317

The program must be able to output up to the limit of the language in use. No lookup tables or common workarounds allowed.

This is code-golf, so the answer with the shortest number of bytes wins!

Answer 1

Python, 64 bytes

f=lambda n,a=0,b=1,r=0:n and f(n-1,b,a+b,r<<len(bin(a))-2|a)or r

Try it online!

Answer 2

Jelly,  7  6 bytes

ḶÆḞBẎḄ

Try it online!

How?

ḶÆḞBẎḄ - Link: integer, n
Ḷ      - lowered range -> [0,1,2,3,4,5,...,n]
 ÆḞ    - Fibonacci (vectorises) -> [0,1,1,2,3,5...,F(n)]
   B   - to binary (vectorises) -> [[0],[1],[1],[1,0],[1,1],[1,0,1],...,B(F(n))]
    Ẏ  - tighten -> [0,1,1,1,0,1,1,1,0,1,...,B(F(n))[0],B(F(n))[1],...]
     Ḅ - from binary -> answer

Answer 3

Python 3.6, 61 bytes

f=lambda n,a=0,b=1:n and int(f'{a:b}{f(n-1,b,a+b)*2:b}',2)//2

Try it online!

Answer 4

Husk, 7 bytes

ḋṁḋ↑Θİf

Try it online!

Explanation

ḋṁḋ↑Θİf                              4
     İf    The Fibonacci numbers     [1,1,2,3,5,8..]
    Θ      Prepends 0                [0,1,1,2,3,5..]
   ↑     Take n elements from list   [0,1,1,2]
  ḋ        Convert to binary digits  [[0],[1],[1],[1,0]]
 ṁ       Map function then concat    [0,1,1,1,0]
ḋ        Convert from base 2         14

Answer 5

brainfuck, 397 bytes

>,[<++++++[->--------<]>>[->++++++++++<]>[-<+>]<<[->+<],]>+[-<<+>>[-[->+<]<<[->+>+<<]<[->+>+<<]>[-<+>]>>[-<<+>>]>]]<<[->+>>>>>+<<<<<<]>[-<+>]>+>>+>>>+<[[->-[<<]>]>[[-]<<<<<<<[->>[-<+>>+<]>[-<+>]<<<]<[->+>>>>>+<<<<<<]>[-<+>]>[-<+>]>[->>[-<+<<+>>>]<[->+<]<]>+>[-]>>+>]<<<<<[[->++>+>++<<<]>[-<+>]<<]>>>]>[-]<<<[-]<<[-]<<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>]<+[->++++++[-<++++++++>]<.<<<+]

Well, that was fun!

Takes ASCII input (e.g. 11), outputs result in ASCII.

Note: to try this online, make sure you set the cell size to 32 bits (on the right side of the webpage). If you do not enter an input, your browser might crash.

The interpreter cannot handle input of 11 and higher because it only supports up to 32 bits.

Try it on copy.sh

Explanation

>,[<++++++[->--------<]>>[->++++++++++<]>[-<+>]<<[->+<],]>+

Get decimal input and add one (to mitigate off-by-one)

[-<<+>>[-[->+<]<<[->+>+<<]<[->+>+<<]>[-<+>]>>[-<<+>>]>]]

Generate fibonacci numbers on the tape.

<<[->+>>>>>+<<<<<<]>[-<+>]>+>>+>>>+<

Set up for the incoming binary concatenation loop

---

So the cells contain the value, starting from the first position,

1 | 0 | 1 | 1 | 2 | 3 | 5 | ... | f_n | 0 | 1 | 0 | 1 | 0 | f_n | 1 | 0 | 0 | 0...

Look at these cells:

f_n | 0 | 1 | 0 | 1 | 0 | f_n | 1

I'll label this:

num | sum | cat | 0 | pow | 0 | num | pow

pow is there to find the maximal power of 2 that is strictly greater than num. sum is the concatenation of numbers so far. cat is the power of 2 that I would need to multiply the num in order to concatenate num in front of the sum (so I would be able to simply add).

---

[[->-[<<]>]>

Loop: Check whether f_n is strictly less than pow.

Truthy:

[[-]<<<<<<<[->>[-<+>>+<]>[-<+>]<<<]<[->+>>>>>+<<<<<<]>[-<+>]>[-<+>]>[->>[-<+<<+>>>]<[->+<]<]>+>[-]>>+>]

Zero out junk. Then, add num * cat to sum. Next, load the next Fibonacci number (= f_(n-1); if it doesn't exist, exit loop) and set cat to cat * pow. Prepare for next loop (zero out more junk, shift scope by one).

Falsey:

<<<<<[[->++>+>++<<<]>[-<+>]<<]

Set pow to 2 * pow, restore num.

]

Repeat until there is no Fibonacci number left.

---

>[-]<<<[-]<<[-]<<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>]<+[->++++++[-<++++++++>]<.<<<+]

Clean garbage. Take each digit of the resulting number and output each (in ascii).

Answer 6

Japt, 9 bytes

ÆMgX ¤Ã¬Í

Run it

Explanation:

ÆMgX ¤Ã¬Í
Æ     Ã     | Iterate X through the range [0...Input]
 MgX        |   Xth Fibonacci number
     ¤      |   Binary
       ¬    | Join into a string
        Í   | Convert into a base-2 number

Answer 7

Pyth, 22 bytes

JU2VQ=+Js>2J)is.BM<JQ2

Try it here

Explanation

JU2VQ=+Js>2J)is.BM<JQ2
JU2                       Set J = [0, 1].
   VQ       )             <Input> times...
     =+Js>2J              ... add the last 2 elements of J and put that in J.
                  <JQ     Take the first <input> elements...
               .BM        ... convert each to binary...
              s           ... concatenate them...
             i       2    ... and convert back to decimal.

Answer 8

JavaScript (Node.js), 70 65 58 57 55 bytes

• thanks to Shaggy for reducing 2 bytes ('0b+C-0 to '0b'+C)

f=(n,a=C=0,b=1)=>--n?f(n,b,a+b,C+=b.toString(2)):'0b'+C

Try it online!

Answer 9

Perl 6, 38 bytes

{:2([~] (0,1,*+*...*)[^$_]>>.base(2))}

Try it online!

Answer 10

05AB1E, 6 bytes

LÅfbJC

Try it online!

---

1-indexed.

Answer 11

x86, 37 22 21 bytes

Changelog

• -13 by using bsr. Thanks Peter Cordes!

• -2 by zeroing registers with mul.

• -1 by using a while loop instead of loop and push/pop ecx (credit Peter Cordes).

Input in edi, output in edx.

.section .text
.globl main
main:
        mov     $5, %edi            # n = 5

start:
        dec     %edi                # Adjust loop count
        xor     %ebx, %ebx          # b = 0
        mul     %ebx                # a = result = 0
        inc     %ebx                # b = 1

fib:
        add     %ebx, %eax          # a += b
        xchg    %eax, %ebx          # swap a,b
        bsr     %eax, %ecx          # c = (bits of a) - 1
        inc     %ecx                # c += 1
        sal     %cl, %edx           # result >>= c
        add     %eax, %edx          # result += a

        dec     %edi                # n--; do while(n)
        jnz     fib 

        ret

Objdump:

00000005 <start>:
   5:   4f                      dec    %edi
   6:   31 db                   xor    %ebx,%ebx
   8:   f7 e3                   mul    %ebx
   a:   43                      inc    %ebx

0000000b <fib>:
   b:   01 d8                   add    %ebx,%eax
   d:   93                      xchg   %eax,%ebx
   e:   0f bd c8                bsr    %eax,%ecx
  11:   41                      inc    %ecx
  12:   d3 e2                   shl    %cl,%edx
  14:   01 c2                   add    %eax,%edx
  16:   4f                      dec    %edi
  17:   75 f2                   jne    b <fib>
  19:   c3                      ret    

Answer 12

J, 36 Bytes

3 :'#.;<@#:"0]2}.(,{:+_2&{)^:y _1 1'

Explanation:

3 :'#.;<@#:"0]2}.(,{:+_2&{)^:y _1 1' | Explicit function
                 (,{:+_2&{)^:y _1 1  | Make n fibonacci numbers, with _1 1 leading
              2}.                    | Drop the _1 1
       <@#:"0]                       | Convert each item to binary and box
      ;                              | Unbox and join
    #.                               | Convert back from binary

Answer 13

Haskell, 89 76 75 bytes

f=0:scanl(+)1f
foldr1(\x y->y+x*2*2^floor(logBase 2.read.show$y)).(`take`f)

Ungolfed version:

import Data.Bits

fib = 0:scanl (+) 1 fib

catInt :: Integer -> Integer -> Integer
catInt x y = x' + y where
    position = floor $ succ $ logBase 2 $ realToFrac y
    x' = shift x position

answer :: Integer -> Integer
answer n = foldr1 catInt fib' where
    fib' = take n fib

Answer 14

APL (Dyalog), 26 22 bytes

4 bytes saved thanks to @H.PWiz

{2⊥∊2∘⊥⍣¯1¨1∧+∘÷\~⍵↑1}

Try it online!

Answer 15

Pari/GP, 59 bytes

n->fromdigits(concat([binary(fibonacci(i))|i<-[0..n-1]]),2)

Try it online!

Answer 16

APL+WIN, 55 bytes

Prompts for screen input of integer.

v←b←0 1⋄⍎∊(⎕-2)⍴⊂'v←v,c←+/¯2↑v⋄b←b,((1+⌊2⍟c)⍴2)⊤c⋄'⋄2⊥b

APL+WIN's maximum integer precision is 17 and integer limit is of the order of 10E300 therefore the maximum input number is 55 and the result is: 1.2492739026634838E300

Answer 17

Pyth, 27 bytes

JU2V-Q2=aJ+eJ@J_2)is.BM<JQ2

Test suite

Python 3 translation:

Q=eval(input())
J=list(range(2))
for i in range(Q-2):
    J.append(J[-1]+J[-2])
print(int(''.join(map("{0:b}".format,J[:Q])),2))

---

37 bytes

J[Z1)W<lJQ=aJ+eJ@J_2)Ig1QZ.?ijkm.BdJ2

Test suite

Python 3 translation:

Q=eval(input())
J=[0,1]
while len(J)<Q:
    J.append(J[-1]+J[-2])
if 1>=Q:
    print(0)
else:
    print(int(''.join(map("{0:b}".format,J)),2))

Answer 18

Python 3, 94 bytes

f=lambda n,a=[0,1]:n>len(a)and f(n,a+[sum(a[-2:])])or int(''.join(bin(v)[2:]for v in a[:n]),2)

Try it online!

Answer 19

Jelly, 6 bytes

ḶÆḞBFḄ

Try it online!

Ḷowered range -> nth ÆḞibonacci number -> from dec to Binary -> Flatten -> from Ḅinary to dec

Answer 20

MATL, 21 bytes

0li:"yy+]xx&h"@B]&hXB

Try it online!

Explanation

0l        % Push 0, then 1 (initial terms of the Fibonacci sequence)
i:"       % Do n times, where n is the input
  yy+     %   Duplicate top two numbers and push their sum
  ]       % End
xx        % Delete the last two results. The stack now contains the
          % first n Fibonacci numbers, starting at 0
&h        % Concatenate all numbers into a row vector
"         % For each
  @       %   Push current number
  B       %   Convert to binary. Gives a vector of 0 and 1
]         % End
&h        % Concatenate all vectors into a row vector
XB        % Convert from binary to decimal. Implicitly display

Answer 21

J, 25 bytes

2(#.;)<@#:@(1#.<:!|.)\@i.

Try it online!

Explanation

2(#.;)<@#:@(1#.<:!|.)\@i.  Input: n
                       i.  Range [0, n)
                     \@    For each prefix
                  |.         Reverse
                 !           Binomial coefficient (vectorized)
               <:            Decrement
            1#.              Sum
        #:                   Convert to binary
      <                      Box
    ;                        Link. Join the contents in each box
2 #.                         Convert to decimal from base 2

Answer 22

Python 3, 86 bytes

def f(N):
 a,b,l=0,1,''
 for _ in range(N):l+=format(a,'b');a,b=b,a+b
 return int(l,2)

Try it online!

Answer 23

Add++, 113 bytes

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,k,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{k}
D,w,@,BBbR
D,l,@,ßR€gp€w@0b]@¦+VcG2$Bb

Try it online!

Answer 24

PHP, 124 Bytes

Try it online!

So I was looking for a way to output fibonacci numbers using the series, until I found this. It turns out you can calculate the fibonacci series via rounding, so I tried the challenge with a recursive function.

I found the approach of "rounding" really interesting, also a professor showed me this a while ago.

Code

function f($n,$i=0,$b=''){ if($n>$i){$b.=
decbin(round(pow((sqrt(5)+1)/2,$i)/sqrt(5)));f($n,$i+1,$b);}else{echo bindec($b);}}

Explanation

function f($n,$i=0,$b=''){           #the function starts with $i=0, our nth-fib number
if($n>$i){                           #it stops once $n (the input) = the nth-fib
    $b.=decbin(                      #decbin returns an integer as bin, concatenates
        round(pow((sqrt(5)+1)/2,$i)/sqrt(5))    
                                       #the formula, basically roundign the expression
        );                           #it returns the (in this case) $i-th fib-number   
    f($n,$i+1,$b);                   #function is called again for the next index
}else{                               #and the current string for fibonacci

    echo bindec($b);                 #"echo" the result, bindec returns the base 10
                                     #value of a base 2 number
}
}

Also check this stackoverflow post the best answer refers to the same article on Wikipedia.

Answer 25

Stax, 9 bytes

ü1∞╓♪εw≤+

Run and debug it at staxlang.xyz!

Unpacked (10 bytes) and explanation:

vr{|5|Bm|B
v             Decrement integer from input. Stax's Fibonacci sequence starts with 1 :(
 r            Integer range [0..n).
  {    m      Map a block over each value in an array.
   |5           Push nth Fibonacci number.
     |B         Convert to binary.
        |B    Implicit concatenate. Convert from binary. Implicit print.

Answer 26

Julia 0.6, 65 bytes

f(n)=n<2?n:f(n-1)+f(n-2)
n->parse(BigInt,prod(bin.(f.(0:n-1))),2)

Try it online!

Answer 27

Ruby, 61 bytes

->n,a=0,b=1,s=""{s+="%b"%a;a,b=b,a+b;(n-=1)>0?redo:s.to_i(2)}

Try it online!

Answer 28

Jotlin, 59 bytes

g(l(0,1)){l(a.sum(),a[0])}.take(this).j(""){a[0].s(2)}.i(2)

Test Program

data class Test(val input: Int, val output: Long)

val tests = listOf(
    Test(1, 0),
    Test(2, 1),
    Test(3, 3),
    Test(4, 14),
    Test(5, 59),
    Test(6, 477),
    Test(7, 7640),
    Test(8, 122253),
    Test(9, 3912117),
    Test(10, 250375522)
)
fun Int.r() = g(l(0,1)){l(a.sum(),a[0])}.take(this).j(""){a[0].s(2)}.i(2)

fun main(args: Array<String>) {
    for (r in tests) {
        println("${r.input.r()} vs ${r.output}")
    }
}

It supports up to 10, changing .i(2) for .toLong(2) would support up to 14 if needed

Answer 29

R, 244 180 179 bytes

i=ifelse;g=function(n)i(n<3,1,g(n-1)+g(n-2))
a=scan(,"");i(a==1,0,sum(2^(which(rev(unlist(sapply(g(2:a-1),function(x)(y=rev(as.numeric(intToBits(x))))[which(!!y)[1]:32]))>0))-1)))

Try it online!

Saved some bytes by concatenating numeric vectors, not strings. Bloody special case for 0!

Answer 30

Python 2, 88 bytes

def f(n):
 a,b,r=0,1,"0"
 for _ in range(n-1):a,b=b,a+b;r+=bin(a)[2:]
 print int(r,2)

Answer 31

Python 3, 74 bytes

w='';a,b=0,1
exec('w+=bin(a)[2:];a,b=b,a+b;'*int(input()))
print(int(w,2))

Try it online!

Ungolfed:

w = ''
a, b = 0, 1
for _ in ' '*int(input()):  # for 0 to input:
    w += bin(a)[2:]         # append next fib. number as binary 
    a, b = b, a + b         #     without leading 0b
print(int(w,2))             # convert whole binary number to decimal int

Answer 32

Julia 0.6, 60 bytes

f(n,a=0,b=1,r=big(0))=n<1?r:f(n-1,b,a+b,r<<length(bin(a))|a)

Inspired by Dennis's bit fiddling python answer.

Try it online!