The Pell Numbers
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:
-
Given $n$, calculate the $n^{th}$ term of the sequence (0 or 1-indexed).
-
Given $n$, calculate the first $n$ elements of the sequence.
-
Output the sequence indefinitely.
Scoring
This is code-golf. Shortest answer in each language wins.
[APL (Dyalog Classic)], 20 18 …
3y ago
[Python 3], 39 bytes …
3y ago
J, 28 bytes ``` :}.@{.m&(+ …
2y ago
Japt, 11 9 bytes Outputs th …
3y ago
[Haskell], 21 bytes …
3y ago
J, 30 char ``` ((2%:2)%(1+ …
2y ago
C (gcc), 35 bytes ``` C f( …
2y ago
Lua 5.4.4, 51 bytes ``` lua …
2y ago
JavaScript, 26 bytes Output …
3y ago
9 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
APL (Dyalog Classic), 20 18 17 16 bytes
⊢/,+.×⍣⎕⍨∘.+⍨⌽⍳2
Matrix implementation, requires ⎕IO←0. Thanks to @Razetime for the idea, -3 bytes by me
APL (Dyalog Classic), 19 18 bytes
{⍵<2:⍵⋄+/∇¨⍵-1,⍳2}
Generic recursive implementation part 2
-1 byte thanks to @Razetime
APL (Dyalog Classic), 26 bytes
{×⍵:⌊0.5+(∇⍵-1)÷1-⍨2*÷2⋄1}
Random fun implementation
APL (Dyalog Classic), 26 bytes
{a←⍳⌈⍵÷2⋄(2*a)+.×⍵!⍨1+2×a}
Random fun implementation 2
Japt, 11 9 bytes
Outputs the first n terms. Change the h to g to get the nth 0-indexed term.
ÈÑ+ZÔÅÎ}h
ÈÑ+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
0 comment threads
J, 28 bytes
[:}.@{.m&(+/ .*)&m=.2 1,:1 0
Tacit matmul solve. x&u&y applies x to y n times.
0 comment threads
JavaScript, 26 bytes
Outputs the nth term, 0-indexed.
f=n=>n<2?n:f(--n)*2+f(--n)
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)]
0 comment threads
1 comment thread