Rosetta Code

Minimum multiple of m where digital sum equals m: Difference between revisions

Page Discussion

Minimum multiple of m where digital sum equals m (view source)

Revision as of 12:16, 14 February 2022

53,701 bytes added ,  2 years ago
→‎much faster: now to 369
(added AWK)
(→‎much faster: now to 369)
Line 1,108:
<small>(Not that the above is particularly slow, but you certainly wouldn't want to push it much past 70)</small>
<!--<lang Phix>(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\mmnn.exw</span>
<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;">forward</span> <span style="color: #008080;">function</span> <span style="color: #000000;">rackup5</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">forward</span> <span style="color: #008080;">function</span> <span style="color: #000000;">rackup11</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">r5</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">forward</span> <span style="color: #008080;">function</span> <span style="color: #000000;">nextup11</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</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>
Line 1,134 ⟶ 1,138:
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- this many trailing 9s...</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- ...and this first digit</span>
<span style="color: #000000;">n0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- eg n=14 -&gt; "59"</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000080;font-style:italic;">-- optimising for trailing zeroes makes a truly *huge* difference</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n0</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">10</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'0'</span> <span style="color: #000080;font-style:italic;">-- (these be static, aka forever past "l")</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">r5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">5</span> <span style="color: #000080;font-style:italic;">-- not quite so much (maybe 30%)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">r5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- ten-fold improvement on some</span>
<span style="color: #000000;">r11</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- took 165 from 1min 25s to 6s,
-- (even faster now r5 working)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r5</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rackup5</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r11</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rackup11</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r5</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</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;">-- calculate remainder(digits,n) digit-wise; faster than mpz</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rem</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
Line 1,156 ⟶ 1,166:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</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: #000080;font-style:italic;">-- (only triggers on eg 202, 222, 271 and higher)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</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: #000000;">digits</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>
<span style="color: #008080;">whileif</span> <span style="color: #004600008080;">truenot</span> <span style="color: #008080000000;">dor11</span> <span style="color: #000080;font-style:italic008080;">-- (r5 optimisation at "end while")then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ddd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- decrementable digit position</span>
<span style="color: #000000;">ddd</span> <span style="color: #000080;font-style:italic;">-- decrementable digit value</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">bIncAbleFound</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</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;">integerif</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;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-></span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dd</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0d</span> <span style="color: #0080800000FF;">and</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">theni</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ddd</span> <span style="color: #0000FF008080;">and</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]<</span><span style="color: #008000;">'9'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ddddigits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d1</span>
<span style="color: #000000;">digits</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;">1</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">bIncAbleFounddigits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">dl</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9digits</span><span style="color: #0000FF;">[</span><span style="color: #008080000000;">andi</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dd1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">ifexit</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bIncAbleFound</span> <span style="color: #008080;">orelsif</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- (so digits[1]=9 or no decrementable)</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ddd</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span>
<span style="color: #008080000000;">ifdigits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bIncAbleFoundd</span><span style="color: #0000FF;">]</span> <span style="color: #0080800000FF;">-=</span> <span style="color: #000000;">then1</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digits1</span><span style="color: #0000FF;">[..</span><span style="color: #000000;">il</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ddigits</span><span style="color: #0000FF;">+[</span><span style="color: #008000000000;">'1'</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverseprepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000008000;">'1'</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span>
<span style="color: #008080000000;">elsel</span> <span style="color: #000080;font-style:italic0000FF;">-- (i+=1,</span> so<span digits[1]style=9 or"color: no decrementable)#000000;">1</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">exit</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;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">r5</span> <span style="color: #008080;">or</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">],</span><span style="color: #008000;">"05"</span><span style="color: #0000FF;">)</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;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">else</span>
<span style="color: #000080;font-style:italic;">-- Same as above but with additional rules</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nextup11</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</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;">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;">digits</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: #008080004080;">returnstring</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;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rackup5</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- converts digits to next (odd) number divisible by 5, while
-- maintaining the exact same sum of digits unaltered.
-- Techincally divisible by 5 is ends in 5 or 0, but since we
-- have already dealt with 10s, we know that n0 (above) must
-- be odd and hence digits[1..l] always end in 5, so we play
-- a neat and simple little trick of cropping the length by 1
-- to make the final 5 static, same as we do with trailing 0s.
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'5'</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'5'</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</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;">d</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'5'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</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: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">digits</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;">'9'</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">-</span><span style="color: #000000;">5</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">digits</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</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: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</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;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">swarpp11</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- special pairwise swapping/reversal for divisible by 11 numbers, eg:
--
-- | 7654321 | , | 653421 | , | 54321 | , | 4321 | , | 321 | , | 21 | , | 1 |
-- &gt; 1234567 &lt; &gt; 213465 &lt; &gt; 12345 &lt; &gt; 2143 &lt; &gt; 123 &lt; &gt; 21 &lt; &gt; 1 &lt;
--
-- (ie after bumping some prior digits following the rules (see below), we
-- need to make the remaining digits (7 or less in the above) as small as
-- legally possible but obviously without breaking any of the said rules.)
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">s</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;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</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;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nextup11</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Divisible by 11 uses the additional rule that the
-- sum of odd place digits - sum of even place digits
-- must be a multiple of 11 (including zero).
-- Hence we look for an odd/even decrementable digit
-- that can pair with an odd/even incrementable digit,
-- or an odd/even decrementable-by-11 set to pair off
-- with an even/odd incrementable-by-11 set/sum.
-- (for the latter see the bTransferable11 flag)
-- Likewise we use a slightly different method to
-- increase the number of digits, and kick-start
-- things off with the rackup11() routine below.
--
-- Aside: A variation is probably extendible to 101,
-- expressed using alternating pairs of digits, eg:
-- 74*11 = 814, 8-1+4 = 11
-- 7242*101 = 731442, 73-14+42 = 101
-- (which really is the same rule writ different)
-- There is also sum of pairs/triples for 11 and 111:
-- 74*11 = 814, 8+14 = 22
-- 237*111 = 26307, 26+307 = 333
-- (not entirely sure that can actually be applied)
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- a digit</span>
<span style="color: #000000;">dd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- decrementable digit position (scratch)</span>
<span style="color: #000000;">ddd</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- decrementable digit value """</span>
<span style="color: #000000;">td</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- total decrementable digits</span>
<span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- total incrementable digits</span>
<span style="color: #000000;">od</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- decrementable odd digit position</span>
<span style="color: #000000;">ed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- decrementable even digit position</span>
<span style="color: #000000;">dod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- decrementable odd digit value</span>
<span style="color: #000000;">ded</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- decrementable even digit value</span>
<span style="color: #000000;">tod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- total odd decrementable digits</span>
<span style="color: #000000;">ted</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- total even decrementable digits</span>
<span style="color: #000000;">iod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- total odd incrementable digits</span>
<span style="color: #000000;">ied</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- total even incrementable digits</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">bIncAbleFound</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">bTransferable11</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">wasdig</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">transdigits</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</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: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">tod</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span>
<span style="color: #000000;">iod</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">-</span><span style="color: #000000;">d</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">od</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">od</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">dod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">dd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">od</span>
<span style="color: #000000;">ddd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dod</span>
<span style="color: #000000;">bIncAbleFound</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">9</span> <span style="color: #008080;">and</span> <span style="color: #000000;">dd</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">bTransferable11</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">iod</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">11</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ted</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">11</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">ted</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span>
<span style="color: #000000;">ied</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">-</span><span style="color: #000000;">d</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">ded</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">dd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ed</span>
<span style="color: #000000;">ddd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ded</span>
<span style="color: #000000;">bIncAbleFound</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">9</span> <span style="color: #008080;">and</span> <span style="color: #000000;">dd</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">bTransferable11</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ied</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">11</span> <span style="color: #008080;">and</span> <span style="color: #000000;">tod</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">11</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bTransferable11</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">od</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)=</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)?{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}:{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">,</span><span style="color: #000000;">td</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">transdigits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">ti</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">od</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">od</span><span style="color: #0000FF;">],</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ti</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">t</span>
<span style="color: #000000;">transdigits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">od</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">t</span>
<span style="color: #000000;">od</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">td</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">td</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">td</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">t</span>
<span style="color: #000000;">transdigits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">t</span>
<span style="color: #000000;">ed</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">transdigits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">swarpp11</span><span style="color: #0000FF;">(</span><span style="color: #000000;">transdigits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">transdigits</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">digits</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">bTransferable11</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">elsif</span> <span style="color: #008080;">not</span> <span style="color: #000000;">bIncAbleFound</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">transdigits</span>
<span style="color: #008080;">exit</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: #008080;">if</span> <span style="color: #000000;">bIncAbleFound</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ddd</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span>
<span style="color: #000000;">digits</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: #008000;">'1'</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">swarpp11</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">bTransferable11</span> <span style="color: #008080;">and</span> <span style="color: #000000;">transdigits</span><span style="color: #0000FF;"><</span><span style="color: #000000;">digits</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">transdigits</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- (so digits[1]=9 or no o/e decrementable)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ddd</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)?{</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ded</span><span style="color: #0000FF;">}:{</span><span style="color: #000000;">od</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dod</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ddd</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">exit</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: #0000FF;">{</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rackup11</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">r5</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Converts digits to next number divisible by 11, while
-- maintaining the exact same sum of digits unaltered, eg
-- 29 -&gt; 209, 499 -&gt; 2299, 6999 -&gt; 42999, 89999 -&gt; 449999,
-- 1999999 -&gt; 6499999, 39999999 -&gt; 66999999, 599999999 -&gt;
-- 869999999, 7999999999 -&gt; 8899999999, 99999999999 -&gt;
-- 1098999999999, 2999999999999 -&gt; 11999999999999.
--
-- For divisible by 55 we've already got the first divisible by 5 and
-- set that in stone, aka digits[l+1] is 5, so here we must take that
-- quickly into account.
--</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r5</span> <span style="color: #008080;">then</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">od</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)),</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">11</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">ed</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)),</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">11</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">od</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">od</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">11</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r5</span> <span style="color: #008080;">then</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">od</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">ed</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">--
-- Aside: I couldn't quite get my head around the apparently convoluted rules
-- of which way to go, but obviously if od=2 and ed=9 then either:
-- add 9 to the odd digits and subtract it from the even digits, or
-- add 2 to the even digits and subtract it from the odd digits,
-- and then in both cases add prefixes for anything you couldn't do.
-- The simplest thing is to just do both and select the smaller,
-- plus a couple of quick checks (wood|weod&gt;9) for odd-od busted.
--</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- a digit</span>
<span style="color: #000000;">woed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">weed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ed</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- work vars for odd+ed, even-ed</span>
<span style="color: #000000;">wood</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">od</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">weod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">od</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- work vars for odd-od, even+od</span>
<span style="color: #000000;">loed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span> <span style="color: #000080;font-style:italic;">-- new value for l should we switch</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">odd_ed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span> <span style="color: #000080;font-style:italic;">-- (odd-od done in digits direct)</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;">l</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">odd_ed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">woed</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- add ed to odd digits</span>
<span style="color: #000000;">odd_ed</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: #000000;">woed</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wood</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- subtract od from ""</span>
<span style="color: #000000;">digits</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: #000000;">wood</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">odd_ed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weed</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- subtract ed from even</span>
<span style="color: #000000;">odd_ed</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: #000000;">weed</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">weod</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- add od to odd digits</span>
<span style="color: #000000;">digits</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: #000000;">weod</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</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;">if</span> <span style="color: #000000;">woed</span> <span style="color: #008080;">or</span> <span style="color: #000000;">weed</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">odd_ed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">weed</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">odd_ed</span>
<span style="color: #000000;">loed</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">woed</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">odd_ed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">woed</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">odd_ed</span>
<span style="color: #000000;">loed</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</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: #008080;">if</span> <span style="color: #000000;">wood</span> <span style="color: #008080;">or</span> <span style="color: #000000;">weod</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">weod</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">digits</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">wood</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wood</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">digits</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</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: #008080;">if</span> <span style="color: #000000;">loed</span><span style="color: #0000FF;"><</span><span style="color: #000000;">l</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">weod</span><span style="color: #0000FF;">></span><span style="color: #000000;">9</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">wood</span><span style="color: #0000FF;">></span><span style="color: #000000;">9</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">loed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">and</span> <span style="color: #000000;">odd_ed</span><span style="color: #0000FF;"><</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">odd_ed</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">loed</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: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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: #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;">100</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- 0.4s2s</span>
<span style="color: #008080;">if</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: #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: #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;">mmnn</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;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">101</span> <span style="color: #008080;">to</span> <span style="color: #000000;">164200</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- 0.7s, but(including mmnn(165above) takes 1mins 25s
--for n=101 to 274 do -- 1mins12.8s, 50sbut mmnn(most275) fromtakes 165,2 gaveminutes upand on 275)</span>25s
--for n=101 to 369 do -- 2 minutes 31s, but I gave up on 370
--for n=101 to 666 do -- 3 minutes 31s, skipping 11 tricky ones
--if not find(n,{275,370,(404),481,505,518,542,625,629,656,666}) then</span>
<span style="color: #008080;">if</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;">5</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</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: #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;">mmnn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)})</span>
<span style="color: #000080;font-style:italic;">--end if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"\n1,000,000: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mmnn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e6</span><span style="color: #0000FF;">))})</span> <span style="color: #000080;font-style:italic;">-- (0.0s)</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: #000080;font-style:italic;">-- 1.1s</span>
<!--</lang>-->
{{out}}
Line 1,231 ⟶ 1,492:
151: 1258278145629139 3217105263157894 1307189477124183 3830512987012987 5161290322516129
156: 4423076923076923 3821656050955414 6202531582278481 5660371069181761 124999999999999993
161: 12415527950310559 12345679012345679 18404907975398773 48773170731707317
1,000,000: 19999999999999999999...99999999999999999999 (111,112 digits)
"1.1s"
</pre>
As shown commented out, it will carry on a bit further, but I gave up on 275, and it looks to me like some quite wierd patterns are starting to appear.
<pre style="font-size: 12px">
161: 12415527950310559 12345679012345679 18404907975398773 48773170731707317 430303030303030303
166: 48186144578313253 53233532874251497 119041666666666666 59165680473372781 588235235294117647
Line 1,245 ⟶ 1,500:
191: 15706806282722513089 41666666666666666614 36269424870466321243 46391752577319535567 153845641025641025641
196: 147959183673469382653 101517766497461928934 101010101010101010101 201005025125628040201 19999999999999999999999
1,000,000: 19999999999999999999...99999999999999999999 (111,112 digits)
"0.7s"
</pre>
As shown commented out, it will carry on a fair bit further, but I gave up on <del>275</del> 370, and <del>it looks to me like some quite wierd patterns are starting to appear</del> now I'm pretty sure any percieved pretty patterns were figments of my fetid imagination, far too random/sparse to be of any significant practical use.
<pre style="font-size: 9px">
201: 293532338308407960199 1900990099009900990099 438374384235960591133 490195588235294117647 1902439024390243902439
206: 1407766990291213592233 966183574879227052657 2836538461538461538461 10526315784688995215311 23809047619047619047619
Line 1,259 ⟶ 1,519:
261: 766283524904210727969348659 1908014885496183206106870229 1520912547528517110266121673 2992424242424242424242424242 7546792452452830188679245283
266: 3007481203007518796992481203 3333333295880149812734082397 10820895485074626865671641791 7397769516728620817843866171 37037037037037037037037037037
271: 31690036900369003690036900369 25735294117647055147058823529 29263003663003663003663003663 29197007299270072992700729927 1126909090909090909090909090909
276: 36231880434782608695652173913 36101083032490974729238266787 107910071942446039568345323741 71684229390681003584229390681 1428571428571428571428571428571
"1 minute and 50s"
281: 209964377188612099644128113879 212765957446808475177304964539 247314487632508833886925795053 352112676056337676056338028169 1052631578947017543859649122807
286: 1006993006993006993006993006993 1003484320557491289198606271777 1736111111111111111111111111076 1384083041522145328719723183391 13793103448275862068965517237931
291: 2061512027491374570446735395189 3356164041095890410958904109589 2730375426621160409215017064843 3061224149659863945578231292517 13559322033898305084745762711861
296: 16858108108108108108108108108108 37003367003367003367003367003367 16744966442919463087248322147651 16655518394648829431438127090301 1333333333333333333333333333333333
301: 23255813953488372092691029900299 29801324503311258278142384102649 130330033003300330033003300330033 98683881578947368421052631578947 196393442622950819672127868852459
306: 98039215686241830065359477124183 130293159283061889250814332247557 487012987012987012987012987012987 194174433656925566343042071197411 1935483870964516129032258064516129
311: 256913183279742765273311897106109 929483974358974358974358974358974 316293929712460063865814696485623 923248407643312101910828025477707 1873015873015873015873015873015873
316: 1895569303797468354430379746835443 1577287066246056782331198738170347 2201226100628930817610062893081761 10655172413793103448275862065830721 31249999999999999999999999999999684
321: 2800623052959498442367601246105919 6211177018633540372670807450310559 6188854489164086687306501547987613 12037037037037037037037037037037037 27692276923076923076923076923076923
326: 15337392638036809815950920245398773 18318012232415902140672782874617737 30457317073170731707317073170731707 24316109422492370820668693009118541 1030303030303030303030303030303030303
331: 57401812688821751963743202416918429 90331325301204819277108433734939759 203003003003003003003003003003003003 146706586826347305389218562874251497 238805970149253728358208955223880597
336: 208333333333333333333333333333333333 204747774480712166172106824925815727 266272189348816568044378698224852071 265191740412979351032448377581120941 2941176470587941176470588235294117647
341: 1612903225806451319648093841642228739 877192953216374269005847953216374269 1165889212827988338192419533527696793 2296511337209302325581395348837209302 2608695652173910144927536231884057971
346: 2283208092485549132947976878612716763 2305187319884726224783861671469740634 2873563218390804597701146551724137931 2865329512893982808020057306590257851 142856857142857142857142857142857142857
351: 11392849002849002849002849002849002849 19602272727272727272727272727272727244 14164300283286118980169971671388101983 16949152542372881355932203389802259887 28169014084504225352112676056338028169
356: 28061797752808988764044943820224719073 22408963585434173389355742296918767507 55586592178770949720670388268156424581 55431754874649025069637883008356545961 833333333333333333333333333333333333333
361: 135734072022160637119113296398891966759 165690607734806629834254143646408839779 212093663911845730027548209366391184573 217032967032967032967032967032967032967 1095586301369863013698630136986301369863
366: 270491803278688524590163934425956284153 272479564032425067847411444141689373297 1086956521739130163043478260869565217391 1027100271002710027100271002710027100271
"2 minutes and 29s"
</pre>
 
Petelomax
7,820

edits

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