31

3

## 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 , so the answer with the shortest number of bytes wins!

1

Added test cases from 0 to 20 from https://tio.run/##DYxBCoQwDAC/Ejwl0Ih63vUj4qFWIjlsWrK9CP69dmDmOCW68lWawBea8Sqef6deWv@YsqVYcTvUot8oemSLKSkq0aMf3qZxNJ73ncJCTbKj9ckcYJkCFFerOEBnAOvy2iNoRNRe. Credit to @alephalpha for the program.

– Nathan Wood – 2018-03-30T16:46:41.287

6As it hasn't been said yet: Welcome to PPCG! Nice first challenge. – Laikoni – 2018-03-30T17:54:33.670

@Laikoni Thanks! – Nathan Wood – 2018-03-30T17:56:34.060

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 – 2018-03-30T20:43:54.777

@PeterCordes I'd say either is allowed, as long as it's at least int32 or that int. – Nathan Wood – 2018-03-30T20:46:58.360

1And 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 – 2018-03-30T20:47:00.897

The output should be an integer – Nathan Wood – 2018-03-30T20:50:12.577

Ok, so you were just describing it in terms of implementation in a language where you explode each bit to a list element, instead of normal bit shifts / manipulation where the result of packing bits together already is an integer. – Peter Cordes – 2018-03-30T21:10:27.370

@PeterCordes It goes like this. Calculate fibonacci up to N 4 -> [0, 1, 1, 2], change to binary [0, 1, 1, 10], concatenate it like a string 01110, convert it from base 2 to base 10 14 – Nathan Wood – 2018-03-30T21:12:27.300

Well yeah if you had a string like "01110" then you'd have some conversion to do. But if you had an integer like 0b01110 (note lack of quote marks; I'm using C++ syntax to represent a constant using ASCII digits for base 2, but I'm talking about those bits packed into an integer already), it would already also represent 14 in decimal, and 0xe in hex. But it's still stored in memory / a register in binary until you print it to a string. Dennis's Python answer doesn't have any list->decimal function because it never unpacked the bits in the first place (except to find log2(a). – Peter Cordes – 2018-03-30T21:19:56.513

Numbers in computers (like an int in C) aren't "in decimal" until you print / convert them to strings, unless you're using binary-coded-decimal or something weird like that.

– Peter Cordes – 2018-03-30T21:20:38.013

Because no one have mentioned that, you can post your challenge in the sandbox before posting on main. (read the link for more details)

– user202729 – 2018-03-31T15:11:46.390

I would ask that you avoid using "dec" as an abbreviation for "decimal. "Dec" is the name for ten in base 12 which made me confused. – stuart stevenson – 2018-03-31T16:32:40.183

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!

1Nice, I was just trying to achieve this style. – Jonathan Allan – 2018-03-30T17:46:50.093

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


1Messing 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. – miles – 2018-03-31T05:06:19.167

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!

7

# 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


Welcome to PPCG! :) – James – 2018-03-30T23:17:04.693

7

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

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


1Bah! Beat me to it! – Shaggy – 2018-03-30T16:57:31.987

1@Shaggy I knew this one was going to be a race against you :P – Oliver – 2018-03-30T16:59:31.033

4

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


3

# JavaScript (Node.js), 70655857 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!

You can ditch the -0 at the end to save another 2 bytes. – Shaggy – 2018-03-30T21:51:45.383

3

{:2([~] (0,1,*+*...*)[^$_]>>.base(2))}  Try it online! 1Note 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) – Brad Gilbert b2gills – 2018-03-30T18:07:28.653 2 # 05AB1E, 6 bytes LÅfbJC  Try it online! 1-indexed. 2 # x86, 3722 21 bytes Changelog • -13 by using bsr. Thanks Peter Cordes! • -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>:
d:   93                      xchg   %eax,%ebx
e:   0f bd c8                bsr    %eax,%ecx
11:   41                      inc    %ecx
12:   d3 e2                   shl    %cl,%edx
16:   4f                      dec    %edi
17:   75 f2                   jne    b <fib>
19:   c3                      ret


1Use 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. – Peter Cordes – 2018-03-30T20:54:06.833

@PeterCordes the source of this convoluted method is the result of a headache and a misinterpretation of the problem spec to use base 10 instead of base 2. I will fix. – qwr – 2018-03-31T01:36:30.953

Heh, see my comments on the question. It drives me nuts when people think that integers are "in decimal" because that's how they wrote the constant. This fuzzy thinking may be due to golfing and other languages that have functions to convert an integer to a list / array of elements, 1 per bit, and then using list manipulation instead of bitwise operations on integers. Although I'm not sure how the "base 10" part of the problem statement got you, more like the way the examples were written with all bits separated leads you to unnecessary unpacking. Headache would do it, though :/ – Peter Cordes – 2018-03-31T01:57:17.990

1You 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. – Peter Cordes – 2018-03-31T02:04:11.843

@PeterCordes aw I got so excited to use loop. :( – qwr – 2018-03-31T02:08:06.353

1You 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. – Peter Cordes – 2018-03-31T02:08:29.740

1

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.

– Peter Cordes – 2018-03-31T02:12:54.480

re: result in EAX, no nvm, result stays in the same register the whole time, and you need EAX to be one of the Fibonacci registers for xchg. So returning in EAX to make this MS __fastcall would cost an extra byte. – Peter Cordes – 2018-03-31T02:22:34.523

1Anyway, 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. – Peter Cordes – 2018-03-31T02:35:23.670

@PeterCordes Now that I think about it, working with ax is like working with ah and al at the same time. I wonder if there are any cool tricks involving that. – qwr – 2018-03-31T16:40:36.597

Yup, sure. integer -> 2-digit decimal ASCII number with div %bl / add $0x3030, %ax (especially in 16-bit code) to give you a 2-byte ASCII string which stores to memory in printing order (10's place first, in AL). You can even use aam to divide AL (rather than AX) by an immediate (default is 10), but the results go in opposite registers from div. Or sometimes lodsw / xchg al,ah, maybe as part of sorting byte elements, again especially in x86-16. – Peter Cordes – 2018-03-31T16:57:45.563 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  2 # Haskell, 8976 75 bytes f=0:scanl(+)1f foldr1(\x y->y+x*2*2^floor(logBase 2.read.show$y)).(takef)


Ungolfed version:

import Data.Bits

fib = 0:scanl (+) 1 fib

catInt :: Integer -> Integer -> Integer
catInt x y = x' + y where
D,w,@,BBbR
D,l,@,ßR€gp€w@0b]@¦+VcG2$Bb  Try it online! 1 ## 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.

Interesting way to do it! – Nathan Wood – 2018-04-04T21:13:35.533

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.


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!

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!

0

# 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

0

# R, 244180 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!

Functions are acceptable. Also it is much more efficient to shift the result left by the number of bits then to bother with numeric vectors. See my or Dennis's python answer. This has the added benefit of handling the 0 case. – qwr – 2018-03-31T14:08:50.697

https://codegolf.stackexchange.com/questions/4024/tips-for-golfing-in-r R golfing is too much for me :/ – qwr – 2018-03-31T14:17:03.663

@qwr The answer is not a function; I am creating a helper function because it must be sapply’d to a vector due to the fact that it is recursive. It cannot be all wrapped into one line. As you see, the programme prompts for user’s input and then returns the answer. One byte can be saved by creating a shortcut for ifelse. And... we can remove ,"" from scan, yes. – Andreï Kostyrka – 2018-03-31T16:07:42.447

0

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


0

# 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


0

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