Rosetta Code

Practical numbers: Difference between revisions

Page Discussion

Practical numbers (view source)

Revision as of 06:34, 1 February 2024

11,511 bytes added ,  4 months ago
m
→‎Using Srinivasan-Stewart-Sierpinsky characterization: 2 other benchmarks
(add freebasic)
 
(9 intermediate revisions by 7 users not shown)
Line 18:
* Show if 666 is a Practical number
 
 
=={{header|11l}}==
{{trans|Nim}}
 
<syntaxhighlight lang="11l">F properDivisors(n)
V result = [1]
L(i) 2 .. Int(sqrt(n))
I n % i == 0
V j = n I/ i
result.append(i)
I i != j
result.append(j)
R result
 
F allSums(n)
V divs = properDivisors(n)
V currSet = Set[Int]()
V result = Set[Int]()
L(d) divs
currSet = copy(result)
L(sum) currSet
result.add(sum + d)
result.add(d)
R result
 
F isPractical(n)
R Set(Array(1 .< n)) <= allSums(n)
 
V count = 0
L(n) 1..333
I isPractical(n)
count++
print(‘#3’.format(n), end' I count % 11 == 0 {"\n"} E ‘ ’)
print(‘Found ’count‘ practical numbers between 1 and 333.’)
print()
print(‘666 is ’(I isPractical(666) {‘’} E ‘not ’)‘a practical number.’)</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
Found 77 practical numbers between 1 and 333.
 
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>
 
=={{header|APL}}==
{{works with|Dyalog APL}}
<langsyntaxhighlight APLlang="apl">pract ← ∧/⍳∊(+⌿⊢×[1](2/⍨≢)⊤(⍳2*≢))∘(⍸0=⍳|⊢)</langsyntaxhighlight>
{{out}}
<langsyntaxhighlight APLlang="apl"> ⍸pract¨⍳333 ⍝ Which numbers from 1 to 333 are practical?
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
pract 666 ⍝ Is 666 practical?
1</langsyntaxhighlight>
 
=={{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}}==
<langsyntaxhighlight lang="csharp">using System.Collections.Generic; using System.Linq; using static System.Console;
 
class Program {
Line 48 ⟶ 221:
Write("\nFound {0} practical numbers between 1 and {1} inclusive.\n", c, m);
do Write("\n{0,5} is a{1}practical number.",
m = m < 500 ? m << 1 : m * 10 + 6, ip(m) ? " " : "n im"); while (m < 1e4); } }</langsyntaxhighlight>
{{out}}
<pre> 1 2 4 6 8 12 16 18 20 24
Line 66 ⟶ 239:
=={{header|C++}}==
{{trans|Phix}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <numeric>
Line 141 ⟶ 314:
<< "a practical number.\n";
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 159 ⟶ 332:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">sub make_divisors( n as uinteger, div() as uinteger )
'produces a list of an integer's proper divisors
for i as uinteger = n/2 to 1 step -1
Line 204 ⟶ 377:
for n as uinteger = 2 to 666
if is_practical(n) then print n;" ";
next n:print</langsyntaxhighlight>
 
All practical numbers up to and including the stretch goal of DCLXVI.
Line 214 ⟶ 387:
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 270 ⟶ 443:
fmt.Println(" The final ten are", practical[len(practical)-10:])
fmt.Println("\n666 is practical:", isPractical(666))
}</langsyntaxhighlight>
 
