Pell numbers: Difference between revisions
m (→{{header|J}}) |
m (Should link to the rosettacode Pythagorean Triples, also) |
||
Line 89:
;* [[oeis:A002315|OEIS:A002315 - NSW numbers]] (Newman-Shank-Williams numbers)
;* [[wp:Pythagorean_triple|Wikipedia: Pythagorean triple]]
;* [[Pythagorean triples]]
|
Revision as of 22:28, 5 March 2022
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:
P0 = 0;
P1 = 1;
Pn = 2 × Pn-1 + Pn-2;
Or, may also be expressed by the closed form formula:
Pn = ((1 + √2)n - (1 - √2)n) / (2 × √2);
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:
Q0 = 2;
Q1 = 2;
Qn = 2 × Qn-1 + Qn-2;
Or, may also be expressed by the closed form formula:
Qn = (1 + √2)n + (1 - √2)n;
or
Qn = P2n / Pn;
The sequence of rational approximations to the square root of 2 begins:
1/1, 3/2, 7/5, 17/12, 41/29, ...
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.
- Task
- Find and show at least the first 10 Pell numbers.
- Find and show at least the first 10 Pell-Lucas numbers.
- Use the Pell (and optionally, Pell-Lucas) numbers sequence to find and show at least the first 10 rational approximations to √2 in both rational and decimal representation.
- Find and show at least the first 10 Pell primes.
- Find and show at least the first 10 indices of Pell primes.
- Find and show at least the first 10 Newman-Shank-Williams numbers
- Find and show at least the first 10 Pythagorean triples corresponding to near isosceles right triangles.
- See also
- Wikipedia: Pell number
- OEIS:A000129 - Pell numbers
- OEIS:A002203 - Companion Pell numbers (Pell-Lucas numbers)
- OEIS:A001333 - Numerators of continued fraction convergents to sqrt(2) (Companion Pell numbers / 2)
- OEIS:A086383 - Prime terms in the sequence of Pell numbers
- OEIS:A096650 - Indices of prime Pell numbers
- OEIS:A002315 - NSW numbers (Newman-Shank-Williams numbers)
- Wikipedia: Pythagorean triple
- Pythagorean triples
J
As detailed in the task description, there's a variety of ways to compute these values.
For example:
<lang J>nextPell=: , 1 2+/ .*_2&{. NB. pell, list extender Pn=: (%:8) %~(1+%:2)&^ - (1-%:2)&^ NB. pell, closed form Qn=: (1+%:2)&^ + (1-%:2)&^ NB. pell lucas, closed form QN=: +: %&Pn ] NB. pell lucas, closed form qn=: 2 * (+&Pn <:) NB. pell lucas, closed form</lang>
Thus:
<lang J> nextPell^:9(0 1) 0 1 2 5 12 29 70 169 408 985 2378
Pn i.11
0 1 2 5 12 29 70 169 408 985 2378
nextPell^:9(2 2)
2 2 6 14 34 82 198 478 1154 2786 6726
Qn i.11
2 2 6 14 34 82 198 478 1154 2786 6726
QN i.11
0 2 6 14 34 82 198 478 1154 2786 6726
qn i.11
2 2 6 14 34 82 198 478 1154 2786 6726</lang>
QN (which is defined as P2n/Pn) doesn't get the first element of the pell lucas sequence right. We could fix this by changing the definition:
<lang J>QN=: 2 >. +: %&Pn ]
QN i.11
2 2 6 14 34 82 198 478 1154 2786 6726</lang>
Continuing... the first ten rational approximations to √2 here would be: <lang J> }.(% _1}. +//.@,:~) nextPell^:9(0 1) 1 0.666667 0.714286 0.705882 0.707317 0.707071 0.707113 0.707106 0.707107 0.707107
}.(% _1}. +//.@,:~) nextPell^:9(0 1x)
1 2r3 5r7 12r17 29r41 70r99 169r239 408r577 985r1393 2378r3363</lang>
The first ten pell primes are: <lang J> 10{.(#~ 1&p:)nextPell^:99(0 1x) 2 5 29 5741 33461 44560482149 1746860020068409 68480406462161287469 13558774610046711780701 4125636888562548868221559797461449</lang>
Their indices are: <lang J> 10{.I. 1&p:nextPell^:99(0 1x) 2 3 5 11 13 29 41 53 59 89</lang>
The NSW numbers are the sums of (non-overlapping) pairs of pell numbers, or: <lang J> _2 +/\ nextPell^:20(0 1x) 1 7 41 239 1393 8119 47321 275807 1607521 9369319 54608393 </lang>
The first ten pell based pythogorean triples would be: <lang J> }.(21$1 0)#|:(}.,~0 1+/+/\@}:)nextPell^:(20)0 1
3 4 5 20 21 29 119 120 169 696 697 985 4059 4060 5741 23660 23661 33461 137903 137904 195025 803760 803761 1136689 4684659 4684660 6625109
27304196 27304197 38613965</lang>
Raku
<lang perl6>my $pell = cache lazy 0, 1, * + * × 2 … *; my $pell-lucas = lazy 2, 2, * + * × 2 … *;
my $upto = 20;
say "First $upto Pell numbers:\n" ~ $pell[^$upto];
say "\nFirst $upto Pell-Lucas numbers:\n" ~ $pell-lucas[^$upto];
say "\nFirst $upto rational approximations of √2 ({sqrt(2)}):\n" ~ (1..$upto).map({ sprintf "%d/%d - %1.16f", $pell[$_-1] + $pell[$_], $pell[$_], ($pell[$_-1]+$pell[$_])/$pell[$_] }).join: "\n";
say "\nFirst $upto Pell primes:\n" ~ $pell.grep(&is-prime)[^$upto].join: "\n";
say "\nIndices of first $upto Pell primes:\n" ~ (^∞).grep({$pell[$_].is-prime})[^$upto];
say "\nFirst $upto Newman-Shank-Williams numbers:\n" ~ (^$upto).map({ $pell[2 × $_, 2 × $_+1].sum });
say "\nFirst $upto near isoceles right tringles:"; map -> \p { printf "(%d, %d, %d)\n", |($_, $_+1 given $pell[^(2 × p + 1)].sum), $pell[2 × p + 1] }, 1..$upto;</lang>
- Output:
First 20 Pell numbers: 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 80782 195025 470832 1136689 2744210 6625109 First 20 Pell-Lucas numbers: 2 2 6 14 34 82 198 478 1154 2786 6726 16238 39202 94642 228486 551614 1331714 3215042 7761798 18738638 First 20 rational approximations of √2 (1.4142135623730951): 1/1 - 1.0000000000000000 3/2 - 1.5000000000000000 7/5 - 1.4000000000000000 17/12 - 1.4166666666666667 41/29 - 1.4137931034482758 99/70 - 1.4142857142857144 239/169 - 1.4142011834319526 577/408 - 1.4142156862745099 1393/985 - 1.4142131979695431 3363/2378 - 1.4142136248948696 8119/5741 - 1.4142135516460548 19601/13860 - 1.4142135642135643 47321/33461 - 1.4142135620573204 114243/80782 - 1.4142135624272734 275807/195025 - 1.4142135623637995 665857/470832 - 1.4142135623746899 1607521/1136689 - 1.4142135623728214 3880899/2744210 - 1.4142135623731420 9369319/6625109 - 1.4142135623730870 22619537/15994428 - 1.4142135623730965 First 20 Pell primes: 2 5 29 5741 33461 44560482149 1746860020068409 68480406462161287469 13558774610046711780701 4125636888562548868221559797461449 4760981394323203445293052612223893281 161733217200188571081311986634082331709 2964793555272799671946653940160950323792169332712780937764687561 677413820257085084326543915514677342490435733542987756429585398537901 4556285254333448771505063529048046595645004014152457191808671945330235841 54971607658948646301386783144964782698772613513307493180078896702918825851648683235325858118170150873214978343601463118106546653220435805362395962991295556488036606954237309847762149971207793263738989 14030291214037674827921599320400561033992948898216351802670122530401263880575255235196727095109669287799074570417579539629351231775861429098849146880746524269269235328805333087546933690012894630670427794266440579064751300508834822795162874147983974059159392260220762973563561382652223360667198516093199367134903695783143116067743023134509886357032327271649 2434804314652199381956027075145741187716221548707931096877274520825143228915116227412484991366386864484767844200542482630246332092069382947111767723898168035847078557798454111405556629400142434835890123610082763986456199467423944182141028870863302603437534363208996458153115358483747994095302552907353919742211197822912892578751357668345638404394626711701120567186348490247426710813709165801137112237291901437566040249805155494297005186344325519103590369653438042689 346434895614929444828445967916634653215454504812454865104089892164276080684080254746939261017687341632569935171059945916359539268094914543114024020158787741692287531903178502306292484033576487391159597130834863729261484555671037916432206867189514675750227327687799973497042239286045783392065227614939379139866240959756584073664244580698830046194724340448293320938108876004367449471918175071251610962540447986139876845105399212429593945098472125140242905536711601925585608153109062121115635939797709 32074710952523740376423283403256578238321646122759160107427497117576305397686814013623874765833543023397971470911301264845142006214276865917420065183527313421909784286074786922242104480428021290764613639424408361555091057197776876849282654018358993099016644054242247557103410808928387071991436781136646322261169941417916607548507224950058710729258466238995253184617782314756913932650536663800753256087990078866003788647079369825102832504351225446531057648755795494571534144773842019836572551455718577614678081652481281009 Indices of first 20 Pell primes: 2 3 5 11 13 29 41 53 59 89 97 101 167 181 191 523 929 1217 1301 1361 First 20 Newman-Shank-Williams numbers: 1 7 41 239 1393 8119 47321 275807 1607521 9369319 54608393 318281039 1855077841 10812186007 63018038201 367296043199 2140758220993 12477253282759 72722761475561 423859315570607 First 20 near isoceles right tringles: (3, 4, 5) (20, 21, 29) (119, 120, 169) (696, 697, 985) (4059, 4060, 5741) (23660, 23661, 33461) (137903, 137904, 195025) (803760, 803761, 1136689) (4684659, 4684660, 6625109) (27304196, 27304197, 38613965) (159140519, 159140520, 225058681) (927538920, 927538921, 1311738121) (5406093003, 5406093004, 7645370045) (31509019100, 31509019101, 44560482149) (183648021599, 183648021600, 259717522849) (1070379110496, 1070379110497, 1513744654945) (6238626641379, 6238626641380, 8822750406821) (36361380737780, 36361380737781, 51422757785981) (211929657785303, 211929657785304, 299713796309065) (1235216565974040, 1235216565974041, 1746860020068409)
Wren
<lang ecmascript>import "./big" for BigInt, BigRat import "./math" for Int import "./fmt" for Fmt
var p = List.filled(40, 0) p[0] = 0 p[1] = 1 for (i in 2..39) p[i] = 2 * p[i-1] + p[i-2] System.print("The first 20 Pell numbers are:") System.print(p[0..19].join(" "))
var q = List.filled(40, 0) q[0] = 2 q[1] = 2 for (i in 2..39) q[i] = 2 * q[i-1] + q[i-2] System.print("\nThe first 20 Pell-Lucas numbers are:") System.print(q[0..19].join(" "))
System.print("\nThe first 20 rational approximations of √2 (1.4142135623730951) are:") for (i in 1..20) {
var r = BigRat.new(q[i]/2, p[i]) Fmt.print("$-17s ≈ $-18s", r, r.toDecimal(16, true, true))
}
System.print("\nThe first 15 Pell primes are:") var p0 = BigInt.zero var p1 = BigInt.one var indices = List.filled(15, 0) var count = 0 var index = 2 var p2 while (count < 15) {
p2 = p1 * BigInt.two + p0 if (Int.isPrime(index) && p2.isProbablePrime(10)) { System.print(p2) indices[count] = index count = count + 1 } index = index + 1 p0 = p1 p1 = p2
}
System.print("\nIndices of the first 15 Pell primes are:") System.print(indices.join(" "))
System.print("\nFirst 20 Newman-Shank_Williams numbers:") var nsw = List.filled(20, 0) for (n in 0..19) nsw[n] = p[2*n] + p[2*n+1] Fmt.print("$d", nsw)
System.print("\nFirst 20 near isosceles right triangles:") p0 = 0 p1 = 1 var sum = 1 var i = 2 while (i < 43) {
p2 = p1 * 2 + p0 if (i % 2 == 1) { Fmt.print("($d, $d, $d)", sum, sum + 1, p2) } sum = sum + p2 p0 = p1 p1 = p2 i = i + 1
}</lang>
- Output:
The first 20 Pell numbers are: 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 80782 195025 470832 1136689 2744210 6625109 The first 20 Pell-Lucas numbers are: 2 2 6 14 34 82 198 478 1154 2786 6726 16238 39202 94642 228486 551614 1331714 3215042 7761798 18738638 The first 20 rational approximations of √2 (1.4142135623730951) are: 1/1 ≈ 1.0000000000000000 3/2 ≈ 1.5000000000000000 7/5 ≈ 1.4000000000000000 17/12 ≈ 1.4166666666666667 41/29 ≈ 1.4137931034482759 99/70 ≈ 1.4142857142857143 239/169 ≈ 1.4142011834319527 577/408 ≈ 1.4142156862745098 1393/985 ≈ 1.4142131979695431 3363/2378 ≈ 1.4142136248948696 8119/5741 ≈ 1.4142135516460547 19601/13860 ≈ 1.4142135642135642 47321/33461 ≈ 1.4142135620573205 114243/80782 ≈ 1.4142135624272734 275807/195025 ≈ 1.4142135623637995 665857/470832 ≈ 1.4142135623746899 1607521/1136689 ≈ 1.4142135623728214 3880899/2744210 ≈ 1.4142135623731420 9369319/6625109 ≈ 1.4142135623730870 22619537/15994428 ≈ 1.4142135623730964 The first 15 Pell primes are: 2 5 29 5741 33461 44560482149 1746860020068409 68480406462161287469 13558774610046711780701 4125636888562548868221559797461449 4760981394323203445293052612223893281 161733217200188571081311986634082331709 2964793555272799671946653940160950323792169332712780937764687561 677413820257085084326543915514677342490435733542987756429585398537901 4556285254333448771505063529048046595645004014152457191808671945330235841 Indices of the first 15 Pell primes are: 2 3 5 11 13 29 41 53 59 89 97 101 167 181 191 First 20 Newman-Shank_Williams numbers: 1 7 41 239 1393 8119 47321 275807 1607521 9369319 54608393 318281039 1855077841 10812186007 63018038201 367296043199 2140758220993 12477253282759 72722761475561 423859315570607 First 20 near isosceles right triangles: (3, 4, 5) (20, 21, 29) (119, 120, 169) (696, 697, 985) (4059, 4060, 5741) (23660, 23661, 33461) (137903, 137904, 195025) (803760, 803761, 1136689) (4684659, 4684660, 6625109) (27304196, 27304197, 38613965) (159140519, 159140520, 225058681) (927538920, 927538921, 1311738121) (5406093003, 5406093004, 7645370045) (31509019100, 31509019101, 44560482149) (183648021599, 183648021600, 259717522849) (1070379110496, 1070379110497, 1513744654945) (6238626641379, 6238626641380, 8822750406821) (36361380737780, 36361380737781, 51422757785981) (211929657785303, 211929657785304, 299713796309065) (1235216565974040, 1235216565974041, 1746860020068409)