18
\$\begingroup\$

The Fibonacci polynomials are a polynomial sequence defined as:

  • \$F_0(x) = 0\$
  • \$F_1(x) = 1\$
  • \$F_n(x) = x F_{n-1}(x) + F_{n-2}(x)\$

The first few Fibonacci polynomials are:

  • \$F_0(x) = 0\$
  • \$F_1(x) = 1\$
  • \$F_2(x) = x\$
  • \$F_3(x) = x^2 + 1\$
  • \$F_4(x) = x^3 + 2x\$
  • \$F_5(x) = x^4 + 3x^2 + 1\$

When you evaluate the Fibonacci polynomials for \$x=1\$, you get the Fibonacci numbers.

Task

Your task is to calculate the Fibonacci polynomial \$F_n(x)\$.

The usual rules apply. So you may:

  • Output all the Fibonacci polynomials.
  • Take an input \$n\$ and output the \$n\$-th Fibonacci polynomial.
  • Take an input \$n\$ and output the first \$n\$ Fibonacci polynomial.

You may use \$0\$-indexing or \$1\$-indexing.

You may output the polynomials in any reasonable format. Here are some example formats:

  • a list of coefficients, in descending order, e.g. \$x^9+8x^7+21x^5+20x^3+5x\$ is represented as [1,0,8,0,21,0,20,0,5,0];
  • a list of coefficients, in ascending order, e.g. \$x^9+8x^7+21x^5+20x^3+5x\$ is represented as [0,5,0,20,0,21,0,8,0,1];
  • a function that takes an input \$n\$ and gives the coefficient of \$x^n\$;
  • a built-in polynomial object.

You may pad the coefficient lists with \$0\$s. For example, the polynomial \$0\$ can represented as [], [0] or even [0,0].

You may also take two integers \$n, k\$, and output the coefficient of \$x^k\$ in \$n\$-th Fibonacci polynomial. You may assume that \$k<n\$.

This is , so the shortest code in bytes wins.

Testcases

Here I output lists of coefficients in descending order.

0 -> []
1 -> [1]
2 -> [1, 0]
3 -> [1, 0, 1]
4 -> [1, 0, 2, 0]
5 -> [1, 0, 3, 0, 1]
6 -> [1, 0, 4, 0, 3, 0]
7 -> [1, 0, 5, 0, 6, 0, 1]
8 -> [1, 0, 6, 0, 10, 0, 4, 0]
9 -> [1, 0, 7, 0, 15, 0, 10, 0, 1]
10 -> [1, 0, 8, 0, 21, 0, 20, 0, 5, 0]
11 -> [1, 0, 9, 0, 28, 0, 35, 0, 15, 0, 1]
12 -> [1, 0, 10, 0, 36, 0, 56, 0, 35, 0, 6, 0]
13 -> [1, 0, 11, 0, 45, 0, 84, 0, 70, 0, 21, 0, 1]
14 -> [1, 0, 12, 0, 55, 0, 120, 0, 126, 0, 56, 0, 7, 0]
15 -> [1, 0, 13, 0, 66, 0, 165, 0, 210, 0, 126, 0, 28, 0, 1]
\$\endgroup\$
4
  • \$\begingroup\$ I assume a coefficient list for \$n=0\$ may be [0] rather than empty? \$\endgroup\$ Jun 27 at 2:49
  • 1
    \$\begingroup\$ @UnrelatedString Both are OK. For other \$n\$ you can also pad the results with \$0\$, e.g., [0,1] for \$n=1\$. \$\endgroup\$
    – alephalpha
    Jun 27 at 2:51
  • \$\begingroup\$ Instead of output a function that takes an input m and gives the coefficient of x^m, can I take m as an additional input and give the coefficient of x^m? \$\endgroup\$ Jun 30 at 3:59
  • \$\begingroup\$ @CommandMaster Yes. You may also take two integers \$n, k\$, and output the coefficient of \$x^k\$ in \$n\$-th Fibonacci polynomial. You may assume that \$k<n\$. \$\endgroup\$
    – alephalpha
    Jun 30 at 4:01

16 Answers 16

10
\$\begingroup\$

J, 13 11 bytes

$1j1#]!&i.-

Attempt This Online!

-2 bytes thanks to @ovs

Looking at the nonzero columns, some keen eyes may have noticed that the columns look like binomial coefficients. And it actually is. (A related fact: summing the coefficients of nth polynomial gives nth Fibonacci number, which you can prove nicely in Lean)

...though we also need to handle the zero columns.

$1j1#]!&i.-    A train that takes n, and gives a vector of descending coeffs
     ]    -    n and -n respectively
       &i.     Apply range to both sides; 0..n-1 and n-1..0
      !        (right)C(left)