{{out}}
Line 286 ⟶ 459:
Borrowed from the [[Proper divisors#J]] page:
 
<langsyntaxhighlight Jlang="j">factors=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__
properDivisors=: factors -. ]</langsyntaxhighlight>
 
Borrowed from the [[Power set#J]] page:
 
<langsyntaxhighlight Jlang="j">ps=: #~ 2 #:@i.@^ #</langsyntaxhighlight>
 
Implementation:
 
<langsyntaxhighlight Jlang="j">isPrac=: ('' -:&# i. -. 0,+/"1@(ps ::empty)@properDivisors)"0</langsyntaxhighlight>
 
Task examples:
 
<langsyntaxhighlight Jlang="j"> +/ isPrac 1+i.333 NB. count practical numbers
77
(#~ isPrac) 1+i.333 NB. list them
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 30...
isPrac 666 NB. test
1</langsyntaxhighlight>
 
=={{header|Java}}==
{{trans|Phix}}
<langsyntaxhighlight lang="java">import java.util.*;
 
public class PracticalNumbers {
Line 404 ⟶ 577:
return str.toString();
}
}</langsyntaxhighlight>
 
{{out}}
Line 428 ⟶ 601:
The version of `proper_divisors` at [[Proper_divisors#jq]] may be used and therefore its definition
is not repeated here.
<langsyntaxhighlight lang="jq"># A reminder to include the definition of `proper_divisors`
# include "proper_divisors" { search: "." };
 
Line 481 ⟶ 654:
task(333),
(666,6666,66666
| "\nIs \(.) practical? \(if isPractical then "Yes." else "No." end)" )</langsyntaxhighlight>
{{out}}
<pre>
Line 499 ⟶ 672:
=={{header|Julia}}==
{{trans|Python}}
<langsyntaxhighlight lang="julia">using Primes
 
""" proper divisors of n """
Line 535 ⟶ 708:
println("$n is ", ispractical(n) ? "" : "not ", "a practical number.")
end
</langsyntaxhighlight>{{out}}
<pre>
There are 77 practical numbers between 1 to 333 inclusive.
Line 547 ⟶ 720:
 
=={{header|Nim}}==
<langsyntaxhighlight Nimlang="nim">import intsets, math, sequtils, strutils
 
func properDivisors(n: int): seq[int] =
Line 576 ⟶ 749:
echo "Found ", count, " practical numbers between 1 and 333."
echo()
echo "666 is ", if 666.isPractical: "" else: "not ", "a practical number."</langsyntaxhighlight>
 
{{out}}
Line 597 ⟶ 770:
because the inequality above holds for each of its prime factors:
3 ≤ σ(2) + 1 = 4, 29 ≤ σ(2 × 3^2) + 1 = 40, and 823 ≤ σ(2 × 3^2 × 29) + 1 = 1171. </pre>
<langsyntaxhighlight lang="pascal">program practicalnumbers;
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
Line 787 ⟶ 960:
{$IFNDEF UNIX} readln; {$ENDIF}
end.
</syntaxhighlight>
</lang>
{{out}}
<pre> TIO.RUN.
Line 820 ⟶ 993:
==={{header|alternative}}===
Now without generating sum of allset.
<langsyntaxhighlight lang="pascal">program practicalnumbers2;
 
{$IFDEF FPC}
Line 952 ⟶ 1,125:
{$ENDIF}
end.
</syntaxhighlight>
</lang>
{{out}}
<pre> TIO.RUN
Line 979 ⟶ 1,152:
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 1,006 ⟶ 1,179:
say @pn . " matching numbers:\n" . (sprintf "@{['%4d' x @pn]}", @pn) =~ s/(.{40})/$1\n/gr;
say '';
printf "%6d is practical? %s\n", $_, is_practical($_) ? 'True' : 'False' for 666, 6666, 66666;</langsyntaxhighlight>
{{out}}
<pre>77 matching numbers:
Line 1,023 ⟶ 1,196:
=={{header|Phix}}==
{{trans|Python|(the composition of functions version)}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">sum_of_any_subset</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return true if any subset of f sums to n.</span>
Line 1,052 ⟶ 1,225:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">({</span><span style="color: #000000;">666</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6666</span><span style="color: #0000FF;">,</span><span style="color: #000000;">66666</span><span style="color: #0000FF;">,</span><span style="color: #000000;">672</span><span style="color: #0000FF;">,</span><span style="color: #000000;">720</span><span style="color: #0000FF;">},</span><span style="color: #000000;">stretch</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,068 ⟶ 1,241:
===Python: Straight forward implementation===
 
<langsyntaxhighlight lang="python">from itertools import chain, cycle, accumulate, combinations
from typing import List, Tuple
 
Line 1,123 ⟶ 1,296:
print(' ', str(p[:10])[1:-1], '...', str(p[-10:])[1:-1])
x = 666
print(f"\nSTRETCH GOAL: {x} is {'not ' if not is_practical(x) else ''}Practical.")</langsyntaxhighlight>
 
{{out}}
Line 1,141 ⟶ 1,314:
An extra check on the sum of all factors has a minor positive effect too.
 
<langsyntaxhighlight lang="python">def is_practical5(x: int) -> bool:
"""Practical number test with factor reverse sort and short-circuiting."""
 
Line 1,178 ⟶ 1,351:
print(f"\nSTRETCH GOAL: {x} is {'not ' if not is_practical(x) else ''}Practical.")
x = 5184
print(f"\nEXTRA GOAL: {x} is {'not ' if not is_practical(x) else ''}Practical.")</langsyntaxhighlight>
 
{{out}}
Line 1,199 ⟶ 1,372:
===Composition of pure functions===
 
<langsyntaxhighlight lang="python">'''Practical numbers'''
 
from itertools import accumulate, chain, groupby, product
Line 1,366 ⟶ 1,539:
# MAIN ---
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{Out}}
<pre>77 OEIS A005153 numbers in [1..333]
Line 1,383 ⟶ 1,556:
 
=={{header|Raku}}==
<syntaxhighlight lang="raku" perl6line>use Prime::Factor:ver<0.3.0+>;
 
sub is-practical ($n) {
Line 1,397 ⟶ 1,570:
given [ (1..333).hyper(:32batch).grep: { is-practical($_) } ];
 
printf "%5s is practical? %s\n", $_, .&is-practical for 666, 6666, 66666, 672, 720;</langsyntaxhighlight>
{{out}}
<pre>77 matching numbers:
Line 1,414 ⟶ 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}}==
{{trans|Phix}}
<langsyntaxhighlight lang="rust">fn sum_of_any_subset(n: isize, f: &[isize]) -> bool {
let len = f.len();
if len == 0 {
Line 1,520 ⟶ 1,755:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,536 ⟶ 1,771:
=={{header|Sidef}}==
Built-in:
<langsyntaxhighlight lang="ruby">say is_practical(2**128 + 1) #=> false
say is_practical(2**128 + 4) #=> true</langsyntaxhighlight>
 
Slow implementation (as the task requires):
<langsyntaxhighlight lang="ruby">func is_practical(n) {
 
var set = Set()
Line 1,561 ⟶ 1,796:
for n in ([666, 6666, 66666]) {
say "#{'%5s' % n } is practical? #{is_practical(n)}"
}</langsyntaxhighlight>
 
Efficient algorithm:
<langsyntaxhighlight lang="ruby">func is_practical(n) {
 
n.is_odd && return (n == 1)
Line 1,578 ⟶ 1,813:
 
return true
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,591 ⟶ 1,826:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports System.Collections.Generic, System.Linq, System.Console
 
Module Module1
Line 1,616 ⟶ 1,851:
Write(vbLf & "{0,5} is a{1}practical number.", m, If(ip(m), " ", "n im")) : Loop While m < 1e4
End Sub
End Module</langsyntaxhighlight>
{{out}}
Same as C#
Line 1,622 ⟶ 1,857:
=={{header|Wren}}==
{{libheader|Wren-math}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int, Nums
 
var powerset // recursive
Line 1,659 ⟶ 1,894:
System.print(" The first ten are %(practical[0..9])")
System.print(" The final ten are %(practical[-10..-1])")
System.print("\n666 is practical: %(isPractical.call(666))")</langsyntaxhighlight>
 
{{out}}
Line 1,669 ⟶ 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>
Aerobar
1,151

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/310381...354703"