Practical numbers: Difference between revisions

Line 19:

=={{header|Phix}}==

~~atom~~ t0 = ~~time~~()

function sum_of_any_subset(integer n, sequence f)

-- return true if any subset of f sums to n.

⚫

~~<span~~ ~~style="color:~~ ~~#008080;">function~~ ~~<span~~ ~~style="color:~~ ~~#000000;">sumset~~(~~sequence~~ ~~res~~, ~~set~~, ~~integer~~ ~~tot~~=0, ~~done~~=~~<span~~ ~~style="color: #000000;">0~~)

if ~~tot~~<~~length~~(~~res~~) then

if find(n,f) then return true end if

if ~~tot~~!=~~0~~ ~~and res~~[~~tot~~~~]=0 then~~

integer total = sum(f)

~~res~~[~~tot~~] = 1

if n=total then return true

~~res~~~~[$]~~ += 1

elsif n>total then return false end if

~~end~~ if

integer d = n-f[$]

~~done~~ += 1

f = f[1..$-1]

if ~~done<=~~~~length~~(~~set~~) ~~and~~ ~~res[$]<length(res~~)~~ then~~

return find(d,f)

~~res~~ = ~~sumset~~~~(</span~~>~~res,~~~~set~~~~<span~~ ~~style="color: #0000FF;">,~~~~tot~~~~<span~~ ~~style="color: #0000FF;">+~~~~set~~[~~done~~],~~done~~)

or (d>0 and sum_of_any_subset(d, f))

~~res =~~ ~~sumset~~(~~res~~,~~<span~~ ~~style="color: #000000;">set,tot,~~~~done~~)

or sum_of_any_subset(n, f)

end if

end function

⚫

end if

⚫

return ~~res~~

end function

function is_practical(integer n)

~~return~~ ~~not find(~~0~~<span~~ ~~style="color: #0000FF;">,sumset~~~~(repeat~~~~<span~~ ~~style="color: #0000FF;">(0,n),~~factors(n,-1)))

sequence f = factors(n,-1)

for i=1 to n-1 do

⚫

if not sum_of_any_subset(i,f) then return false end if

⚫

end for

⚫

return true

end function

Line 44:

Line 46:

procedure stretch(integer n)

printf(1,"is_practical(%d):%t ~~(%s)~~\n",{n,is_practical(n),elapsed(time()-t0)})

printf(1,"is_practical(%d):%t\n",{n,is_practical(n)})

end procedure

papply({666,6666,66666,672,720},stretch)

Line 50:

Line 52:

<pre>

Found 76 practical numbers:

Found 77 practical numbers:

2, 4, 6, 8, 12, 16, 18, 20, 24~~, 28~~, ..., 288, 294, 300, 304, 306, 308, 312, 320, 324, 330

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, ..., 288, 294, 300, 304, 306, 308, 312, 320, 324, 330

is_practical(666):true ~~(0.3s)~~

is_practical(666):true

is_practical(6666):true ~~(0.3s)~~

is_practical(6666):true

is_practical(66666):false ~~(0.3s)~~

is_practical(66666):false

is_practical(672):true ~~(1.5s)~~

is_practical(672):true

is_practical(720):true ~~(1 minute and 7s)~~

is_practical(720):true

</pre>

@@ Line 19: / Line 19: @@
 =={{header|Phix}}==
+{{trans|Python|(the composition of functions version)}}
 <!--<lang Phix>-->
- <span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
+ <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>
- <span style="color: #008080;">function</span> <span style="color: #000000;">sumset</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
-     <span style="color: #008080;">if</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
+     <span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-         <span style="color: #008080;">if</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tot</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
+     <span style="color: #004080;">integer</span> <span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
-             <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tot</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
+     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">total</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
-             <span style="color: #000000;">res</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
+     <span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">total</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+     <span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">f</span><span style="color: #0000FF;">[$]</span>
-         <span style="color: #000000;">done</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
+     <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
-         <span style="color: #008080;">if</span> <span style="color: #000000;">done</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[$]<</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
+     <span style="color: #008080;">return</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
-             <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sumset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tot</span><span style="color: #0000FF;">+</span><span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">done</span><span style="color: #0000FF;">],</span><span style="color: #000000;">done</span><span style="color: #0000FF;">)</span>
+         <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">sum_of_any_subset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">))</span>
-             <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sumset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tot</span><span style="color: #0000FF;">,</span><span style="color: #000000;">done</span><span style="color: #0000FF;">)</span>
+         <span style="color: #008080;">or</span> <span style="color: #000000;">sum_of_any_subset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
-         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-     <span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
- <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  <span style="color: #008080;">function</span> <span style="color: #000000;">is_practical</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: #008080;">return</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sumset</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</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: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
+     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
+         <span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">sum_of_any_subset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+     <span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
  <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
@@ Line 44: / Line 46: @@
  <span style="color: #008080;">procedure</span> <span style="color: #000000;">stretch</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: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"is_practical(%d):%t (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">is_practical</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
+     <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"is_practical(%d):%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">is_practical</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)})</span>
  <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>
@@ Line 50: / Line 52: @@
 {{out}}
 <pre>
-Found 76 practical numbers:
+Found 77 practical numbers:
-,   4,   6,   8,  12,  16,  18,  20,  24,  28, ..., 288, 294, 300, 304, 306, 308, 312, 320, 324, 330
+,   2,   4,   6,   8,  12,  16,  18,  20,  24, ..., 288, 294, 300, 304, 306, 308, 312, 320, 324, 330
-is_practical(666):true (0.3s)
+is_practical(666):true
-is_practical(6666):true (0.3s)
+is_practical(6666):true
-is_practical(66666):false (0.3s)
+is_practical(66666):false
-is_practical(672):true (1.5s)
+is_practical(672):true
-is_practical(720):true (1 minute and 7s)
+is_practical(720):true
 </pre>