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!

Added test cases from 0 to 20 from tio.run/##DYxBCoQwDAC/…. Credit to @alephalpha for the program. — Nathan Wood, Commented Mar 30, 2018 at 16:46
As it hasn't been said yet: Welcome to PPCG! Nice first challenge. — Laikoni, Commented Mar 30, 2018 at 17:54
Where exactly does the language-specific limit apply? Would a C function that returns a 32-bit integer be allowed? Like int32_t binary_concat_Fib(int n), which would limit the resulting output value to 2^31-1. i.e. you get to assume all the concatenated bits fit in an integer. Or should the function work up to the point where the largest Fibonacci number doesn't fit in an integer on its own, so concatenating the bits takes extended precision? — Peter Cordes, Commented Mar 30, 2018 at 20:43
@PeterCordes I'd say either is allowed, as long as it's at least int32 or that int. — Nathan Wood, Commented Mar 30, 2018 at 20:46
And does the "converts to decimal" have to be explicit, calling an integer->string function or writing one yourself? Concatenating the bits into a single integer gives you a representation of the final value. If I understand correctly, Dennis's Python answer is returning an integer, leaving it up to the caller to turn that value into a decimal string or do whatever with it. Integer values in computer languages that support bit-shift operators are naturally binary, not decimal, unless they're stored in strings. In languages without shifts / bitwise operators, nothing implies any base. — Peter Cordes, Commented Mar 30, 2018 at 20:47

Dennis · Accepted Answer · 2018-03-30 17:52:17Z

11

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!

edited Mar 30, 2018 at 17:52

answered Mar 30, 2018 at 17:33

Dennis

211k41 gold badges370 silver badges825 bronze badges

1

\$\begingroup\$ Nice, I was just trying to achieve this style. \$\endgroup\$
– Jonathan Allan
Commented Mar 30, 2018 at 17:46

Add a comment |

Jonathan Allan · Accepted Answer · 2018-03-30 15:51:21Z

10

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

edited Mar 30, 2018 at 15:51

answered Mar 30, 2018 at 15:44

Jonathan Allan

110k7 gold badges65 silver badges282 bronze badges

1

\$\begingroup\$ Messing around with the new quicks, I found that the first n Fibonacci numbers can also be found using Ṛc’SƲƤ which could be useful for similar sequences. \$\endgroup\$
– miles
Commented Mar 31, 2018 at 5:06

Add a comment |

Dennis · Accepted Answer · 2018-03-30 18:44:59Z

9

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!

edited Mar 30, 2018 at 18:44

answered Mar 30, 2018 at 17:50

Dennis

211k41 gold badges370 silver badges825 bronze badges

Add a comment |

Fyr · Accepted Answer · 2018-04-05 15:36:57Z

8

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

edited Apr 5, 2018 at 15:36

answered Mar 30, 2018 at 23:15

Fyr

6313 silver badges4 bronze badges

\$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$
– DJMcMayhem
Commented Mar 30, 2018 at 23:17

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 30, 2018 at 16:52

Oliver

7,9022 gold badges18 silver badges38 bronze badges

1

\$\begingroup\$ Bah! Beat me to it! \$\endgroup\$
– Shaggy
Commented Mar 30, 2018 at 16:57
1

\$\begingroup\$ @Shaggy I knew this one was going to be a race against you :P \$\endgroup\$
– Oliver
Commented Mar 30, 2018 at 16:59

Add a comment |

user48543user48543 · Accepted Answer · 2018-03-30 16:51:51Z

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.

nwellnhof · Accepted Answer · 2018-03-30 17:48:07Z

3

Perl 6, 38 bytes

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

Try it online!

answered Mar 30, 2018 at 17:48

nwellnhof

10.6k1 gold badge19 silver badges38 bronze badges

1

\$\begingroup\$ Note that this starts to get noticeably slower with inputs above 200. It takes about 8 seconds to generate the output with an input of 1000. (20 seconds if you include printing it) \$\endgroup\$
– Brad Gilbert b2gills
Commented Mar 30, 2018 at 18:07

Add a comment |

DanielIndie · Accepted Answer · 2018-03-31 05:40:22Z

3

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!

edited Mar 31, 2018 at 5:40

answered Mar 30, 2018 at 16:24

DanielIndie

1,2406 silver badges5 bronze badges

\$\begingroup\$ You can ditch the -0 at the end to save another 2 bytes. \$\endgroup\$
– Shaggy
Commented Mar 30, 2018 at 21:51

Add a comment |

Magic Octopus Urn · Accepted Answer · 2018-03-30 16:08:07Z

2

05AB1E, 6 bytes

LÅfbJC

Try it online!

1-indexed.

answered Mar 30, 2018 at 16:08

Magic Octopus Urn

20.8k5 gold badges62 silver badges136 bronze badges

