Practical numbers: Difference between revisions
m
→Using Srinivasan-Stewart-Sierpinsky characterization: 2 other benchmarks
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→Using Srinivasan-Stewart-Sierpinsky characterization: 2 other benchmarks) |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 67:
666 is a practical number.
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">
BEGIN # find some practical numbers - positive integers n where subsets of #
# their proper divisors can be summed to every positive integer < n #
# returns TRUE if n is practical, FALSE otherwise #
PROC is practical = ( INT n )BOOL:
IF n < 1 THEN FALSE
ELIF n = 1 THEN TRUE
ELIF ODD n THEN FALSE
ELSE
# get a list of the proper divisors of n #
[ 1 : 30 ]INT pd; # should be more than enough for n < 667 #
INT pd pos := LWB pd - 1;
# returns TRUE if a subset of pd can be summed to n, FALSE otherwise #
PROC can sum to = ( INT x )BOOL:
BEGIN
BOOL found sum := FALSE;
INT max v = ( 2 ^ pd pos ) - 1;
FOR i TO max v WHILE NOT found sum DO
INT sum := 0;
INT v := i;
INT bit := 0;
WHILE v > 0 DO
bit +:= 1;
IF ODD v THEN sum +:= pd[ bit ] FI;
v OVERAB 2
OD;
found sum := sum = x
OD;
found sum
END # can sum to # ;
pd[ pd pos +:= 1 ] := 1;
FOR i FROM 2 TO ENTIER sqrt( n ) DO
IF n MOD i = 0 THEN
pd[ pd pos +:= 1 ] := i;
INT j = n OVER i;
IF i /= j THEN pd[ pd pos +:= 1 ] := j FI
FI
OD;
# check that subsets of the divisors can be summed to every #
# integer less than n #
BOOL practical := TRUE;
FOR i TO n - 1 WHILE practical := can sum to( i ) DO SKIP OD;
practical
FI # is practical # ;
[ 1 : 333 ]BOOL practical;
FOR i FROM LWB practical TO UPB practical DO practical[ i ] := is practical( i ) OD;
INT p count := 0;
FOR i FROM LWB practical TO UPB practical DO IF practical[ i ] THEN p count +:= 1 FI OD;
print( ( "Found ", whole( p count, 0 ), " practical numbers up to ", whole( UPB practical, 0 ), newline ) );
INT count := 0;
FOR i FROM LWB practical TO UPB practical WHILE count < 10 DO
IF practical[ i ] THEN
count +:= 1;
print( ( " ", whole( i, 0 ) ) )
FI
OD;
print( ( " ..." ) );
count := 0;
FOR i FROM LWB practical TO UPB practical DO
IF practical[ i ] THEN
count +:= 1;
IF count > p count - 10 THEN print( ( " ", whole( i, 0 ) ) ) FI
FI
OD;
print( ( newline ) );
print( ( "666 is ", IF NOT is practical( 666 ) THEN "not " ELSE "" FI, "a practical number", newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
1 2 4 6 8 12 16 18 20 24 ... 288 294 300 304 306 308 312 320 324 330
666 is a practical number
</pre>
Line 79 ⟶ 159:
pract 666 ⍝ Is 666 practical?
1</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">allSums: function [n][
result: []
current: []
loop factors n 'd [
current: new result
loop current 's ->
'result ++ s+d
'result ++ d
unique 'result
]
return result
]
practical?: function [n]->
or? -> n=1 -> subset? @1..dec n allSums n
practicals: select 1..333 => practical?
print ["Found" size practicals "practical numbers between 1 and 333:"]
loop split.every: 10 practicals 'x ->
print map x 's -> pad to :string s 4
print ""
p666: practical? 666
print ["666" p666 ? -> "is" -> "is not" "a practical number"]</syntaxhighlight>
{{out}}
<pre>Found 77 practical numbers between 1 and 333:
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
666 is a practical number</pre>
=={{header|C#|CSharp}}==
Line 1,465 ⟶ 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}}==
Line 1,673 ⟶ 1,857:
=={{header|Wren}}==
{{libheader|Wren-math}}
<syntaxhighlight lang="
var powerset // recursive
Line 1,720 ⟶ 1,904:
666 is practical: true
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">int Divs(32), NumDivs;
proc GetDivs(N); \Fill array Divs with proper divisors of N
int N, I, Div, Quot;
[Divs(0):= 1; I:= 1; Div:= 2;
loop [Quot:= N/Div;
if Div > Quot then quit;
if rem(0) = 0 then
[Divs(I):= Div; I:= I+1;
if Div # Quot then
[Divs(I):= Quot; I:= I+1];
if I > 30 then
[Text(0, "beyond the limit of 30 divisors.^m^j"); exit];
];
Div:= Div+1;
];
NumDivs:= I;
];
func PowerSet(N); \Return 'true' if some combination of Divs sums to N
int N, I, J, Sum;
[for I:= 0 to 1<<NumDivs - 1 do \(beware of 1<<31 - 1 infinite loop)
[Sum:= 0;
for J:= 0 to NumDivs-1 do
[if I & 1<<J then \for all set bits...
[Sum:= Sum + Divs(J);
if Sum = N then return true;
];
];
];
return false;
];
func Practical(X); \Return 'true' if X is a practical number
int X, N;
[GetDivs(X);
for N:= 1 to X-1 do
if PowerSet(N) = false then return false;
return true;
];
int N, I;
[for N:= 1 to 333 do
if Practical(N) then
[IntOut(0, N); ChOut(0, ^ )];
CrLf(0);
N:= [666, 6666, 66666, 672, 720, 222222];
for I:= 0 to 6-1 do
[IntOut(0, N(I)); Text(0, " is ");
if not Practical(N(I)) then Text(0, "not ");
Text(0, "a practical number.^m^j");
];
]</syntaxhighlight>
{{out}}
<pre>
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
666 is a practical number.
6666 is a practical number.
66666 is not a practical number.
672 is a practical number.
720 is a practical number.
222222 is beyond the limit of 30 divisors.
</pre>
| |||