Perfect numbers: Difference between revisions
→{{header|Picat}}
Line 2,898:
echo $num . PHP_EOL;
}</lang>
=={{header|Picat}}==
First is the slow perfect1/1 that use the simple divisors/1 function:
<lang Picat>go =>
println(perfect1=[I : I in 1..10_000, perfect1(I)]),
nl.
perfect1(N) => sum(divisors(N)) == N.
divisors(N) = [J: J in 1..1+N div 2, N mod J == 0].</lang>
{{out}}
<pre>perfect1 = [1,6,28,496,8128]</pre>
The formula for perfect number candidates is: 2^(p-1)*(2^p-1) for prime p. This is used to find some more perfect numbers in reasonable time. perfect2/1 is a faster version of checking if a number is perfect.
<lang Picat>go2 =>
println("Using the formula: 2^(p-1)*(2^p-1) for prime p"),
foreach(P in primes(32))
PF=perfectf(P),
% Check that it is really a perfect number
if perfect2(PF) then
printf("%w (prime %w)\n",PF,P)
end
end,
nl.
% Formula for perfect number candidates:
% 2^(p-1)*(2^p-1) where p is a prime
%
perfectf(P) = (2**(P-1))*((2**P)-1).
% Faster check of a perfect number
perfect2(N) => sum_divisors(N) == N.
% Sum of divisors
table
sum_divisors(N) = Sum =>
sum_divisors(2,N,1,Sum).
sum_divisors(I,N,Sum0,Sum), I > floor(sqrt(N)) =>
Sum = Sum0.
% I is a divisor of N
sum_divisors(I,N,Sum0,Sum), N mod I == 0 =>
Sum1 = Sum0 + I,
(I != N div I ->
Sum2 = Sum1 + N div I
;
Sum2 = Sum1
),
sum_divisors(I+1,N,Sum2,Sum).
% I is not a divisor of N.
sum_divisors(I,N,Sum0,Sum) =>
sum_divisors(I+1,N,Sum0,Sum).</lang>
{{out}}
<pre>6 (prime 2)
28 (prime 3)
496 (prime 5)
8128 (prime 7)
33550336 (prime 13)
8589869056 (prime 17)
137438691328 (prime 19)
2305843008139952128 (prime 31)
CPU time 118.039 seconds. Backtracks: 0</pre>
Now let's cheat a little. At [[Media:https://en.wikipedia.org/wiki/Perfect_number]] there is a list of the first 48 primes that generates perfect numbers according to the formula 2^(p-1)*(2^p-1) for prime p.
The perfect numbers are printed only if they has < 80 digits, otherwise the number of digits are shown. The program stops when reaching a number with more than 100 000 digits. (Note: The major time running this program is getting the number of digits.)
<lang Picat>go3 =>
ValidP = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,
1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213,
19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091,
756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593,
13466917, 20996011, 24036583, 25964951, 30402457, 32582657,
37156667, 42643801, 43112609, 57885161],
foreach(P in ValidP)
printf("prime %w: ", P),
PF = perfectf(P),
Len = PF.to_string.len,
if Len < 80 then
println(PF)
else
println(len=Len)
end,
if Len >= 100_000 then
fail
end
end,
nl.</lang>
{{out}}
<pre>prime 2: 6
prime 3: 28
prime 5: 496
prime 7: 8128
prime 13: 33550336
prime 17: 8589869056
prime 19: 137438691328
prime 31: 2305843008139952128
prime 61: 2658455991569831744654692615953842176
prime 89: 191561942608236107294793378084303638130997321548169216
prime 107: 13164036458569648337239753460458722910223472318386943117783728128
prime 127: 14474011154664524427946373126085988481573677491474835889066354349131199152128
prime 521: len = 314
prime 607: len = 366
prime 1279: len = 770
prime 2203: len = 1327
prime 2281: len = 1373
prime 3217: len = 1937
prime 4253: len = 2561
prime 4423: len = 2663
prime 9689: len = 5834
prime 9941: len = 5985
prime 11213: len = 6751
prime 19937: len = 12003
prime 21701: len = 13066
prime 23209: len = 13973
prime 44497: len = 26790
prime 86243: len = 51924
prime 110503: len = 66530
prime 132049: len = 79502
prime 216091: len = 130100</pre>
=={{header|PicoLisp}}==
| |||