Challenges

+2
−0

# Introduction

The Pell(no, not Bell) Numbers are a simple, Fibonacci-like sequence, defined by the following relation:

$P_n=\begin{cases}0&\mbox{if }n=0;\\1&\mbox{if }n=1;\\2P_{n-1}+P_{n-2}&\mbox{otherwise.}\end{cases}$

They also have a closed form:

$P_n=\frac{\left(1+\sqrt2\right)^n-\left(1-\sqrt2\right)^n}{2\sqrt2}$

And a matrix multiplication based form, for the daring:

$\begin{pmatrix} P_{n+1} & P_n \\ P_n & P_{n-1} \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}^n.$

# Challenge

Your mission, should you choose to accept it, is to do any one of the following:

1. Given $n$, calculate the $n^{th}$ term of the sequence (0 or 1-indexed).

2. Given $n$, calculate the first $n$ elements of the sequence.

3. Output the sequence indefinitely.

# Scoring

This is code-golf. Shortest answer in each language wins.

Why does this post require moderator attention?
Why should this post be closed?

Test cases (1 comment)

+2
−0

# Python 3, 39 bytes

f=lambda x:x if x<2else 2*f(x-1)+f(x-2)


Generic recursive implementation

Try it online!

Why does this post require moderator attention?

+2
−0

# APL (Dyalog Classic), 201817 16 bytes

⊢/,+.×⍣⎕⍨∘.+⍨⌽⍳2


Matrix implementation, requires ⎕IO←0. Thanks to @Razetime for the idea, -3 bytes by me

Try it online!

# APL (Dyalog Classic), 19 18 bytes

{⍵<2:⍵⋄+/∇¨⍵-1,⍳2}


Generic recursive implementation part 2

-1 byte thanks to @Razetime

Try it online!

# APL (Dyalog Classic), 26 bytes

{×⍵:⌊0.5+(∇⍵-1)÷1-⍨2*÷2⋄1}


Random fun implementation

Try it online!

# APL (Dyalog Classic), 26 bytes

{a←⍳⌈⍵÷2⋄(2*a)+.×⍵!⍨1+2×a}


Random fun implementation 2

Try it online!

Why does this post require moderator attention?

+1
−0

# Japt, 11 9 bytes

Outputs the first n terms. Change the h to g to get the nth 0-indexed term.

ÈÑ+ZÔÅÎ}h


Try it

ÈÑ+ZÔÅÎ}h     :Implicit input of integer U
È             :Function taking an integer X and an array Z as arguments
Ñ            :  X*2
+           :  Plus
ZÔ         :  Reverse Z
Å        :  Slice off the first element
Î       :  Get the first element
}      :End function
h     :Starting with the array [0,1] repeatedly pass it (Z)
and its last element (X) through that function
pushing the result back to it each time until it reaches length U
Why does this post require moderator attention?

+1
−0

f=0:scanl((+).(*2))1f


Try it online!

Why does this post require moderator attention?

+0
−0

# JavaScript, 26 bytes

Outputs the nth term, 0-indexed.

f=n=>n<2?n:f(--n)*2+f(--n)


Try it online!

# JavaScript, 49 bytes

Outputs the first n terms as a comma delimited string.

f=n=>--n&&f(n)+[,(g=n=>n<2?n:g(--n)*2+g(--n))(n)]


Try it online!

Why does this post require moderator attention? 