Pell numbers: Difference between revisions
add RPL
(Created Nim solution.) |
(add RPL) |
||
Line 1,427:
(211929657785303, 211929657785304, 299713796309065)
(1235216565974040, 1235216565974041, 1746860020068409)</pre>
=={{header|RPL}}==
Let's start first with a universal Pell sequence generator, which takes a smaller sequence as input:
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ → n
≪ '''IF''' DUP SIZE n < '''THEN'''
LIST→ n SWAP -
1 SWAP '''START''' DUP2 DUP + + '''NEXT'''
n →LIST '''END'''
≫ ≫ ''''PELLS'''' STO
|
'''PELLS''' ''( { P(0)..P(m) } n -- { P(0)..P(n-1) } )''
if m < n
put P(0)..P(m) in the stack
loop n-m times: P(j+1) = 2*P(j) + P(j-1)
pop stack to a list
return new list
|}
We can then generate Pell and Pell-Lucas numbers with the same function:
{ 0 1 } 25 '''PELLS'''
{ 2 2 } 25 '''PELLS'''
{{out}}
<pre>
2: { 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 80782 195025 470832 1136689 2744210 6625109 15994428 38613965 93222358 225058681 543339720 }
1: { 2 2 6 14 34 82 198 478 1154 2786 6726 16238 39202 94642 228486 551614 1331714 3215042 7761798 18738638 45239074 109216786 263672646 636562078 1536796802 }
</pre>
Generating a sequence of rational approximations needs some code for appropriate formatting:
≪ { 0 1 } 16 '''PELLS''' → p
≪ { } 2 15 '''FOR''' j
p j GET "'" OVER p j 1 - GET + →STR + "/" + SWAP →STR + STR→ DUP →NUM ROT ROT + SWAP + '''NEXT'''
≫ ≫ ''''TASK3'''' STO
{{out}}
<pre>
{ '1/1' 1 '3/2' 1.5 '7/5' 1.4 '17/12' 1.41666666667 '41/29' 1.41379310345 '99/70' 1.41428571429 '239/169' 1.41420118343 '577/408' 1.41421568627 '1393/985' 1.41421319797 '3363/2378' 1.41421362489 '8119/5741' 1.41421355165 '19601/13860' 1.41421356421 '47321/33461' 1.41421356206 '114243/80782' 1.41421356243 }
</pre>
To look for prime Pell numbers, we need a fast Pell number generator and also a prime number checker, available [[Primality by trial division#RPL|here]]:
≪ '''DO'''
1 + ROT ROT DUP DUP + ROT + ROT
'''UNTIL''' 3 PICK '''BPRIM? END'''
≫ ≫ ''''PRPL'''' STO
≪ n { } → n primpell
≪ # 0d # 1d 1 1 n '''START '''
'''PRPL''' 3 PICK B→R OVER 1 - R→C primpell SWAP + 'primpell' STO '''NEXT'''
3 DROPN primpell
≫ ≫ ''''TASK4'''' STO
<code>'''TASK4'''</code> returns a list of complex numbers, the real part being the prime number and the imaginary part being the indice.
{{out}}
<pre>
1: { (2,2) (5,3) (29,5) (5741,11) (33461,13) (44560482149,29) }
</pre>
Unfortunately, the emulator's watchdog timer has refused to let us look beyond P<sub>29</sub>.
Generating the NSW sequence is again light work:
≪ → n
≪ { 0 1 } 2 n * 1 + '''PELLS''' { }
0 n 1 - '''FOR''' j
OVER j DUP + 1 + GET LAST 1 + GET + + '''NEXT'''
SWAP DROP
≫ ≫ ''''NSW'''' STO
15 '''NSW'''
{{out}}
<pre>
1: { 1 7 41 239 1393 8119 47321 275807 1607521 9369319 54608393 318281039 1855077841 10812186007 63018038201 }
</pre>
For dessert, the Pythagorean triplets can be found with:
≪ → n
≪ { 0 1 } 2 n * 2 + '''PELLS''' { }
1 n '''FOR''' j
OVER 2 j * 2 + GET LASTARG 1 - 1 SWAP SUB ∑LIST DUP 1 +
ROT 3 →LIST 1 →LIST + '''NEXT'''
SWAP DROP
≫ ≫ ''''PYTH3'''' STO
15 '''PYTH3'''
This program runs on HP-48G or newer models only, but it can be adapted for older ones by creating a homemade version of <code>∑LIST</code>, which sums the items of a list, and replacing <code>LASTARG</code> with <code>LAST</code>.
{{out}}
<pre>
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 } { 159140519 159140520 225058681 } { 927538920 927538921 1311738121 } { 5406093003 5406093004 7645370045 } { 31509019100 31509019101 44560482149 } { 183648021599 183648021600 259717522849 } }
</pre>
=={{header|Scala}}==
| |||