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

Dashboard
Notifications
Mark all as read
Challenges

The Pell Numbers

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

0 comments

3 answers

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

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

2 comments

Not sure why short circuiting isn't working here: Try it online! Razetime‭ 7 days ago

@Razetime‭ Because when x=0 the condition (x<2and x) evaluates to 0, which is falsy, so or can't short-circuit. Hakerh400‭ 5 days ago

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

8 comments

fun matrix multiplication(20): 4⊃,+.×⍣⎕⍨2 2⍴2 1 1 0 Razetime‭ 8 days ago

-1 byte Razetime‭ 8 days ago

@Razetime i shaved 2 bytes off your fun matrix implementation - its now tied Quintec‭ 8 days ago

I think your link is wrong, and the program doesn't seem to work correctly Razetime‭ 8 days ago

I got 19 bytes: ⊢/,+.×⍣⎕⍨2-⍨∘.+⍨⌽⍳2 from it Razetime‭ 8 days ago

Show 3 more comments

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!