Add a comment |

Bolce Bussiere · Accepted Answer · 2018-03-30 22:11:41Z

2

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

answered Mar 30, 2018 at 22:11

Bolce Bussiere

1,0907 silver badges9 bronze badges

Add a comment |

qwr · Accepted Answer · 2018-03-31 16:37:36Z

2

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

edited Mar 31, 2018 at 16:37

answered Mar 30, 2018 at 19:24

qwr

12.3k6 gold badges47 silver badges80 bronze badges

1

\$\begingroup\$ Use lea to shift-and-add in fib2. Also, extracting each bit one at a time is unnecessary. Use bsr %eax, %ecx to find the number of bits in the binary representation, and use a shift by CL / or to merge, like Dennis's Python answer is doing. \$\endgroup\$
– Peter Cordes
Commented Mar 30, 2018 at 20:54
1

\$\begingroup\$ You need cl for shift counts, so take your loop counter in a different reg (like %edi) and use dec %edi / jnz (3 bytes in 32-bit code, 4 bytes in 64-bit). In 32-bit code, that saves 1 byte total from dropping the push/pop ecx. Don't fall into the trap of using loop when it makes the problem harder, not easier. (Your calling convention is already custom, clobbering %ebx, so don't call your function main) You might be able to return in EAX while still taking advantage of 1-byte xchg, no need to be non-standard if you don't need to. \$\endgroup\$
– Peter Cordes
Commented Mar 31, 2018 at 2:04
1

\$\begingroup\$ You can replace the extra inc %ecx of the shift count with an extra left-shift as you add, using lea (%eax, %edx, 2), %edx. Neutral in bytes for 32-bit, saves one for x86-64. But saves an instruction. \$\endgroup\$
– Peter Cordes
Commented Mar 31, 2018 at 2:08
1

\$\begingroup\$ Every time I end up using loop in code golf, I feel dirty. Well not quite, but disappointed that I couldn't find an equally small implementation that avoided that slow instruction; outside of code golf, loop is one of my pet peeves. I wish it was fast on modern CPUs, because it would be very nice for extended-precision loops without partial-flag stalls, but it's not and should be considered only as an obscure size optimization instruction that makes your code slow. \$\endgroup\$
– Peter Cordes
Commented Mar 31, 2018 at 2:12
1

\$\begingroup\$ Anyway, nice job. Other than push/pop/loop -> dec/jnz, I don't see any savings, just the LEA speedup that's neutral in code-size. I'd always wondered if there was ever a real use case for the xor/mul trick to zero three registers (do you ever need that many zeroes?), but using that as part of creating a 1 makes it more sensible. \$\endgroup\$
– Peter Cordes
Commented Mar 31, 2018 at 2:35

| Show 6 more comments

Uriel · Accepted Answer · 2018-03-31 19:47:55Z

2

APL (Dyalog), 26 22 bytes

4 bytes saved thanks to @H.PWiz

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

Try it online!

edited Mar 31, 2018 at 19:47

answered Mar 31, 2018 at 18:18

Uriel

13.2k4 gold badges17 silver badges45 bronze badges

\$\begingroup\$ Save 2 bytes on the fibonacci bit \$\endgroup\$
– H.PWiz
Commented Mar 31, 2018 at 18:52
\$\begingroup\$ Even shorter \$\endgroup\$
– H.PWiz
Commented Mar 31, 2018 at 19:06

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 31, 2018 at 3:14

user79465

1

\$\begingroup\$ Welcome to PPCG and Haskell golfing in particular! A shorter way to generate an infinite list of Fibonacci numbers is f=0:scanl(+)1f (taken from here). Functions can be anonymous, so you can drop the leading g=, see our Guide to Ggolfing Rules in Haskell. \$\endgroup\$
– Laikoni
Commented Mar 31, 2018 at 9:47
\$\begingroup\$ Thanks! That compensates for some of the longer functions used. I spent a while trying to find a way to implement bit-shifting in a more concise way, but came up short. \$\endgroup\$
– user79465
Commented Mar 31, 2018 at 18:25
\$\begingroup\$ You can replace $realToFrac y with .read.show$y for one byte \$\endgroup\$
– H.PWiz
Commented Mar 31, 2018 at 18:59

Add a comment |

hakr14 · Accepted Answer · 2018-04-12 03:51:32Z

2

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

edited Apr 12, 2018 at 3:51

answered Mar 30, 2018 at 16:20

hakr14

5,0141 gold badge11 silver badges18 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2018-03-30 15:46:12Z

1

Pari/GP, 59 bytes

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

Try it online!

answered Mar 30, 2018 at 15:46

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 30, 2018 at 16:18

Graham

6,8461 gold badge15 silver badges11 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2018-03-30 16:55:38Z

1

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!

