Practical numbers: Difference between revisions
m
→Using Srinivasan-Stewart-Sierpinsky characterization: 2 other benchmarks
m (→Using Srinivasan-Stewart-Sierpinsky characterization: 2 other benchmarks) |
|||
| (36 intermediate revisions by 18 users not shown) | |||
Line 17:
;Stretch Goal
* 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}}
<syntaxhighlight lang="apl">pract ← ∧/⍳∊(+⌿⊢×[1](2/⍨≢)⊤(⍳2*≢))∘(⍸0=⍳|⊢)</syntaxhighlight>
{{out}}
<syntaxhighlight lang="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</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}}==
<
class Program {
Line 37 ⟶ 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); } }</
{{out}}
<pre> 1 2 4 6 8 12 16 18 20 24
Line 52 ⟶ 236:
6666 is a practical number.
66666 is an impractical number.</pre>
=={{header|C++}}==
{{trans|Phix}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <numeric>
#include <sstream>
#include <vector>
// Returns true if any subset of [begin, end) sums to n.
template <typename iterator>
bool sum_of_any_subset(int n, iterator begin, iterator end) {
if (begin == end)
return false;
if (std::find(begin, end, n) != end)
return true;
int total = std::accumulate(begin, end, 0);
if (n == total)
return true;
if (n > total)
return false;
--end;
int d = n - *end;
return (d > 0 && sum_of_any_subset(d, begin, end)) ||
sum_of_any_subset(n, begin, end);
}
// Returns the proper divisors of n.
std::vector<int> factors(int n) {
std::vector<int> f{1};
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
f.push_back(i);
if (i * i != n)
f.push_back(n / i);
}
}
std::sort(f.begin(), f.end());
return f;
}
bool is_practical(int n) {
std::vector<int> f = factors(n);
for (int i = 1; i < n; ++i) {
if (!sum_of_any_subset(i, f.begin(), f.end()))
return false;
}
return true;
}
std::string shorten(const std::vector<int>& v, size_t n) {
std::ostringstream out;
size_t size = v.size(), i = 0;
if (n > 0 && size > 0)
out << v[i++];
for (; i < n && i < size; ++i)
out << ", " << v[i];
if (size > i + n) {
out << ", ...";
i = size - n;
}
for (; i < size; ++i)
out << ", " << v[i];
return out.str();
}
int main() {
std::vector<int> practical;
for (int n = 1; n <= 333; ++n) {
if (is_practical(n))
practical.push_back(n);
}
std::cout << "Found " << practical.size() << " practical numbers:\n"
<< shorten(practical, 10) << '\n';
for (int n : {666, 6666, 66666, 672, 720, 222222})
std::cout << n << " is " << (is_practical(n) ? "" : "not ")
<< "a practical number.\n";
return 0;
}</syntaxhighlight>
{{out}}
<pre>
Found 77 practical numbers:
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.
6666 is a practical number.
66666 is not a practical number.
672 is a practical number.
720 is a practical number.
222222 is a practical number.
</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Practical_numbers#Pascal Pascal].
=={{header|FreeBASIC}}==
<syntaxhighlight 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
if n mod i = 0 then
redim preserve div(1 to 1 + ubound(div))
div(ubound(div)) = i
end if
next i
end sub
function sum_divisors( n as uinteger, div() as uinteger ) as uinteger
'takes a list of divisors and an integer which, when interpreted
'as binary, selects which terms to sum
dim as uinteger sum = 0, term = 1
while n
if n mod 2 = 1 then sum += div(term)
term += 1
n\=2
wend
return sum
end function
function is_practical( n as uinteger ) as boolean
'determines if an integer is practical
if n = 1 then return true
if n mod 2 = 1 then return false 'there can be no odd practicals other than 1
if n < 5 then return true '2 and 4 are practical, but small enough to be handled specially
dim as uinteger hits(1 to n-1), nt, i, sd
redim as uinteger div(0 to 0)
make_divisors( n, div() )
nt = ubound(div)
for i = 1 to 2^nt-1
sd = sum_divisors(i, div())
if sd<n then hits(sd)+=1
next i
for i = 1 to n-1
if hits(i) = 0 then return false
next i
return true
end function
print 1;" "; 'treat 1 as a special case
for n as uinteger = 2 to 666
if is_practical(n) then print n;" ";
next n:print</syntaxhighlight>
All practical numbers up to and including the stretch goal of DCLXVI.
{{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 336 340 342 348 352 360 364 368 378 380 384 390 392 396 400 408 414 416 420 432 440 448 450 456 460 462 464 468 476 480 486 496 500 504 510 512 520 522 528 532 540 544 546 552 558 560 570 576 580 588 594 600 608 612 616 620 624 630 640 644 648 660 666</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<syntaxhighlight lang="go">package main
import (
"fmt"
"rcu"
)
func powerset(set []int) [][]int {
if len(set) == 0 {
return [][]int{{}}
}
head := set[0]
tail := set[1:]
p1 := powerset(tail)
var p2 [][]int
for _, s := range powerset(tail) {
h := []int{head}
h = append(h, s...)
p2 = append(p2, h)
}
return append(p1, p2...)
}
func isPractical(n int) bool {
if n == 1 {
return true
}
divs := rcu.ProperDivisors(n)
subsets := powerset(divs)
found := make([]bool, n) // all false by default
count := 0
for _, subset := range subsets {
sum := rcu.SumInts(subset)
if sum > 0 && sum < n && !found[sum] {
found[sum] = true
count++
if count == n-1 {
return true
}
}
}
return false
}
func main() {
fmt.Println("In the range 1..333, there are:")
var practical []int
for i := 1; i <= 333; i++ {
if isPractical(i) {
practical = append(practical, i)
}
}
fmt.Println(" ", len(practical), "practical numbers")
fmt.Println(" The first ten are", practical[0:10])
fmt.Println(" The final ten are", practical[len(practical)-10:])
fmt.Println("\n666 is practical:", isPractical(666))
}</syntaxhighlight>
{{out}}
<pre>
In the range 1..333, there are:
77 practical numbers
The first ten are [1 2 4 6 8 12 16 18 20 24]
The final ten are [288 294 300 304 306 308 312 320 324 330]
666 is practical: true
</pre>
=={{header|J}}==
Line 57 ⟶ 459:
Borrowed from the [[Proper divisors#J]] page:
<
properDivisors=: factors -. ]</
Borrowed from the [[Power set#J]] page:
<
Implementation:
<
Task examples:
<
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</
=={{header|Java}}==
{{trans|Phix}}
<syntaxhighlight lang="java">import java.util.*;
public class PracticalNumbers {
public static void main(String[] args) {
final int from = 1;
final int to = 333;
List<Integer> practical = new ArrayList<>();
for (int i = from; i <= to; ++i) {
if (isPractical(i))
practical.add(i);
}
System.out.printf("Found %d practical numbers between %d and %d:\n%s\n",
practical.size(), from, to, shorten(practical, 10));
printPractical(666);
printPractical(6666);
printPractical(66666);
printPractical(672);
printPractical(720);
printPractical(222222);
}
private static void printPractical(int n) {
if (isPractical(n))
System.out.printf("%d is a practical number.\n", n);
else
System.out.printf("%d is not a practical number.\n", n);
}
private static boolean isPractical(int n) {
int[] divisors = properDivisors(n);
for (int i = 1; i < n; ++i) {
if (!sumOfAnySubset(i, divisors, divisors.length))
return false;
}
return true;
}
private static boolean sumOfAnySubset(int n, int[] f, int len) {
if (len == 0)
return false;
int total = 0;
for (int i = 0; i < len; ++i) {
if (n == f[i])
return true;
total += f[i];
}
if (n == total)
return true;
if (n > total)
return false;
--len;
int d = n - f[len];
return (d > 0 && sumOfAnySubset(d, f, len)) || sumOfAnySubset(n, f, len);
}
private static int[] properDivisors(int n) {
List<Integer> divisors = new ArrayList<>();
divisors.add(1);
for (int i = 2;; ++i) {
int i2 = i * i;
if (i2 > n)
break;
if (n % i == 0) {
divisors.add(i);
if (i2 != n)
divisors.add(n / i);
}
}
int[] result = new int[divisors.size()];
for (int i = 0; i < result.length; ++i)
result[i] = divisors.get(i);
Arrays.sort(result);
return result;
}
private static String shorten(List<Integer> list, int n) {
StringBuilder str = new StringBuilder();
int len = list.size(), i = 0;
if (n > 0 && len > 0)
str.append(list.get(i++));
for (; i < n && i < len; ++i) {
str.append(", ");
str.append(list.get(i));
}
if (len > i + n) {
if (n > 0)
str.append(", ...");
i = len - n;
}
for (; i < len; ++i) {
str.append(", ");
str.append(list.get(i));
}
return str.toString();
}
}</syntaxhighlight>
{{out}}
<pre>
Found 77 practical numbers between 1 and 333:
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.
6666 is a practical number.
66666 is not a practical number.
672 is a practical number.
720 is a practical number.
222222 is a practical number.
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
This implementation does not create an in-memory representation of the powerset; this
saves some time and of course potentially a great deal of memory.
The version of `proper_divisors` at [[Proper_divisors#jq]] may be used and therefore its definition
is not repeated here.
<syntaxhighlight lang="jq"># A reminder to include the definition of `proper_divisors`
# include "proper_divisors" { search: "." };
# Input: an array, each of whose elements is treated as distinct.
# Output: a stream of arrays.
# If the items in the input array are distinct, then the items in the
# stream represent the items in the powerset of the input array. If
# the items in the input array are sorted, then the items in each of
# the output arrays will also be sorted. The lengths of the output
# arrays are non-decreasing.
def powersetStream:
if length == 0 then []
else .[0] as $first
| (.[1:] | powersetStream)
| ., ([$first] + . )
end;
def isPractical:
. as $n
| if . == 1 then true
elif . % 2 == 1 then false
else [proper_divisors] as $divs
| first(
foreach ($divs|powersetStream) as $subset (
{found: [],
count: 0 };
($subset|add) as $sum
| if $sum > 0 and $sum < $n and (.found[$sum] | not)
then .found[$sum] = true
| .count += 1
| if (.count == $n - 1) then .emit = true
else .
end
else .
end;
select(.emit).emit) )
// false
end;
# Input: the upper bound of range(1,_) to consider (e.g. infinite)
# Output: a stream of the practical numbers, in order
def practical:
range(1;.)
| select(isPractical);
def task($n):
($n + 1 | [practical]) as $p
| ("In the range 1 .. \($n) inclusive, there are \($p|length) practical numbers.",
"The first ten are:", $p[0:10],
"The last ten are:", $p[-10:] );
task(333),
(666,6666,66666
| "\nIs \(.) practical? \(if isPractical then "Yes." else "No." end)" )</syntaxhighlight>
{{out}}
<pre>
In the range 1 .. 333 inclusive, there are 77 practical numbers.
The first ten are:
[1,2,4,6,8,12,16,18,20,24]
The last ten are:
[288,294,300,304,306,308,312,320,324,330]
Is 666 practical? Yes.
Is 6666 practical? Yes.
Is 66666 practical? No.
</pre>
=={{header|Julia}}==
{{trans|Python}}
<
""" proper divisors of n """
Line 115 ⟶ 708:
println("$n is ", ispractical(n) ? "" : "not ", "a practical number.")
end
</
<pre>
There are 77 practical numbers between 1 to 333 inclusive.
Line 126 ⟶ 719:
</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import intsets, math, sequtils, strutils
func properDivisors(n: int): seq[int] =
result = @[1]
for i in 2..sqrt(n.toFloat).int:
if n mod i == 0:
let j = n div i
result.add i
if i != j: result.add j
func allSums(n: Positive): IntSet =
let divs = n.properDivisors()
var currSet: IntSet
for d in divs:
currSet.assign(result) # Make a copy of the set.
for sum in currSet:
result.incl sum + d # Add a new sum to the set.
result.incl d # Add the single value.
func isPractical(n: Positive): bool =
toSeq(1..<n).toIntSet <= allSums(n)
var count = 0
for n in 1..333:
if n.isPractical:
inc count
stdout.write ($n).align(3), if count mod 11 == 0: '\n' else: ' '
echo "Found ", count, " practical numbers between 1 and 333."
echo()
echo "666 is ", if 666.isPractical: "" else: "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|Pascal}}==
simple brute force.Marking sum of divs by shifting the former sum by the the next divisor.<BR>
SumAllSetsForPractical tries to break as soon as possible.Should try to check versus [[wp:Practical number|https://en.wikipedia.org/wiki/Practical_number#Characterization_of_practical_numbers]]<BR>
<pre>
...σ denotes the sum of the divisors of x. For example, 2 × 3^2 × 29 × 823 = 429606 is practical,
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>
<syntaxhighlight lang="pascal">program practicalnumbers;
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils
{$IFNDEF FPC}
,Windows
{$ENDIF}
;
const
LOW_DIVS = 0;
HIGH_DIVS = 2048 - 1;
type
tdivs = record
DivsVal: array[LOW_DIVS..HIGH_DIVS] of Uint32;
DivsMaxIdx, DivsNum, DivsSumProp: NativeUInt;
end;
var
Divs: tDivs;
HasSum: array of byte;
procedure GetDivisors(var Divs: tdivs; n: Uint32);
//calc all divisors,keep sorted
var
i, quot, ug, og: UInt32;
sum: UInt64;
begin
with Divs do
begin
DivsNum := n;
sum := 0;
ug := 0;
og := HIGH_DIVS;
i := 1;
while i * i < n do
begin
quot := n div i;
if n - quot * i = 0 then
begin
DivsVal[og] := quot;
Divs.DivsVal[ug] := i;
inc(sum, quot + i);
dec(og);
inc(ug);
end;
inc(i);
end;
if i * i = n then
begin
DivsVal[og] := i;
inc(sum, i);
dec(og);
end;
//move higher divisors down
while og < high_DIVS do
begin
inc(og);
DivsVal[ug] := DivsVal[og];
inc(ug);
end;
DivsMaxIdx := ug - 2;
DivsSumProp := sum - n;
end; //with
end;
function SumAllSetsForPractical(Limit: Uint32): boolean;
//mark sum and than shift by next divisor == add
//for practical numbers every sum must be marked
var
hs0, hs1: pByte;
idx, j, loLimit, maxlimit, delta: NativeUint;
begin
Limit := trunc(Limit * (Limit / Divs.DivsSumProp));
loLimit := 0;
maxlimit := 0;
hs0 := @HasSum[0];
hs0[0] := 1; //empty set
for idx := 0 to Divs.DivsMaxIdx do
begin
delta := Divs.DivsVal[idx];
hs1 := @hs0[delta];
for j := maxlimit downto 0 do
hs1[j] := hs1[j] or hs0[j];
maxlimit := maxlimit + delta;
while hs0[loLimit] <> 0 do
inc(loLimit);
//IF there is a 0 < delta, it will never be set
//IF there are more than the Limit set,
//it will be copied by the following Delta's
if (loLimit < delta) or (loLimit > Limit) then
Break;
end;
result := (loLimit > Limit);
end;
function isPractical(n: Uint32): boolean;
var
i: NativeInt;
sum: NativeUInt;
begin
if n = 1 then
EXIT(True);
if ODD(n) then
EXIT(false);
if (n > 2) and not ((n mod 4 = 0) or (n mod 6 = 0)) then
EXIT(false);
GetDivisors(Divs, n);
i := n - 1;
sum := Divs.DivsSumProp;
if sum < i then
result := false
else
begin
if length(HasSum) > sum + 1 + 1 then
FillChar(HasSum[0], sum + 1, #0)
else
begin
setlength(HasSum, 0);
setlength(HasSum, sum + 8 + 1);
end;
result := SumAllSetsForPractical(i);
end;
end;
procedure OutIsPractical(n: nativeInt);
begin
if isPractical(n) then
writeln(n, ' is practical')
else
writeln(n, ' is not practical');
end;
const
ColCnt = 10;
MAX = 333;
var
T0: Int64;
n, col, count: NativeInt;
begin
col := ColCnt;
count := 0;
for n := 1 to MAX do
if isPractical(n) then
begin
write(n: 5);
inc(count);
dec(col);
if col = 0 then
begin
writeln;
col := ColCnt;
end;
end;
writeln;
writeln('There are ', count, ' pratical numbers from 1 to ', MAX);
writeln;
T0 := GetTickCount64;
OutIsPractical(666);
OutIsPractical(6666);
OutIsPractical(66666);
OutIsPractical(954432);
OutIsPractical(720);
OutIsPractical(5384);
OutIsPractical(1441440);
writeln(Divs.DivsNum, ' has ', Divs.DivsMaxIdx + 1, ' proper divisors');
writeln((GetTickCount64 - T0) / 1000: 10: 3, ' s');
T0 := GetTickCount64;
OutIsPractical(99998640);
writeln(Divs.DivsNum, ' has ', Divs.DivsMaxIdx + 1, ' proper divisors ');
writeln((GetTickCount64 - T0) / 1000: 10: 3, ' s');
T0 := GetTickCount64;
OutIsPractical(99998640);
writeln(Divs.DivsNum, ' has ', Divs.DivsMaxIdx + 1, ' proper divisors ');
writeln((GetTickCount64 - T0) / 1000: 10: 3, ' s');
setlength(HasSum, 0);
{$IFNDEF UNIX} readln; {$ENDIF}
end.
</syntaxhighlight>
{{out}}
<pre> TIO.RUN.
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
There are 77 pratical numbers from 1 to 333
666 is practical
6666 is practical
66666 is not practical
954432 is not practical
720 is practical
5384 is not practical
1441440 is practical
1441440 has 287 proper divisors
0.017 s
99998640 is not practical
99998640 has 119 proper divisors
0.200 s // with reserving memory
99998640 is not practical
99998640 has 119 proper divisors
0.081 s // already reserved memory
Real time: 0.506 s CPU share: 87.94 %</pre>
==={{header|alternative}}===
Now without generating sum of allset.
<syntaxhighlight lang="pascal">program practicalnumbers2;
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
SysUtils;
type
tdivs = record
DivsVal: array[0..1024 - 1] of Uint32;
end;
var
Divs: tDivs;
function CheckIsPractical(var Divs: tdivs; n: Uint32): boolean;
//calc all divisors,calc sum of divisors
var
sum: UInt64;
i :NativeInt;
quot,ug,sq,de: UInt32;
begin
with Divs do
begin
sum := 1;
ug := Low(tdivs.DivsVal);
i := 2;
sq := 4;
de := 5;
while sq < n do
begin
quot := n div i;
if n - quot * i = 0 then
begin
if sum + 1 < i then
EXIT(false);
Inc(sum, i);
DivsVal[ug] := quot;
Inc(ug);
end;
Inc(i);
sq += de;
de := de+2;
end;
if sq = n then
begin
if sum + 1 < i then
EXIT(false);
DivsVal[ug] := i;
Inc(sum, i);
Inc(ug);
end;
//check higher
while ug > 0 do
begin
Dec(ug);
i := DivsVal[ug];
if sum + 1 < i then
EXIT(false);
Inc(sum, i);
if sum >= n - 1 then
break;
end;
end;//with
result := true;
end;
function isPractical(n: Uint32): boolean;
begin
if n in [1,2] then
EXIT(True);
if ODD(n) then
EXIT(False);
Result := CheckIsPractical(Divs, n);
end;
procedure OutIsPractical(n: nativeInt);
begin
if isPractical(n) then
writeln(n, ' is practical')
else
writeln(n, ' is not practical');
end;
const
ColCnt = 10;
MAX = 333;
var
T0 : int64;
n, col, Count: NativeInt;
begin
col := ColCnt;
Count := 0;
for n := 1 to MAX do
if isPractical(n) then
begin
Write(n: 5);
Inc(Count);
Dec(col);
if col = 0 then
begin
writeln;
col := ColCnt;
end;
end;
writeln;
writeln('There are ', Count, ' pratical numbers from 1 to ', MAX);
writeln;
OutIsPractical(666);
OutIsPractical(6666);
OutIsPractical(66666);
OutIsPractical(954432);
OutIsPractical(720);
OutIsPractical(5184);
OutIsPractical(1441440);
OutIsPractical(99998640);
T0 := GetTickCOunt64;
count := 0;
For n := 1 to 1000*1000 do
inc(count,Ord(isPractical(n)));
writeln('Count of practical numbers til 1,000,000 ',count,(GetTickCount64-t0)/1000:8:4,' s');
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end.
</syntaxhighlight>
{{out}}
<pre> TIO.RUN
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
There are 77 pratical numbers from 1 to 333
666 is practical
6666 is practical
66666 is not practical
954432 is not practical
720 is practical
5184 is practical
1441440 is practical
99998640 is not practical
Count of practical numbers til 1,000,000 97385 2.1380 s
Real time: 2.277 s CPU share: 99.55 %</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
use enum <False True>;
use ntheory <divisors vecextract>;
use List::AllUtils <sum uniq firstidx>;
sub proper_divisors {
return 1 if 0 == (my $n = shift);
my @d = divisors($n);
pop @d;
@d
}
sub powerset_sums { uniq map { sum vecextract(\@_,$_) } 1..2**@_-1 }
sub is_practical {
my($n) = @_;
return True if $n == 1;
return False if 0 != $n % 2;
($n-2 == firstidx { $_ == $n-1 } powerset_sums(proper_divisors($n)) ) ? True : False;
}
my @pn;
is_practical($_) and push @pn, $_ for 1..333;
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;</syntaxhighlight>
{{out}}
<pre>77 matching numbers:
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 practical? True
6666 is practical? True
66666 is practical? False</pre>
=={{header|Phix}}==
{{trans|Python|(the composition of functions version)}}
<!--<
<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 157 ⟶ 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>
<!--</
{{out}}
<pre>
Line 173 ⟶ 1,241:
===Python: Straight forward implementation===
<
from typing import List, Tuple
Line 228 ⟶ 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.")</
{{out}}
Line 243 ⟶ 1,311:
the sets. 720, another Practical number needs just 0.01% of its half a billion sets to prove it is Practical.
The inner loop is sensitive to the order of factors passed to the powerset generator and
An extra check on the sum of all factors has a minor positive effect too.
<syntaxhighlight lang="python">def is_practical5(x: int) -> bool:
"""Practical number test with factor reverse sort and short-circuiting."""
Line 258 ⟶ 1,326:
f = sorted(factors5(x), reverse=True)
if sum(f) < x - 1:
return False # Never get x-1
ps = powerset(f)
Line 281 ⟶ 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.")</
{{out}}
Line 302 ⟶ 1,372:
===Composition of pure functions===
<
from itertools import accumulate, chain, groupby, product
Line 469 ⟶ 1,539:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>77 OEIS A005153 numbers in [1..333]
Line 486 ⟶ 1,556:
=={{header|Raku}}==
<syntaxhighlight lang="raku"
sub is-practical ($n) {
Line 500 ⟶ 1,570:
given [ (1..333).hyper(:32batch).grep: { is-practical($_) } ];
printf "%5s is practical? %s\n", $_, .&is-practical for 666, 6666, 66666, 672, 720;</
{{out}}
<pre>77 matching numbers:
Line 517 ⟶ 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}}
<syntaxhighlight lang="rust">fn sum_of_any_subset(n: isize, f: &[isize]) -> bool {
let len = f.len();
if len == 0 {
return false;
}
if f.contains(&n) {
return true;
}
let mut total = 0;
for i in 0..len {
total += f[i];
}
if n == total {
return true;
}
if n > total {
return false;
}
let d = n - f[len - 1];
let g = &f[0..len - 1];
(d > 0 && sum_of_any_subset(d, g)) || sum_of_any_subset(n, g)
}
fn proper_divisors(n: isize) -> Vec<isize> {
let mut f = vec![1];
let mut i = 2;
loop {
let i2 = i * i;
if i2 > n {
break;
}
if n % i == 0 {
f.push(i);
if i2 != n {
f.push(n / i);
}
}
i += 1;
}
f.sort();
f
}
fn is_practical(n: isize) -> bool {
let f = proper_divisors(n);
for i in 1..n {
if !sum_of_any_subset(i, &f) {
return false;
}
}
true
}
fn shorten(v: &[isize], n: usize) -> String {
let mut str = String::new();
let len = v.len();
let mut i = 0;
if n > 0 && len > 0 {
str.push_str(&v[i].to_string());
i += 1;
}
while i < n && i < len {
str.push_str(", ");
str.push_str(&v[i].to_string());
i += 1;
}
if len > i + n {
if n > 0 {
str.push_str(", ...");
}
i = len - n;
}
while i < len {
str.push_str(", ");
str.push_str(&v[i].to_string());
i += 1;
}
str
}
fn main() {
let from = 1;
let to = 333;
let mut practical = Vec::new();
for n in from..=to {
if is_practical(n) {
practical.push(n);
}
}
println!(
"Found {} practical numbers between {} and {}:\n{}",
practical.len(),
from,
to,
shorten(&practical, 10)
);
for n in &[666, 6666, 66666, 672, 720, 222222] {
if is_practical(*n) {
println!("{} is a practical number.", n);
} else {
println!("{} is not practical number.", n);
}
}
}</syntaxhighlight>
{{out}}
<pre>
Found 77 practical numbers between 1 and 333:
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.
6666 is a practical number.
66666 is not practical number.
672 is a practical number.
720 is a practical number.
222222 is a practical number.
</pre>
=={{header|Sidef}}==
Built-in:
<syntaxhighlight lang="ruby">say is_practical(2**128 + 1) #=> false
say is_practical(2**128 + 4) #=> true</syntaxhighlight>
Slow implementation (as the task requires):
<syntaxhighlight lang="ruby">func is_practical(n) {
var set = Set()
n.divisors.grep { _ < n }.subsets {|*a|
set << a.sum
}
1..n-1 -> all { set.has(_) }
}
var from = 1
var upto = 333
var list = (from..upto).grep { is_practical(_) }
say "There are #{list.len} practical numbers in the range #{from}..#{upto}."
say "#{list.first(10).join(', ')} ... #{list.last(10).join(', ')}\n"
for n in ([666, 6666, 66666]) {
say "#{'%5s' % n } is practical? #{is_practical(n)}"
}</syntaxhighlight>
Efficient algorithm:
<syntaxhighlight lang="ruby">func is_practical(n) {
n.is_odd && return (n == 1)
n.is_pos || return false
var p = 1
var f = n.factor_exp
f.each_cons(2, {|a,b|
p *= sigma(a.head**a.tail)
b.head > (1 + p) && return false
})
return true
}</syntaxhighlight>
{{out}}
<pre>
There are 77 practical numbers in the range 1..333.
1, 2, 4, 6, 8, 12, 16, 18, 20, 24 ... 288, 294, 300, 304, 306, 308, 312, 320, 324, 330
666 is practical? true
6666 is practical? true
66666 is practical? false
</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 545 ⟶ 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</
{{out}}
Same as C#
Line 551 ⟶ 1,857:
=={{header|Wren}}==
{{libheader|Wren-math}}
<
var powerset // recursive
Line 579 ⟶ 1,885:
System.print("In the range 1..333, there are:")
var practical = []
for (i in 1..333) {
if (isPractical.call(i)) {
practical.add(i)
}
}
System.print(" %(practical.count) practical numbers")
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))")</
{{out}}
Line 600 ⟶ 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>
| |||