Practical numbers: Difference between revisions
m
→Using Srinivasan-Stewart-Sierpinsky characterization: 2 other benchmarks
(→{{header|ALGOL 68}}: The proper divisors are unique (apart from root(n)- so no need to check that when adding them...) |
m (→Using Srinivasan-Stewart-Sierpinsky characterization: 2 other benchmarks) |
||
| (2 intermediate revisions by the same user not shown) | |||
Line 1,587:
672 is practical? True
720 is practical? True</pre>
=={{header|RPL}}==
{{works with|HP|49/50}}
====Brute & slow force====
« 1 SF REVLIST
1 « '''IF''' 1 FS? '''THEN''' NOT '''IF''' DUP '''THEN''' 1 CF '''END END''' » DOLIST
REVLIST
» '<span style="color:blue">INCLIST</span>' STO <span style="color:grey">@ ( { bit..bit } → { bit..bit+1 } ) </span>
« '''CASE'''
DUP LN 2 LN / FP NOT '''THEN''' SIGN '''END''' <span style="color:grey">@ powers of two are practical</span>
DUP 2 MOD '''THEN''' NOT '''END''' <span style="color:grey">@ odd numbers are not practical</span>
DUP DIVIS 1 OVER SIZE 1 - SUB { } → n divs sums
« 2 CF 1
0 divs SIZE NDUPN →LIST INCLIST
'''DO''' <span style="color:blue">INCLIST</span>
DUP divs * ∑LIST
'''CASE'''
DUP n ≥ '''THEN''' DROP '''END'''
sums OVER POS '''THEN''' DROP '''END'''
'sums' STO+ SWAP 1 + SWAP
'''END'''
'''IF''' OVER n == '''THEN''' 2 SF '''END'''
'''UNTIL''' DUP 0 POS NOT 2 FS? OR '''END'''
DROP2 2 FC?
»
'''END'''
» '<span style="color:blue">PRACTICAL?</span>' STO <span style="color:grey">@ ( n → boolean ) </span>
====Using Srinivasan-Stewart-Sierpinsky characterization====
From [https://en.wikipedia.org/wiki/Practical_number#Characterization_of_practical_numbers the Wikipedia article]. It's very fast and needs only to store the prime decomposition of the tested number.
« '''CASE'''
DUP LN 2 LN / FP NOT '''THEN''' SIGN '''END''' <span style="color:grey">@ powers of two are practical</span>
DUP 2 MOD '''THEN''' NOT '''END''' <span style="color:grey">@ odd numbers are not practical</span>
2 SF FACTORS
2 OVER DUP SIZE GET ^
OVER SIZE 2 - 2 '''FOR''' j
OVER j 1 - GET
DUP2 SWAP DIVIS ∑LIST 1 +
'''IF''' > '''THEN''' 2 CF 2. 'j' STO '''END''' <span style="color:grey">@ 2. is needed to exit the loop</span>
PICK3 j GET ^ *
-2 '''STEP'''
DROP2 2 FS?
'''END'''
» '<span style="color:blue">PRACTICAL?</span>' STO <span style="color:grey">@ ( n → boolean ) </span>
« { }
1 333 '''FOR''' j
'''IF''' j <span style="color:blue">PRACTICAL?</span> '''THEN''' j + '''END'''
'''NEXT'''
666 <span style="color:blue">PRACTICAL?</span>
66666 <span style="color:blue">PRACTICAL?</span>
» '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
4: { 1 2 4 6 8 12 16 18 20 24 28 30 32 36 40 42 48 54 56 60 64 66 72 78 80 84 88 90 96 100 104 108 112 120 126 128 132 140 144 150 156 160 162 168 176 180 192 196 198 200 204 208 210 216 220 224 228 234 240 252 256 260 264 270 272 276 280 288 294 300 304 306 308 312 320 324 330 }
3: 77
2: 1
1: 0
</pre>
Non-practicality of 66666 is established in 0.57 seconds on an HP-50 handheld calculator; testing 222222 or 9876543210 needs 1.5 seconds. Because of the algorithm's efficiency, even antique calculators from the 1970s could implement it, with an acceptable execution time.
=={{header|Rust}}==
| |||