Pell numbers: Difference between revisions
Content added Content deleted
(Created Nim solution.) |
(add RPL) |
||
Line 1,427: | Line 1,427: | ||
(211929657785303, 211929657785304, 299713796309065) |
(211929657785303, 211929657785304, 299713796309065) |
||
(1235216565974040, 1235216565974041, 1746860020068409)</pre> |
(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}}== |
=={{header|Scala}}== |