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

Content added Content deleted

Inline

@@ Line 1,079: / Line 1,079: @@
  -- (actually, it turns out to be faster this way anyhows)</span>
- <span style="color: #008080;">function</span> <span style="color: #000000;">rmc</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;">n</span><span style="color: #0000FF;">,</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;">digits</span><span style="color: #0000FF;">))</span>
+ <span style="color: #008080;">function</span> <span style="color: #000000;">rmc</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;">n</span><span style="color: #0000FF;">)</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: #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;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
      <span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rc</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
          <span style="color: #000000;">rc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rc</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
@@ Line 1,086: / Line 1,087: @@
      <span style="color: #004080;">sequence</span> <span style="color: #000000;">rcn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
      <span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rcn</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">l</span> <span style="color: #008080;">then</span>
-         <span style="color: #000000;">rc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- kill refcount</span>
+         <span style="color: #000000;">rc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (kill refcount)</span>
          <span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rcn</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
              <span style="color: #000000;">rcn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rcn</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rcn</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>
@@ Line 1,107: / Line 1,108: @@
      -- Just as we can emulate normal counting using an array of digits,
      -- we can count while maintaining a sum of digits, which means we
-     -- have to find both an incrementable and a decrementable digit,
+     -- have to find both a decrementable and an incrementable digit,
-     -- moving the latter to the end(ish), or if none such prepend a 1,
+     -- moving the former to the end(ish), or if none such prepend a 1,
      -- eg: 5 -&gt; 14 -&gt; 23 -&gt; 32 -&gt; 41 -&gt; 50 -&gt; 104 -&gt; 113 -&gt; 122 -&gt; 131
      -- -&gt; 140 -&gt; 203 .. 230 -&gt; 302 .. 500 -&gt; 1004 .. 10004, etc.
@@ Line 1,116: / Line 1,117: @@
      -- -&gt; 806 .. 860 -&gt; 905 .. 950 -&gt; 1049, etc.
      -- in that last case, what we actually need to do is decrement the
-     -- 5 (-&gt;940), and then reverse the whole thing, then prepend a 1,
+     -- 5 (-&gt;940), then reverse the whole thing, and then prepend a 1,
-     -- likewise if we increment a middle digit, dec & reverse(rest).
+     -- likewise if we increment a middle digit, dec then reverse(rest).
      -- In the extreme case you would want 1 -&gt; 10 -&gt; 100 -&gt; 1000, etc,
      -- although since 1 passes muster we would never actually do that.
      --</span>
-     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">sprint</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: #000080;font-style:italic;">-- (avoid remainder(x,0|1))
+     <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;">-- avoid remainder(x,0), and tz=inf
-     -- optimising for trailing zeroes makes a huge difference</span>
+     -- 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: #0000FF;">,</span> <span style="color: #000000;">tz</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</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>
@@ Line 1,129: / Line 1,130: @@
          <span style="color: #000000;">tz</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
      <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
-     <span style="color: #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...</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 3*)</span>
-     <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: #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;">-- we need l 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: #000080;font-style:italic;">-- ...and this first digit</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: #000080;font-style:italic;">-- ...and this first digit</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: #008000;">'0'</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: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tz</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- eg n=14 -&gt; "59"</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: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tz</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: #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: #008080;">while</span> <span style="color: #000000;">rmc</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: #000000;">0</span> <span style="color: #008080;">do</span>
-         <span style="color: #004080;">integer</span> <span style="color: #000000;">rem</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rmc</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;">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: #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>
@@ Line 1,158: / Line 1,157: @@
                      <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: #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;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #000000;">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: #7060A8;">reverse</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;">else</span> <span style="color: #000080;font-style:italic;">-- (i=1 and (digits[1]=9] or no decrementable) case)</span>
+                     <span style="color: #008080;">else</span> <span style="color: #000080;font-style:italic;">-- (i=1, so digits[1]=9 or no decrementable)</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>
@@ Line 1,187: / Line 1,186: @@
      <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: #7060A8;">puts</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: #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>-->
@@ Line 1,215: / Line 1,214: @@
 : 4423076923076923 3821656050955414 6202531582278481 5660371069181761 124999999999999993
 : 12415527950310559 12345679012345679 18404907975398773 48773170731707317
+,000,000: 19999999999999999999...99999999999999999999 (111,112 digits)
 "1.1s"
 </pre>