### Communities

tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Notifications
Challenges

+4
−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?
You might want to add some details to your flag.
Why should this post be closed?

#### 1 comment thread

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?
You might want to add some details to your flag.

#### 1 comment thread

General comments (2 comments)
+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?
You might want to add some details to your flag.

#### 1 comment thread

General comments (8 comments)
+1
−0

# J, 28 bytes

[:}.@{.m&(+/ .*)&m=.2 1,:1 0


Try it online!

Tacit matmul solve. x&u&y applies x to y n times.

Why does this post require moderator attention?
You might want to add some details to your flag.

+1
−0

# Haskell, 21 bytes

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


Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

+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?
You might want to add some details to your flag.

+0
−0

# C (gcc), 35 bytes

f(n){return n<2?n:f(n-1)*2+f(n-2);}


Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

+0
−0

# Lua 5.4.4, 51 bytes

function f(n)return n<2 and n or f(n-1)*2+f(n-2)end


Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

+0
−0

# J, 30 char

((2*%:2)%~(1+%:2)&^-(1-%:2)&^)

   ((2*%:2)%~(1+%:2)&^-(1-%:2)&^) 0
0
((2*%:2)%~(1+%:2)&^-(1-%:2)&^) 1
1
((2*%:2)%~(1+%:2)&^-(1-%:2)&^) 2
2
((2*%:2)%~(1+%:2)&^-(1-%:2)&^) 8
408


Why does this post require moderator attention?
You might want to add some details to your flag.

+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?
You might want to add some details to your flag.