31
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Added test cases from 0 to 20 from tio.run/##DYxBCoQwDAC/…. Credit to @alephalpha for the program. \$\endgroup\$ – Nathan Wood Mar 30 '18 at 16:46
  • 6
    \$\begingroup\$ As it hasn't been said yet: Welcome to PPCG! Nice first challenge. \$\endgroup\$ – Laikoni Mar 30 '18 at 17:54
  • \$\begingroup\$ @Laikoni Thanks! \$\endgroup\$ – Nathan Wood Mar 30 '18 at 17:56
  • \$\begingroup\$ 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? \$\endgroup\$ – Peter Cordes Mar 30 '18 at 20:43
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Cordes Mar 30 '18 at 20:47

32 Answers 32

0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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