Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
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
Search help
Notifications
Mark all as read See all your notifications »
Challenges

The Pell Numbers

+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)

9 answers

+2
−0

APL (Dyalog Classic), 20 18 17 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)
+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)
+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.

0 comment threads

+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 comment threads

+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.

0 comment threads

+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 comment threads

+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 comment threads

+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 comment threads

+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.

0 comment threads

Sign up to answer this question »

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!

Like what we're doing? Support us! Donate