edited Mar 30, 2018 at 16:55

answered Mar 30, 2018 at 16:47

Jonathan Allan

110k7 gold badges65 silver badges282 bronze badges

Add a comment |

chromaticiT · Accepted Answer · 2018-03-30 19:21:32Z

1

Jelly, 6 bytes

ḶÆḞBFḄ

Try it online!

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

answered Mar 30, 2018 at 19:21

chromaticiT

2191 silver badge5 bronze badges

\$\begingroup\$ Didn't understand this language but I thought the output is not always correct. e.g. Input 10 and you will get an 16024033463, it is incorrect (correct answer is 250375522). \$\endgroup\$
– Guoyang Qin
Commented Mar 31, 2018 at 8:51
\$\begingroup\$ @AbrahamChin Input 10 returns 250375522 \$\endgroup\$
– Dennis
Commented Mar 31, 2018 at 15:31
\$\begingroup\$ Equivalent, duplicate answer, just a heads up \$\endgroup\$
– caird coinheringaahin g ♦
Commented Apr 2, 2018 at 15:11

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

jrtapsell · Accepted Answer · 2018-03-31 00:44:40Z

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

miles · Accepted Answer · 2018-03-31 05:27:39Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 31, 2018 at 8:45

Guoyang Qin

5834 silver badges8 bronze badges

Add a comment |

caird coinheringaahin g · Accepted Answer · 2018-04-02 15:11:27Z

1

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!

answered Apr 2, 2018 at 15:11

caird coinheringaahin g♦

50.3k11 gold badges128 silver badges354 bronze badges

Add a comment |

Nathan Wood · Accepted Answer · 2018-04-04 21:32:56Z

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.

\$\begingroup\$ Interesting way to do it! \$\endgroup\$
– Nathan Wood
Commented Apr 4, 2018 at 21:13 — Nathan Wood, Commented Apr 4, 2018 at 21:13

Khuldraeseth na'Barya · Accepted Answer · 2018-04-05 15:53:11Z

1

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.

answered Apr 5, 2018 at 15:53

Khuldraeseth na'Barya

3,41819 silver badges34 bronze badges

Add a comment |

gggg · Accepted Answer · 2018-04-05 16:24:51Z

1

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!

answered Apr 5, 2018 at 16:24

gggg

2,01511 silver badges9 bronze badges

Add a comment |

chunes · Accepted Answer · 2023-05-09 02:17:42Z

1

Factor + `project-euler.025`, 37 bytes

[ iota [ fib >bin ] map-concat bin> ]

Try it online!

answered May 9, 2023 at 2:17

chunes

26.8k3 gold badges24 silver badges53 bronze badges

Add a comment |

lyxal · Accepted Answer · 2023-05-09 12:47:18Z

1

Vyxal, 44 bits¹, 5.5 bytes

ʁ∆FbfB

Try it Online!

Explained

ʁ∆FbfB
ʁ      # range [0, input)
 ∆F    # 0-indexed fibonacci number of each
   bf  # convert each to binary and flatten the list
     B # convert that from binary

answered May 9, 2023 at 12:47

lyxal

34.3k2 gold badges64 silver badges141 bronze badges

Add a comment |

Reinstate Monica -- notmaynard · Accepted Answer · 2018-03-30 19:29:22Z

0

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!

answered Mar 30, 2018 at 19:29

Reinstate Monica -- notmaynard

1,0835 silver badges9 bronze badges

Add a comment |

Binary Fibonacci

Challenge

Test cases

36 Answers 36

Python, 64 bytes

Jelly, 7 6 bytes

How?

Python 3.6, 61 bytes

Husk, 7 bytes

Explanation

brainfuck, 397 bytes

Explanation

Japt, 9 bytes

Explanation:

Pyth, 22 bytes

Explanation

Perl 6, 38 bytes

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

05AB1E, 6 bytes

J, 36 Bytes

Explanation:

x86, 37 22 21 bytes

APL (Dyalog), 26 22 bytes

Haskell, 89 76 75 bytes

Pyth, 27 bytes

37 bytes

Pari/GP, 59 bytes

APL+WIN, 55 bytes

Python 3, 94 bytes

Jelly, 6 bytes

MATL, 21 bytes

Explanation

Jotlin, 59 bytes

Test Program

J, 25 bytes

Explanation

Python 3, 86 bytes

Add++, 113 bytes

PHP, 124 Bytes

Stax, 9 bytes

Unpacked (10 bytes) and explanation:

Julia 0.6, 65 bytes

Factor + project-euler.025, 37 bytes

Vyxal, 44 bits1, 5.5 bytes

Explained

Ruby, 61 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Factor + `project-euler.025`, 37 bytes

Vyxal, 44 bits¹, 5.5 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
binary
fibonacci
or ask your own question.