Minimum multiple of m where digital sum equals m: Difference between revisions
Content deleted Content added
→much faster: added run online link |
much simpler to 1000 |
||
Line 1,537:
361: 135734072022160637119113296398891966759 165690607734806629834254143646408839779 212093663911845730027548209366391184573 217032967032967032967032967032967032967 1095586301369863013698630136986301369863
366: 270491803278688524590163934425956284153 272479564032425067847411444141689373297 1086956521739130163043478260869565217391 1027100271002710027100271002710027100271
"2 minutes and 29s"
</pre>
===much simpler, to 1000===
Uses dynamic programming, at least I think it does.
Maintains a grid of digit sum against remainder in the form of the (final) digit that got us there first (so it's the smallest) along with a (parent) link to the chain of preceding digits. In effect, we are simply performing a breadth first search of unvisited nodes to get from {0,0} aka "" to {n,0} ie a digital sum of n with no remainder. The clever (ok, obvious if you prefer) maths bit is remainder(<parent's remainder>*10,n) when appending each individual digit.
While a fair bit slower on most individual numbers (esp under pwa/p2js) it hits far fewer bottlenecks such as that 275 above, and at least past 200 turns out to be quite a bit faster. However there is no equivalent trailing zero optimisation that I can see, and it caps out at 1e4 on 32 bit, 2e4 on 64 bit, for obvious reasons the square root of the hard limits of the above (assuming a number the code above doesn't pick a fight with).<br>
Translation of the C++ code on [[oeis:A002998|A002998]] but with the additional final divide for [[oeis:A131382|A131382]] and significantly clearer imnsho.
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> <span style="color: #000080;font-style:italic;">-- (for the final divide only)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">mmnn</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;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">"0"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (edge case)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</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: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)),</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"0"</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">parent</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: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)),</span> <span style="color: #000000;">queue</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">dsum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">residue</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (found or queue not empty at end of loop)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dsum</span><span style="color: #0000FF;">></span><span style="color: #000000;">n</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: #008080;">if</span> <span style="color: #000000;">dsum</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span> <span style="color: #008080;">and</span> <span style="color: #000000;">residue</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- success!!</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</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: #000000;">digit</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">pdx</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pdx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">res</span>
<span style="color: #000000;">pdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">parent</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pdx</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">drx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dsum</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">residue</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">drx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">drx</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: #000000;">digit</span>
<span style="color: #000000;">parent</span><span style="color: #0000FF;">[</span><span style="color: #000000;">drx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pdx</span>
<span style="color: #000000;">queue</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">queue</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">dsum</span><span style="color: #0000FF;">,</span><span style="color: #000000;">residue</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">dsum</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">residue</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">residue</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</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;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">queue</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">"FAIL"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">dsum</span><span style="color: #0000FF;">,</span><span style="color: #000000;">residue</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">queue</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">queue</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">queue</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
<span style="color: #000000;">pdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dsum</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">residue</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">residue</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">residue</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</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;">while</span>
<span style="color: #008080;">return</span> <span style="color: #008000;">"what???"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<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: #004080;">integer</span> <span style="color: #000000;">llen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">5</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">200</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- 1.2s (15.4s under pwa/p2js)
--for n=1 to 274 do -- 3.1s
--for n=1 to 369 do -- 7.1s
--for n=1 to 500 do -- 19s
--for n=1 to 1000 do -- 2 mins 29s</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mmnn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">llen</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: #004080;">bool</span> <span style="color: #000000;">bCR</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">101</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">llen</span><span style="color: #0000FF;">></span><span style="color: #000000;">118</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bCR</span> <span style="color: #008080;">then</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;">"\n%3d:"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">llen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">5</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;">end</span> <span style="color: #008080;">if</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;">" %-11s"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- printf(1,"%d %s\n",{n,mmnn(n)}) // Generate b-file for A131382 (1..1000)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--printf(1,"%d %s\n",{1e3,mmnn(1e3)}) -- 0.6s
--printf(1,"%d %s\n",{1e4,mmnn(1e4)}) -- 1min 8s
--printf(1,"%d %s\n",{2e4,mmnn(2e4)}) -- crashes on 32 bit, 6 minutes and 18s on 64 bit
--printf(1,"%d %s\n",{1e6,mmnn(1e6)}) -- not a chance!</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;">"\n"</span><span style="color: #0000FF;">)</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>
<!--</lang>-->
<!--</lang>-->
{{out}}
Coincidentally taking exactly as long to get to 1000 as the above took to get to 369, as above with slightly different line breaks, plus
<pre>
<snip>
995: 2010040201005025125628140703517587939698492462311557788944723618090452261306532663316582914572864321608040201
996: 1907630522088353413654618473895481927710843373493975903614457831325301204819277108433734939759036144578313253
997: 1003009027081243731193580742226579739217652958876629889669007021063189568706118355065195586760279839518555667
998: 2004008016032064128256513026052104208416833667234468937875751503006012024048096192384769539078156312625250501
999: 1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001
1000: 1999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
"2 minutes and 29s"
</pre>
| |||