$1j1#          Insert a zero after each number and take first n numbers
\$\endgroup\$
0
7
\$\begingroup\$

Jelly, 5 bytes

Ż+¥¡1

Try it online!

Full program taking \$n\$ from STDIN and outputting coefficients ascending.

It's always felt a bit silly that the only "repeat" quick is designed for Fibonacci-like recurrences, but when it comes up I can't say it isn't useful.

         Since this is invoked as niladic, the initial left argument is 0.
    1    Starting with 1 on the right,
   ¡     repeat n times
  ¥      with the previous left argument replacing the right argument:
 +       vectorized add the right argument to
Ż        the left argument with a prepended 0.
\$\endgroup\$
6
\$\begingroup\$

R, 33 bytes

\(n,k,s=n+k)choose(s/2-.5,k)*s%%2

Attempt This Online!

Takes input as \$n,k\$ and outputs the coefficient of \$x^k\$ in \$n\$-th Fibonacci polynomial. Uses the formula from Wikipedia:

\$F(n,k) = {\frac{n+k-1}{2}\choose k}\$ if \$n\$ and \$k\$ have opposite parity.

\$\endgroup\$
4
\$\begingroup\$

Factor + math.polynomials, 45 bytes

{ } .s { 1 } [ dup . tuck "\0"p* p+ t ] loop

Try it online!

Prints the sequence forever as ascending coefficients.

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 14 bytes

#~Fibonacci~x&

Try it online!

Returns a polynomial in \$x\$.

If \$n,x\$ were valid input, Fibonacci alone would do.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 37 bytes

f=(n,k)=>n>1?f(n-1,k-1)+f(n-2,k):!k*n

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python, 62 bytes (@AnttiP)

f=lambda n:n>1and[*map(sum,zip(f(n-1)+[0]),[0,0]+f(n-2))]or[n]

Attempt This Online!

Old Python, 64 bytes

f=lambda n:n>1and[*map(sum,zip(f(n-1)+[0]),[0,0]+f(n-2))]or[1]*n

Attempt This Online!

Naive implementation of the defining recurrence.

\$\endgroup\$
1
  • \$\begingroup\$ -2 bytes with [1]*n => [n] \$\endgroup\$
    – AnttiP
    Jun 27 at 6:07
3
\$\begingroup\$

Vyxal, 8 bytes

ʁḂ$ƈ0ZfẎ

Try it Online!

Same idea as Bubbler's J answer.

ʁḂ$ƈ0ZfẎ
ʁ        # Exclusive zero range, 0..n-1
 Ḃ       # Bifurcate, push reverse without popping
  $      # Swap
   ƈ     # Binomial coefficients
    0Zf  # Append zero after each
       Ẏ # Only keep the first input items

Porting pajonk's Python answer is 8 bytes as well:

Vyxal, 8 bytes

+₌∷½⌊⁰ƈ*

Try it Online!

\$\endgroup\$
3
\$\begingroup\$

Python 2, 43 bytes

lambda n,k:2**(n*(n-~k))/(4**n-1)**-~k%2**n

Try it online!

Uses an arithmetic expression for the binomial adapted to \$ \binom{\frac{n+k-1}2}{k}\$ in a way that gives 0 if the top isn't a whole number.

Python 2, 48 bytes

f=lambda n,k:n>0and(k*k+n<2)+f(n-1,k-1)+f(n-2,k)

Try it online!

A recursive expression taken from tsh for Pascal's triangle but tilted.

\$\endgroup\$
2
\$\begingroup\$

Python3, 139 bytes:

def f(n):d={};F(n,d);return[d.get(i,0)for i in range(n-1,-1,-1)]
def F(n,d,c=0):
 if n==1:d[c]=d.get(c,0)+1
 if n>1:F(n-1,d,c+1);F(n-2,d,c)

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ range(n-1,-1,-1) is range(n)[::-1] => -2; walrus operator lets you define a variable in a parameter list: F(n,d:={}) => -1; you can use else instead of if n==1 if you use +n instead of +1 => -3; changing f into a lambda lets you use or instead of ;return => -3. You are also technically allowed to return the coefficients in ascending order so you can use range(n) for an extra 6 bytes. \$\endgroup\$ Jun 27 at 21:23
2
\$\begingroup\$

Charcoal, 32 bytes

NθF⊕θ⊞υ⎇‹ι²ιΣE…⮌υ²×κ∨λXχθI↨⊟υXχθ

Try it online! Link is to verbose version of code. Takes n as input and outputs the list of coefficients in descending order. Explanation:

Nθ

