Rosetta Code

Factor-perfect numbers: Difference between revisions

Page Discussion

Factor-perfect numbers (view source)

Revision as of 14:32, 8 October 2022

1,150 bytes removed ,  1 year ago
m
→‎{{header|Phix}}: replaced my beloved g() with the even faster cached erdosFactorCount().
(→‎{{header|Wren}}: Changed to Erdos method for factor counting - another huge speed-up > 30x.)
m (→‎{{header|Phix}}: replaced my beloved g() with the even faster cached erdosFactorCount().)
Line 127:
=={{header|Phix}}==
{{libheader|Phix/online}}
You can run this online [http://phix.x10.mx/p2js/fpn.htm here]. Note(expect thata myblank routinescreen namesfor of f(~30s), m(), and g() match my detailed understanding of what I'm doing here perfectly.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo/rosetta/factor-perfect_numbers.exw
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">fget_factor_set</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">x</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: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span> <span style="color: #008080;">in</span> <span style="color: #000000;">fget_factor_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">&</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 159 ⟶ 162:
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">48</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fget_factor_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">jbm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">bool</span> <span style="color: #000000;">munge</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">munge</span> <span style="color: #008080;">then</span> <span style="color: #000000;">rN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rN</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;">if</span>
Line 168 ⟶ 171:
<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;">"%d sequences using second definition:\n%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">jbm</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))</span>
<span style="color: #008080004080;">functioninteger</span> <span style="color: #000000;">gefc_cache</span> <span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #0000007060A8;">nnew_dict</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: #004080008080;">integerfunction</span> <span style="color: #000000;">lerdosFactorCount</span> <span style="color: #0000FF;">=(</span> <span style="color: #7060A8004080;">lengthinteger</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ddivs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeatfactors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ln</span><span style="color: #0000FF;">)</span>
<span style="color: #008080004080;">forinteger</span> <span style="color: #000000;">ires</span> <span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080008080;">integerfor</span> <span style="color: #000000;">kd</span> <span style="color: #0000FF008080;">=in</span> <span style="color: #000000;">fdivs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF008080;">]do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[,</span> <span style="color: #000000;">ir</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">efc_cache</span><span style="color: #0000FF;">)</span>
<span style="color: #004080008080;">integerif</span> <span style="color: #000000;">jnode</span> <span style="color: #0000FF;">=</span> <span style="color: #000000004600;">iNULL</span><span style="color: #0000FF;">+</span><span style="color: #000000008080;">1then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">xr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nerdosFactorCount</span> <span style="color: #0080800000FF;">by(</span> <span style="color: #000000;">kt</span> <span style="color: #0080800000FF;">do)</span>
<span style="color: #0080807060A8;">while</span> <span style="color: #000000;">jsetd</span><span style="color: #0000FF;"><=(</span><span style="color: #000000;">l</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ft</span><span style="color: #0000FF;">[,</span><span style="color: #000000;">jr</span><span style="color: #0000FF;">]<,</span><span style="color: #000000;">x</span> <span style="color: #008080;">do</span> <span style="color: #000000;">jefc_cache</span><span style="color: #0000FF;">+=</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">forelse</span>▼
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">></span><span style="color: #000000;">l</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080000000;">ifr</span> <span style="color: #0000000000FF;">f=</span> <span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">[(</span><span style="color: #000000;">jnode</span><span style="color: #0000FF;">]=,</span><span style="color: #000000;">xefc_cache</span> <span style="color: #0080800000FF;">then)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</span> <span style="color: #0080800000FF;">end+=</span> <span style="color: #008080000000;">ifr</span>
▲ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 190 ⟶ 192:
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">while</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: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">78</span><span style="color: #0000FF;">:</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">gerdosFactorCount</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</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;">if</span>
Line 202 ⟶ 204:
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</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;">"Found %d: %s (%s)\n"</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: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</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;">t</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
Line 233 ⟶ 237:
{12,4} {16,3} {24,2} {48}
 
Found 79: 0 1 48 1280 2496 28672 29808 454656 2342912 (1.2s minute and 9s)
</pre>
Unfortunately it takes 4 minutes 13 seconds to find 9 under p2js, so I've limited that to 8 (as mentioned above, ~30s)
It takes about 6s under p2js, and 4&half; minutes to get the eighth, and 2 hours, 23 minutes and 6s to get the ninth (2342912) on desktop/Phix, compared to 13s for 7 and 39:18 for 8 in Julia (9th not tried), and since python took 2:20 for 7 I didn't even bother trying 8.
 
=={{header|Python}}==
Petelomax
7,820

edits

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