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 code-golf, 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.2876As 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.300Well yeah if you had a

stringlike`"01110"`

then you'd have some conversion to do. But if you had anintegerlike`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.513Numbers in computers (like an

– Peter Cordes – 2018-03-30T21:20:38.013`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.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.390I 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