Input n.

F⊕θ

Repeat n+1 times.

⊞υ⎇‹ι²ιΣE…⮌υ²×κ∨λXχθ

Except for the first two numbers (which are just 0 and 1) multiply the last number by a very large base (10ⁿ) and add on the penultimate number.

I↨⊟υXχθ

Interpret the last value as a number in that very large base and output the "digits".

\$\endgroup\$
2
\$\begingroup\$

Python, 58 52 50 bytes

Edit: -8 bytes thanks to 301_Moved_Permanently.

lambda n,k:(n+k)%2*math.comb(n+k>>1,k)
import math

Attempt This Online!

Port of my R answer.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can change the and to * for -3 bytes, you can also drop the -1 as n+k is guaranteed an odd number and //2 will floor the result. \$\endgroup\$ Jun 27 at 13:16
  • \$\begingroup\$ If you change (n+k) to (n:=n+k) (Python 3.8+), you can change the (n+k-1) to ~-n for -1. EDIT: Nvm, removing the -1 is indeed shorter, as mentioned in the comment above. \$\endgroup\$ Jun 27 at 13:17
  • \$\begingroup\$ Also using math.comb and import math rather than from math import* gives you -1 byte. \$\endgroup\$ Jun 27 at 13:23
  • 1
    \$\begingroup\$ Order of operations: //2 and >>1 are equivalent, but the latter have lower priority than addition, so you can drop parenthesis. \$\endgroup\$ Jun 27 at 20:30
2
\$\begingroup\$

K (ngn/k), 22 bytes

{(0 0,x)+y,0}\[;!0;,1]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 8 6 bytes

λ0š0ζO

Outputs the infinite 1-based sequence. The inner coefficient-lists are output in ascending order for -2 bytes.

Try it online.

Since I was curious, a port of @Bubbler's J answer would be 9 bytes:

ݨÂc€¾RI£

Outputs the 0-based \$n^{th}\$ list, in descending order.

Try it online or verify all test cases.

Explanation:

λ         # Create a recursive environment,
          # to result in the infinite sequence
          # Implicitly starting at a(0)=1
          # Where every following a(n) is calculated as:
          #  (implicitly push the a(n-2)'th and a(n-1)'th terms
          #  (where a(-1)=0 in the first iteration)
 0š       #  Prepend a 0 in front of the top a(n-1)'th term
          #  (which implicitly converts integers to digit-lists first)
    ζ     #  Pair and zip/transpose the two lists,
   0      #  with 0 as filler since the lists are of unequal lengths
     O    #  Sum each inner pair
          # (after which the infinite sequence is output implicitly)

Ý         # Push a list in the range [0, (implicit) input]
 ¨        # Remove the last item to make the range [0,input)
  Â       # Bifurcate; short for Duplicate & Reverse copy
   c      # Calculate the binomial coefficient of the values in the two lists at
          # the same positions
    €¾    # Prepend a 0 in front of each item
      R   # Reverse this list
       I£ # Keep just the first input amount of items
          # (after which this list is output implicitly as result)
\$\endgroup\$
4
  • \$\begingroup\$ +DÉ*<;²c also works for 8 bytes, outputting the k-th coefficient in the n-th polynomial \$\endgroup\$ Jun 30 at 4:12
  • \$\begingroup\$ @CommandMaster That seems to output the 0-based \$(n-k-1)^{th}\$ coefficient (or 1-based \$(n-k)^{th}\$) in the \$n^{th}\$ polynomial, though. E.g. n=11,k=2 outputs 15 instead of 9: try it online. \$\endgroup\$ Jun 30 at 7:23
  • 1
    \$\begingroup\$ The 11-th Fibonacci polynomial is \$ x^{10} + 9 x^8 + 28 x^6 + 35 x^4 + 15 x^2 + 1\$, and 15 is the coefficient of \$ x^2 \$, so 15 is a correct answer \$\endgroup\$ Jun 30 at 12:02
  • \$\begingroup\$ @CommandMaster Good point. I was still looking at it from the descending list perspective, but if you explain it like that it indeed makes total sense! But maybe it's better if you post it as a separated answer? It's quite a bit different than mine, and I also already golfed 2 bytes off it. \$\endgroup\$ Jun 30 at 12:05
1
\$\begingroup\$

Desmos, 62 41 bytes

L=[n...0]
f(n)=mod(L+n,2)nCr((n+L-1)/2,L)

Function f outputs a list of coefficients in descending order, with a leading zero.

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 22 bytes SBCS

{a←¯1+⍳⍵⋄⍵↑,⍉↑(a!⌽a)0}

Try it on APLgolf!

\$\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.