How to resolve the algorithm Pell numbers step by step in the Common Lisp programming language
How to resolve the algorithm Pell numbers step by step in the Common Lisp programming language
Table of Contents
Problem Statement
Pell numbers are an infinite sequence of integers that comprise the denominators of the closest rational approximations to the square root of 2 but have many other interesting uses and relationships. The numerators of each term of rational approximations to the square root of 2 may also be derived from Pell numbers, or may be found by taking half of each term of the related sequence: Pell-Lucas or Pell-companion numbers.
The Pell numbers: 0, 1, 2, 5, 12, 29, 70, etc., are defined by the recurrence relation: Or, may also be expressed by the closed form formula:
Pell-Lucas or Pell-companion numbers: 2, 2, 6, 14, 34, 82, etc., are defined by a very similar recurrence relation, differing only in the first two terms: Or, may also be expressed by the closed form formula: or
The sequence of rational approximations to the square root of 2 begins: Starting from n = 1, for each term, the denominator is Pn and the numerator is Qn / 2 or Pn-1 + Pn.
Pell primes are Pell numbers that are prime. Pell prime indices are the indices of the primes in the Pell numbers sequence. Every Pell prime index is prime, though not every prime index corresponds to a prime Pell number.
If you take the sum S of the first 4n + 1 Pell numbers, the sum of the terms P2n and P2n + 1 will form the square root of S. For instance, the sum of the Pell numbers up to P5; 0 + 1 + 2 + 5 + 12 + 29 == 49, is the square of P2 + P3 == 2 + 5 == 7. The sequence of numbers formed by the sums P2n + P2n + 1 are known as Newman-Shank-Williams numbers or NSW numbers.
Pell numbers may also be used to find Pythagorean triple near isosceles right triangles; right triangles whose legs differ by exactly 1. E.G.: (3,4,5), (20,21,29), (119,120,169), etc. For n > 0, each right triangle hypotenuse is P2n + 1. The shorter leg length is the sum of the terms up to P2n + 1. The longer leg length is 1 more than that.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Pell numbers step by step in the Common Lisp programming language
Source code in the common programming language
(defun recurrent-sequence-2 (a0 a1 k1 k2 max)
"A generic function for any recurrent sequence of order 2, where a0 and a1 are the initial elements,
k1 is the factor of a(n-1) and k2 is the factor of a(n-2)"
(do* ((i 0 (1+ i))
(result (list a1 a0))
(b0 a0 b1)
(b1 a1 b2)
(b2 (+ (* k1 b1) (* k2 b0)) (+ (* k1 b1) (* k2 b0))) )
((> i max) (nreverse result))
(push b2 result) ))
(defun pell-sequence (max)
(recurrent-sequence-2 0 1 2 1 max) )
(defun pell-lucas-sequence (max)
(recurrent-sequence-2 2 2 2 1 max) )
(defun fibonacci-sequence (max) ; As an extra bonus, you get Fibonacci's numbers with this simple call
(recurrent-sequence-2 1 1 1 1 max) )
(defun rational-approximation-sqrt2 (max)
"Approximate square root of 2 with (P(n-1)+P(n-2))/P(n)"
(butlast (maplist #'(lambda (l) (/ (+ (first l) (or (second l) 0)) (or (second l) 1))) (pell-sequence max))) )
(defun pell-primes (max)
(do* ((i 0 (1+ i))
(result (list 1 0))
(indices nil)
(b0 0 b1)
(b1 1 b2)
(b2 (+ (* 2 b1) (* 1 b0)) (+ (* 2 b1) (* 1 b0))) )
((> (length result) max) (values (nreverse result)(nreverse indices)))
; primep can be any function determining whether a number is prime, for example,
; https://rosettacode.org/wiki/Primality_by_Wilson%27s_theorem#Common_Lisp
(when (primep b2)
(push b2 result)
(push i indices) )))
(pell-sequence 10)
(0 1 2 5 12 29 70 169 408 985 2378 5741 13860)
(pell-lucas-sequence 10)
(2 2 6 14 34 82 198 478 1154 2786 6726 16238 39202)
(rational-approximation-sqrt2 10)
(1 3/2 7/5 17/12 41/29 99/70 239/169 577/408 1393/985 3363/2378 8119/5741
19601/13860)
(mapcar #'float (rational-approximation-sqrt2 10))
(1.0 1.5 1.4 1.4166666 1.4137931 1.4142857 1.4142011 1.4142157 1.4142132
1.4142137 1.4142135 1.4142135)
(pell-primes 7)
(0 1 2 5 29 5741 33461 44560482149) ;
(0 1 3 9 11 27)
You may also check:How to resolve the algorithm Jacobsthal numbers step by step in the F# programming language
You may also check:How to resolve the algorithm Square-free integers step by step in the Python programming language
You may also check:How to resolve the algorithm Averages/Mode step by step in the Ada programming language
You may also check:How to resolve the algorithm Compound data type step by step in the Elena programming language
You may also check:How to resolve the algorithm ASCII art diagram converter step by step in the C programming language