Minimum multiple of m where digital sum equals m

From Rosetta Code
Revision as of 22:41, 27 August 2022 by Thundergnat (talk | contribs) (syntax highlighting fixup automation)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Task
Minimum multiple of m where digital sum equals m
You are encouraged to solve this task according to the task description, using any language you may know.

Generate the sequence a(n) when each element is the minimum integer multiple m such that the digit sum of n times m is equal to n.


Task
  • Find the first 40 elements of the sequence.


Stretch
  • Find the next 30 elements of the sequence.


See also



ALGOL 68[edit]

BEGIN # find the smallest m where mn = digit sum of n, n in 1 .. 70 #
    # returns the digit sum of n, n must be >= 0 #
    OP   DIGITSUM = ( INT n )INT:
         IF  n < 10 THEN n
         ELSE
            INT result := n MOD  10;
            INT v      := n OVER 10;
            WHILE v > 0 DO
                result +:= v MOD  10;
                v       := v OVER 10
            OD;
            result
         FI # DIGITSUM # ;
    # show the minimum multiples of n where the digit sum of the multiple is n #
    FOR n TO 70 DO
        BOOL found multiple := FALSE;
        FOR m WHILE NOT found multiple DO
            IF DIGITSUM ( m * n ) = n THEN
                found multiple := TRUE;
                print( ( " ", whole( m, -8 ) ) );
                IF n MOD 10 = 0 THEN print( ( newline ) ) FI
            FI
        OD
    OD
END
Output:
        1        1        1        1        1        1        1        1        1       19
       19        4       19       19       13       28       28       11       46      199
       19      109       73       37      199       73       37      271      172     1333
      289      559     1303      847     1657      833     1027     1576     1282    17497
     4339     2119     2323    10909    11111    12826    14617    14581    16102   199999
    17449    38269    56413    37037  1108909   142498   103507   154981   150661  1333333
   163918   322579   315873   937342  1076923  1030303   880597  1469116  1157971 12842857


APL[edit]

Works with: Dyalog APL
{n  (+1){n=+/10¯1×n}0 } ¨ 7 10⍴⍳70
Output:
     1      1      1      1       1       1      1       1       1       19
    19      4     19     19      13      28     28      11      46      199
    19    109     73     37     199      73     37     271     172     1333
   289    559   1303    847    1657     833   1027    1576    1282    17497
  4339   2119   2323  10909   11111   12826  14617   14581   16102   199999
 17449  38269  56413  37037 1108909  142498 103507  154981  150661  1333333
163918 322579 315873 937342 1076923 1030303 880597 1469116 1157971 12842857

AWK[edit]

# syntax: GAWK -f MINIMUM_MULTIPLE_OF_M_WHERE_DIGITAL_SUM_EQUALS_M.AWK
BEGIN {
    start = 1
    stop = 70
    printf("A131382 %d-%d:\n",start,stop)
    for (n=start; n<=stop; n++) {
      for (m=1; ; m++) {
        if (digit_sum(m*n,10) == n) {
          printf("%9d%1s",m,++count%10?"":"\n")
          break
        }
      }
    }
    exit(0)
}
function digit_sum(n,b,  s) { # digital sum of n in base b
    while (n) {
      s += n % b
      n = int(n/b)
    }
    return(s)
}
Output:
A131382 1-70:
        1         1         1         1         1         1         1         1         1        19
       19         4        19        19        13        28        28        11        46       199
       19       109        73        37       199        73        37       271       172      1333
      289       559      1303       847      1657       833      1027      1576      1282     17497
     4339      2119      2323     10909     11111     12826     14617     14581     16102    199999
    17449     38269     56413     37037   1108909    142498    103507    154981    150661   1333333
   163918    322579    315873    937342   1076923   1030303    880597   1469116   1157971  12842857

BASIC[edit]

BASIC256[edit]

c = 0
n = 1
while c < 70
    m = 1
    while 1
        nm = n*m
		t = 0
        while nm
            t += nm mod 10
            nm = floor(nm / 10)
        end while
        if t = n then exit while
        m += 1
    end while
    c += 1
    print rjust(string(m), 8); " ";
    if c mod 10 = 0 then print
    n += 1
end while
end
Output:
Igual que la entrada de FreeBASIC.

FreeBASIC[edit]

Translation of: Phix
#define floor(x) ((x*2.0-0.5) Shr 1)

Dim As Integer c = 0, n = 1
Do While c < 70
    Dim As Integer m = 1
    Do
        Dim As Integer nm = n*m, t = 0
        While nm
            t += nm Mod 10
            nm = floor(nm/10)
        Wend
        If t = n Then Exit Do : End If
        m += 1
    Loop
    c += 1
    Print Using "######## "; m;
    If c Mod 10 = 0 Then Print
    n += 1
Loop
Sleep
Output:
       1        1        1        1        1        1        1        1        1       19
      19        4       19       19       13       28       28       11       46      199
      19      109       73       37      199       73       37      271      172     1333
     289      559     1303      847     1657      833     1027     1576     1282    17497
    4339     2119     2323    10909    11111    12826    14617    14581    16102   199999
   17449    38269    56413    37037  1108909   142498   103507   154981   150661  1333333
  163918   322579   315873   937342  1076923  1030303   880597  1469116  1157971 12842857

Yabasic[edit]

c = 0
n = 1
while c < 70
    m = 1
    do
        nm = n*m
		t = 0
        while nm
            t = t + mod(nm, 10)
            nm = floor(nm / 10)
        wend
        if t = n then break : fi
        m = m + 1
    loop
    c = c + 1
    print m using "########", " ";
    if mod(c, 10) = 0 then print : fi
    n = n + 1
wend
end
Output:
Igual que la entrada de FreeBASIC.

C[edit]

#include <stdio.h>

unsigned digit_sum(unsigned n) {
    unsigned sum = 0;
    do { sum += n % 10; }
    while(n /= 10);
    return sum;
}

unsigned a131382(unsigned n) {
    unsigned m;
    for (m = 1; n != digit_sum(m*n); m++);
    return m;
}

int main() {
    unsigned n;
    for (n = 1; n <= 70; n++) {
        printf("%9u", a131382(n));
        if (n % 10 == 0) printf("\n");
    }
    return 0;
}
Output:
        1        1        1        1        1        1        1        1        1       19
       19        4       19       19       13       28       28       11       46      199
       19      109       73       37      199       73       37      271      172     1333
      289      559     1303      847     1657      833     1027     1576     1282    17497
     4339     2119     2323    10909    11111    12826    14617    14581    16102   199999
    17449    38269    56413    37037  1108909   142498   103507   154981   150661  1333333
   163918   322579   315873   937342  1076923  1030303   880597  1469116  1157971 12842857

C++[edit]

#include <iomanip>
#include <iostream>

int digit_sum(int n) {
    int sum = 0;
    for (; n > 0; n /= 10)
        sum += n % 10;
    return sum;
}

int main() {
    for (int n = 1; n <= 70; ++n) {
        for (int m = 1;; ++m) {
            if (digit_sum(m * n) == n) {
                std::cout << std::setw(8) << m << (n % 10 == 0 ? '\n' : ' ');
                break;
            }
        }
    }
}
Output:
       1        1        1        1        1        1        1        1        1       19
      19        4       19       19       13       28       28       11       46      199
      19      109       73       37      199       73       37      271      172     1333
     289      559     1303      847     1657      833     1027     1576     1282    17497
    4339     2119     2323    10909    11111    12826    14617    14581    16102   199999
   17449    38269    56413    37037  1108909   142498   103507   154981   150661  1333333
  163918   322579   315873   937342  1076923  1030303   880597  1469116  1157971 12842857

CLU[edit]

digit_sum = proc (n: int) returns (int)
    sum: int := 0
    while n > 0 do
        sum := sum + n // 10
        n := n / 10
    end
    return(sum)
end digit_sum

a131382 = iter () yields (int)
    n: int := 1
    while true do
        m: int := 1
        while digit_sum(m * n) ~= n do
            m := m + 1
        end
        yield(m)
        n := n + 1
    end
end a131382

start_up = proc ()
    po: stream := stream$primary_output()
    n: int := 0
    
    for m: int in a131382() do
        stream$putright(po, int$unparse(m), 9)
        n := n + 1
        if n = 70 then break end
        if n // 10 = 0 then stream$putl(po, "") end
    end
end start_up
Output:
        1        1        1        1        1        1        1        1        1       19
       19        4       19       19       13       28       28       11       46      199
       19      109       73       37      199       73       37      271      172     1333
      289      559     1303      847     1657      833     1027     1576     1282    17497
     4339     2119     2323    10909    11111    12826    14617    14581    16102   199999
    17449    38269    56413    37037  1108909   142498   103507   154981   150661  1333333
   163918   322579   315873   937342  1076923  1030303   880597  1469116  1157971 12842857

COBOL[edit]

       IDENTIFICATION DIVISION.
       PROGRAM-ID. A131382.
       
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 VARIABLES.
          03 MAXIMUM      PIC 99 VALUE 40.
          03 N            PIC 999.
          03 M            PIC 9(9).
          03 N-TIMES-M    PIC 9(9).
          03 DIGITS       PIC 9 OCCURS 9 TIMES,
                          REDEFINES N-TIMES-M,
                          INDEXED BY D.
          03 DIGITSUM     PIC 999 VALUE ZERO.
       01 OUTFMT.
          03 FILLER       PIC XX VALUE "A(".
          03 N-OUT        PIC Z9.
          03 FILLER       PIC X(4) VALUE ") = ".
          03 M-OUT        PIC Z(8)9.
       
       PROCEDURE DIVISION.
       BEGIN.
           PERFORM CALC-A131382 VARYING N FROM 1 BY 1
           UNTIL N IS GREATER THAN MAXIMUM.
           STOP RUN.
       
       CALC-A131382.
           PERFORM FIND-LEAST-M VARYING M FROM 1 BY 1
           UNTIL DIGITSUM IS EQUAL TO N.
           SUBTRACT 1 FROM M.
           MOVE N TO N-OUT.
           MOVE M TO M-OUT.
           DISPLAY OUTFMT.
           
       FIND-LEAST-M.
           MOVE ZERO TO DIGITSUM.
           MULTIPLY N BY M GIVING N-TIMES-M.
           PERFORM ADD-DIGIT VARYING D FROM 1 BY 1
           UNTIL D IS GREATER THAN 9.
       
       ADD-DIGIT.
           ADD DIGITS(D) TO DIGITSUM.
Output:
A( 1) =         1
A( 2) =         1
A( 3) =         1
A( 4) =         1
A( 5) =         1
A( 6) =         1
A( 7) =         1
A( 8) =         1
A( 9) =         1
A(10) =        19
A(11) =        19
A(12) =         4
A(13) =        19
A(14) =        19
A(15) =        13
A(16) =        28
A(17) =        28
A(18) =        11
A(19) =        46
A(20) =       199
A(21) =        19
A(22) =       109
A(23) =        73
A(24) =        37
A(25) =       199
A(26) =        73
A(27) =        37
A(28) =       271
A(29) =       172
A(30) =      1333
A(31) =       289
A(32) =       559
A(33) =      1303
A(34) =       847
A(35) =      1657
A(36) =       833
A(37) =      1027
A(38) =      1576
A(39) =      1282
A(40) =     17497

Cowgol[edit]

include "cowgol.coh";

sub digit_sum(n: uint32): (sum: uint8) is
    sum := 0;
    while n != 0 loop
        sum := sum + (n % 10) as uint8;
        n := n / 10;
    end loop;
end sub;

sub a131382(n: uint8): (m: uint32) is
    m := 1;
    while n != digit_sum(n as uint32 * m) loop
        m := m + 1;
    end loop;
end sub;

var n: uint8 := 1;
while n <= 70 loop
    print_i32(a131382(n));
    if n % 10 == 0 then print_nl(); 
    else print_char(' ');
    end if;
    n := n + 1;
end loop;
Output:
1 1 1 1 1 1 1 1 1 19
19 4 19 19 13 28 28 11 46 199
19 109 73 37 199 73 37 271 172 1333
289 559 1303 847 1657 833 1027 1576 1282 17497
4339 2119 2323 10909 11111 12826 14617 14581 16102 199999
17449 38269 56413 37037 1108909 142498 103507 154981 150661 1333333
163918 322579 315873 937342 1076923 1030303 880597 1469116 1157971 12842857

Draco[edit]

/* this is very slow even in emulation - if you're going to try it
 * on a real 8-bit micro I'd recommend setting this back to 40;
 * it does, however, eventually get there */
byte MAX = 70;

/* note on types: 2^32 is a 10-digit number,
 * so the digit sum of an ulong is guaranteed
 * to be <= 90 */
proc nonrec digitsum(ulong n) byte:
    byte sum;
    sum := 0;
    while n /= 0 do
        sum := sum + make(n % 10, byte);
        n := n / 10
    od;
    sum
corp

proc nonrec a131382(ulong n) ulong:
    ulong m;
    m := 1;
    while digitsum(m * n) /= n do
        m := m + 1
    od;
    m
corp

proc nonrec main() void:
    byte n;
    for n from 1 upto MAX do
        write(a131382(n):9);
        if (n & 7) = 0 then writeln() fi
    od
corp
Output:
        1        1        1        1        1        1        1        1
        1       19       19        4       19       19       13       28
       28       11       46      199       19      109       73       37
      199       73       37      271      172     1333      289      559
     1303      847     1657      833     1027     1576     1282    17497
     4339     2119     2323    10909    11111    12826    14617    14581
    16102   199999    17449    38269    56413    37037  1108909   142498
   103507   154981   150661  1333333   163918   322579   315873   937342
  1076923  1030303   880597  1469116  1157971 12842857

F#[edit]

// Minimum multiple of m where digital sum equals m. Nigel Galloway: January 31st., 2022
let SoD n=let rec SoD n=function 0L->int n |g->SoD(n+g%10L)(g/10L) in SoD 0L n
let A131382(g:int)=let rec fN i=match SoD(i*int64(g)) with
                                 n when n=g -> i
                                |n when n>g -> fN (i+1L)
                                |n -> fN (i+(int64(ceil(float(g-n)/float n))))
                   fN ((((pown 10L (g/9))-1L)+int64(g%9)*(pown 10L (g/9)))/int64 g)
Seq.initInfinite((+)1>>A131382)|>Seq.take 70|>Seq.chunkBySize 10|>Seq.iter(fun n->n|>Seq.iter(printf "%13d "); printfn "")
Output:
            1             1             1             1             1             1             1             1             1            19
           19             4            19            19            13            28            28            11            46           199
           19           109            73            37           199            73            37           271           172          1333
          289           559          1303           847          1657           833          1027          1576          1282         17497
         4339          2119          2323         10909         11111         12826         14617         14581         16102        199999
        17449         38269         56413         37037       1108909        142498        103507        154981        150661       1333333
       163918        322579        315873        937342       1076923       1030303        880597       1469116       1157971      12842857

FOCAL[edit]

01.10 F N=1,40;D 2
01.20 Q

02.10 S M=0
02.20 S M=M+1
02.30 S D=N*M
02.40 D 3
02.50 I (N-S)2.2,2.6,2.2
02.60 T "N",%2,N," M",%6,M,!

03.10 S S=0
03.20 S E=FITR(D/10)
03.30 S S=S+(D-E*10)
03.40 S D=E
03.50 I (-D)3.2
Output:
N=  1 M=      1
N=  2 M=      1
N=  3 M=      1
N=  4 M=      1
N=  5 M=      1
N=  6 M=      1
N=  7 M=      1
N=  8 M=      1
N=  9 M=      1
N= 10 M=     19
N= 11 M=     19
N= 12 M=      4
N= 13 M=     19
N= 14 M=     19
N= 15 M=     13
N= 16 M=     28
N= 17 M=     28
N= 18 M=     11
N= 19 M=     46
N= 20 M=    199
N= 21 M=     19
N= 22 M=    109
N= 23 M=     73
N= 24 M=     37
N= 25 M=    199
N= 26 M=     73
N= 27 M=     37
N= 28 M=    271
N= 29 M=    172
N= 30 M=   1333
N= 31 M=    289
N= 32 M=    559
N= 33 M=   1303
N= 34 M=    847
N= 35 M=   1657
N= 36 M=    833
N= 37 M=   1027
N= 38 M=   1576
N= 39 M=   1282
N= 40 M=  17497

Forth[edit]

Works with: Gforth
: digit-sum ( u -- u )
  dup 10 < if exit then
  10 /mod recurse + ;

: main
  1+ 1 do
    0
    begin
      1+ dup i * digit-sum i =
    until
    8 .r i 10 mod 0= if cr else space then
  loop ;

70 main
bye
Output:
       1        1        1        1        1        1        1        1        1       19
      19        4       19       19       13       28       28       11       46      199
      19      109       73       37      199       73       37      271      172     1333
     289      559     1303      847     1657      833     1027     1576     1282    17497
    4339     2119     2323    10909    11111    12826    14617    14581    16102   199999
   17449    38269    56413    37037  1108909   142498   103507   154981   150661  1333333
  163918   322579   315873   937342  1076923  1030303   880597  1469116  1157971 12842857

Go[edit]

Library: Go-rcu
package main

import "rcu"

func main() {
    var res []int
    for n := 1; n <= 70; n++ {
        m := 1
        for rcu.DigitSum(m*n, 10) != n {
            m++
        }
        res = append(res, m)
    }
    rcu.PrintTable(res, 7, 10, true)
}
Output:
         1          1          1          1          1          1          1 
         1          1         19         19          4         19         19 
        13         28         28         11         46        199         19 
       109         73         37        199         73         37        271 
       172      1,333        289        559      1,303        847      1,657 
       833      1,027      1,576      1,282     17,497      4,339      2,119 
     2,323     10,909     11,111     12,826     14,617     14,581     16,102 
   199,999     17,449     38,269     56,413     37,037  1,108,909    142,498 
   103,507    154,981    150,661  1,333,333    163,918    322,579    315,873 
   937,342  1,076,923  1,030,303    880,597  1,469,116  1,157,971 12,842,857 

Haskell[edit]

import Data.Bifunctor (first)
import Data.List (elemIndex, intercalate, transpose)
import Data.List.Split (chunksOf)
import Data.Maybe (fromJust)
import Text.Printf (printf)

------------------------- A131382 ------------------------

a131382 :: [Int]
a131382 =
  fromJust . (elemIndex <*> productDigitSums)
    <$> [1 ..]

productDigitSums :: Int -> [Int]
productDigitSums n = digitSum . (n *) <$> [0 ..]

--------------------------- TEST -------------------------
main :: IO ()
main =
  (putStrLn . table " ") $
    chunksOf 10 $ show <$> take 40 a131382

------------------------- GENERIC ------------------------
digitSum :: Int -> Int
digitSum 0 = 0
digitSum n = uncurry (+) (first digitSum $ quotRem n 10)

table :: String -> [[String]] -> String
table gap rows =
  let ws = maximum . fmap length <$> transpose rows
      pw = printf . flip intercalate ["%", "s"] . show
   in unlines $ intercalate gap . zipWith pw ws <$> rows
Output:
  1   1    1   1    1   1    1    1    1    19
 19   4   19  19   13  28   28   11   46   199
 19 109   73  37  199  73   37  271  172  1333
289 559 1303 847 1657 833 1027 1576 1282 17497

J[edit]

Implementation:

findfirst=: {{
  ($:@((+1+i.@+:)@#)@[`(+&{. I.)@.(1 e. ]) u) ,1
}}

A131382=: {{y&{{x = sumdigits x*y}} findfirst}}"0

sumdigits=: +/@|:@(10&#.inv)

Task example:

   A131382 1+i.4 10
  1   1    1   1    1   1    1    1    1    19
 19   4   19  19   13  28   28   11   46   199
 19 109   73  37  199  73   37  271  172  1333
289 559 1303 847 1657 833 1027 1576 1282 17497

Stretch example:

   A131382 41+i.3 10
  4339   2119   2323  10909   11111   12826  14617   14581   16102   199999
 17449  38269  56413  37037 1108909  142498 103507  154981  150661  1333333
163918 322579 315873 937342 1076923 1030303 880597 1469116 1157971 12842857

Julia[edit]

minproddigsum(n) = findfirst(i -> sum(digits(n * i)) == n, 1:typemax(Int32))

for j in 1:70
    print(lpad(minproddigsum(j), 10), j % 7 == 0 ? "\n" : "")
end
Output:
         1         1         1         1         1         1         1
         1         1        19        19         4        19        19
        13        28        28        11        46       199        19
       109        73        37       199        73        37       271
       172      1333       289       559      1303       847      1657
       833      1027      1576      1282     17497      4339      2119
      2323     10909     11111     12826     14617     14581     16102
    199999     17449     38269     56413     37037   1108909    142498
    103507    154981    150661   1333333    163918    322579    315873
    937342   1076923   1030303    880597   1469116   1157971  12842857

MAD[edit]

            NORMAL MODE IS INTEGER
            VECTOR VALUES FMT = $2HA(,I2,4H) = ,I8*$
            
            THROUGH NUMBER, FOR N = 1, 1, N.G.70
MULT        THROUGH MULT, FOR M = 1, 1, N.E.DSUM.(M*N)
NUMBER      PRINT FORMAT FMT, N, M
            
            INTERNAL FUNCTION(X)
            ENTRY TO DSUM.
            SUM = 0
            V = X
DIGIT       WHENEVER V.E.0, FUNCTION RETURN SUM
            W = V/10
            SUM = SUM + V - W*10
            V = W
            TRANSFER TO DIGIT
            END OF FUNCTION
            END OF PROGRAM
Output:
A( 1) =        1
A( 2) =        1
A( 3) =        1
A( 4) =        1
A( 5) =        1
A( 6) =        1
A( 7) =        1
A( 8) =        1
A( 9) =        1
A(10) =       19
A(11) =       19
A(12) =        4
A(13) =       19
A(14) =       19
A(15) =       13
A(16) =       28
A(17) =       28
A(18) =       11
A(19) =       46
A(20) =      199
A(21) =       19
A(22) =      109
A(23) =       73
A(24) =       37
A(25) =      199
A(26) =       73
A(27) =       37
A(28) =      271
A(29) =      172
A(30) =     1333
A(31) =      289
A(32) =      559
A(33) =     1303
A(34) =      847
A(35) =     1657
A(36) =      833
A(37) =     1027
A(38) =     1576
A(39) =     1282
A(40) =    17497
A(41) =     4339
A(42) =     2119
A(43) =     2323
A(44) =    10909
A(45) =    11111
A(46) =    12826
A(47) =    14617
A(48) =    14581
A(49) =    16102
A(50) =   199999
A(51) =    17449
A(52) =    38269
A(53) =    56413
A(54) =    37037
A(55) =  1108909
A(56) =   142498
A(57) =   103507
A(58) =   154981
A(59) =   150661
A(60) =  1333333
A(61) =   163918
A(62) =   322579
A(63) =   315873
A(64) =   937342
A(65) =  1076923
A(66) =  1030303
A(67) =   880597
A(68) =  1469116
A(69) =  1157971
A(70) = 12842857

Pascal[edit]

Free Pascal[edit]

over strechted limit to 110. Constructing minimal start number with sum of digits = m -> k+9+9+9+9+9+9
Break up in parts of 4 digits.Could be more optimized.

program m_by_n_sumofdgts_m;
//Like https://oeis.org/A131382/b131382.txt
{$IFDEF FPC} {$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$ENDIF}
uses
  sysutils;
const
   BASE = 10;
   BASE4 = BASE*BASE*BASE*BASE;
   MAXDGTSUM4 = 4*(BASE-1);
var
  {$ALIGN 32}
  SoD: array[0..BASE4-1] of byte;
  {$ALIGN 32}
  DtgBase4 :array[0..7] of Uint32;
  DtgPartSums :array[0..7] of Uint32;
  DgtSumBefore :array[0..7] of Uint32;

  
procedure Init_SoD;
var
  d0,d1,i,j : NativeInt;
begin
  i := 0;
  For d1 := 0 to BASE-1 do
    For d0 := 0 to BASE-1 do
      begin SoD[i]:= d1+d0;inc(i); end;
 
  j := Base*Base;
  For i := 1 to Base*Base-1 do
    For d1 := 0 to BASE-1 do
      For d0 := 0 to BASE-1 do
      begin
        SoD[j] := SoD[i]+d1+d0;
        inc(j);
      end;
end;
 
procedure OutDgt;
var
   i : integer;
begin
  for i := 5 downto 0 do
    write(DtgBase4[i]:4);
  writeln;
  for i := 5 downto 0 do
    write(DtgPartSums[i]:4);
  writeln;
  for i := 5 downto 0 do
    write(DgtSumBefore[i]:4);
  writeln;
end;
 
procedure InitDigitSums(m:NativeUint);
var
  n,i,s: NativeUint;
begin
  //constructing minimal number with sum of digits = m ;k+9+9+9+9+9+9
  //21 -> 299
  n := m;
  if n>BASE then
  begin
    i := 1;
    while n>BASE-1 do
    begin
      i *= BASE;
      dec(n,BASE-1);
    end;
    n := i*(n+1)-1;
    //make n multiple of m
    n := (n div m)*m;
    //m ending in 0
    i := m;
    while i mod BASE = 0 do
    begin
      n *= BASE;
      i := i div BASE;
    end;
  end;
  
  For i := 0 to 4 do
  begin
    s := n MOD BASE4;
    DtgBase4[i] := s;
    DtgPartSums[i] := SoD[s];
    n := (n-s) DIV BASE4;
  end;
 
  s := 0;
  For i := 3 downto 0 do
  begin
    s += DtgPartSums[i+1];
    DgtSumBefore[i]:= s;
  end;
end;

 
function CorrectSums(sum:NativeUint):NativeUint;
var
i,q,carry : NativeInt;
begin
  i := 0;
  q := sum MOD Base4;
  sum := sum DIV Base4;  
  result := q; 
  
  DtgBase4[i] := q;
  DtgPartSums[i] := SoD[q];    
  
  carry := 0;
  repeat 
    inc(i);  
    q := sum MOD Base4+DtgBase4[i]+carry;  
    sum := sum DIV Base4;  
    carry := 0;
    if q >= BASE4 then 
    begin
      carry := 1;
      q -= BASE4;
    end;
    DtgBase4[i]:= q;
    DtgPartSums[i] := SoD[q];    
  until (sum =0) AND( carry = 0);

  sum := 0;
  For i := 3 downto 0 do
  begin
    sum += DtgPartSums[i+1];
    DgtSumBefore[i]:= sum;
  end;
end;

function TakeJump(dgtSum,m:NativeUint):NativeUint;
var
  n,i,j,carry : nativeInt;
begin
  i := dgtsum div MAXDGTSUM4-1;
  n := 0;
  j := 1;
  for i := i downto 0 do
  Begin
    n:= n*BASE4+DtgBase4[i];
    j:= j*BASE4;
  end;  
  n := ((j-n) DIV m)*m;
//  writeln(n:10,DtgBase4[i]:10);
  i := 0;
  carry := 0;
  repeat
    j := DtgBase4[i]+ n mod BASE4 +carry;
    n := n div BASE4;
    carry := 0;
    IF j >=BASE4 then
    begin
      j -= BASE4;
      carry := 1;
    end;
    DtgBase4[i] := j;
    DtgPartSums[i]:= SoD[j];
    inc(i);
  until (n= 0) AND (carry=0);
  j := 0;
  For i := 3 downto 0 do
  begin
    j += DtgPartSums[i+1];
    DgtSumBefore[i]:= j;
  end;  
  result := DtgBase4[0];
end; 

procedure CalcN(m:NativeUint);
var
  dgtsum,sum: NativeInt;
begin
  InitDigitSums(m);
  
  sum := DtgBase4[0];
  dgtSum:= m-DgtSumBefore[0];
  //  while dgtsum+SoD[sum] <> m do
  while dgtsum<>SoD[sum] do
  begin
    inc(sum,m);  
    if sum >= BASE4 then
    begin
      sum := CorrectSums(sum);
      dgtSum:= m-DgtSumBefore[0];
      if dgtSum > MAXDGTSUM4 then
      begin 
        sum := TakeJump(dgtSum,m);   
        dgtSum:= m-DgtSumBefore[0];        
      end;  
    end;  
  end;
  DtgBase4[0] := sum;  
end;
 
var
  T0:INt64;
  i : NativeInt;
  m,n: NativeUint;
Begin
  T0 := GetTickCount64;
  Init_SoD;
  for m := 1 to 70 do
  begin
    CalcN(m);
    //Check sum of digits
    n := SoD[DtgBase4[4]];
    For i := 3 downto 0 do
      n += SoD[DtgBase4[i]];
    If n<>m then
    begin
      writeln('ERROR at ',m);
      HALT(-1);
    end;       
       
    n := DtgBase4[4];
    For i := 3 downto 0 do
      n := n*BASE4+DtgBase4[i];
    write(n DIV m :15); 
    if m mod 10 = 0 then
      writeln;
  end;
  writeln;
  writeln('Total runtime  ',GetTickCount64-T0,' ms');
  {$IFDEF WINDOWS} readln{$ENDIF}
end.
@TIO.RUN:
Real time: 36.660 s CPU share: 99.48 %
              1              1              1              1              1              1              1              1              1             19
             19              4             19             19             13             28             28             11             46            199
             19            109             73             37            199             73             37            271            172           1333
            289            559           1303            847           1657            833           1027           1576           1282          17497
           4339           2119           2323          10909          11111          12826          14617          14581          16102         199999
          17449          38269          56413          37037        1108909         142498         103507         154981         150661        1333333
         163918         322579         315873         937342        1076923        1030303         880597        1469116        1157971       12842857

Total runtime  4 ms
..100
        4084507        5555554        6849163       37027027       13333333       11710513       11686987       11525641       12656962      374999986
       12345679       60852439       72168553       82142857      117647047       93022093      103445977      227272726      112247191     1111111111
      658010989      652173913      731172043      849893617     2947368421     2083333228     1030927834     3969377551    11101010101   199999999999

Total runtime  642 ms
..110 
    28900990099     5881372549     6796115533    18173076922    27619047619    18679245283    18691495327    36111111111    44862385321  1090909090909

Total runtime  36486 ms
@home
 111         79009009009  17882 ms
 112         80356249999  17906 ms
 113         78761061946  17910 ms
 114         87710526307  17916 ms
 115        426086956513  18022 ms
 116        258620688793  18033 ms
 117        255547008547  18035 ms
 118        414406779661  18039 ms
 119        411756302521  18040 ms
 120       4999999999999  26838 ms

 121       2809909090909  27273 ms
 122        811475409754  27290 ms
 123        730081300813  27291 ms
 124       2419193548387  27328 ms
 125       5599999999999  29177 ms
 126       2380873015873  29181 ms
 127       3148818897637  29183 ms
 128       5468749999921  29328 ms
 129       5348836434031  29334 ms
 130      46076923076923  32383 ms

 131       6106793893129  32386 ms
 132      28030303030303  32559 ms
 133       6766917293233  32560 ms
 134      22388058880597  32577 ms
 135      37037037037037  32665 ms
 136      44044117647058  32712 ms
 137      56919700729927  32774 ms
 138      36231884057971  32775 ms
 139      49568345323741  32775 ms
 140     571427857142857  58364 ms

 141      63822694964539  58366 ms
 142     140140838028169  58378 ms
 143     391606993006993  58606 ms
 144     277777777777777  58698 ms
 145     482751724137931  58929 ms
 146     471917801369863  58959 ms
 147     401360544217687  58961 ms
 148    1081081081081081  59207 ms
 149     536912751677851  59213 ms
 150   13333333333333333  728689 ms

Perl[edit]

#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Minimum_multiple_of_m_where_digital_sum_equals_m
use warnings;
use ntheory qw( sumdigits );

my @answers = map
  {
  my $m = 1;
  $m++ until sumdigits($m*$_) == $_;
  $m;
  } 1 .. 70;
print "@answers\n\n" =~ s/.{65}\K /\n/gr;
Output:
1 1 1 1 1 1 1 1 1 19 19 4 19 19 13 28 28 11 46 199 19 109 73 37 199
73 37 271 172 1333 289 559 1303 847 1657 833 1027 1576 1282 17497
4339 2119 2323 10909 11111 12826 14617 14581 16102 199999 17449 38269
56413 37037 1108909 142498 103507 154981 150661 1333333 163918 322579
315873 937342 1076923 1030303 880597 1469116 1157971 12842857

Phix[edit]

Translation of: XPL0
with javascript_semantics
integer c = 0, n = 1
while c<70 do
    integer m = 1
    while true do
        integer nm = n*m, t = 0
        while nm do
            t += remainder(nm,10)
            nm = floor(nm/10)
        end while
        if t=n then exit end if
        m += 1
    end while
    c += 1
    printf(1,"%-8d%s",{m,iff(remainder(c,10)=0?"\n":"")})
    n += 1
end while
Output:
1       1       1       1       1       1       1       1       1       19
19      4       19      19      13      28      28      11      46      199
19      109     73      37      199     73      37      271     172     1333
289     559     1303    847     1657    833     1027    1576    1282    17497
4339    2119    2323    10909   11111   12826   14617   14581   16102   199999
17449   38269   56413   37037   1108909 142498  103507  154981  150661  1333333
163918  322579  315873  937342  1076923 1030303 880597  1469116 1157971 12842857

much faster[edit]

(Not that the above is particularly slow, but you certainly wouldn't want to push it much past 70)

Library: Phix/online

You can run this online here.

-- demo\rosetta\mmnn.exw
with javascript_semantics
include mpfr.e -- (for the final divide only)
forward function rackup5(string digits, integer l)
forward function rackup11(string digits, integer l, bool r5=false)
forward function nextup11(string digits, integer l)

function mmnn(integer n)
    --
    -- minimum multiple of n that sums to n
    --
    -- 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 a decrementable and an incrementable digit, 
    -- moving the former to the end(ish), or if no "" prepend a 1, eg
    -- 5 -> 14 -> 23 -> 32 -> 41 -> 50 -> 104 -> 113 -> 122 -> 131 ->
    -- 140 -> 203 .. 230 -> 302 .. 500 -> 1004 .. 10004, etc.
    -- Another example, this time summing to 14 (the above was to 5!):
    -- 59 -> 68 .. 95 -> 149 .. 194 -> 239 .. 293 -> 329 .. 392 ->
    -- 419 .. 491 -> 509 .. 590 -> 608 .. 680 -> 707 .. 770 -> 806
    -- .. 860 -> 905 .. 950 -> 1049, etc.
    -- in that last case, what we actually need to do is decrement the
    -- 5 (->940), then reverse the whole thing, and then prepend a 1,
    -- likewise if we increment a middle digit, dec then reverse(rest).
    -- In the extreme case you would want 1 -> 10 -> 100 -> 1000, etc,
    -- although since 1 passes muster we would never actually do that.
    --
    if n=0 then return "0" end if -- avoid remainder(x,0), and tz=inf

    integer l = ceil(n/9)-1,        -- this many trailing 9s...
            k = n-9*l+'0',          -- ...and this first digit
            n0 = n
    string digits = k&repeat('9',l) -- eg n=14 -> "59"
    l += 1

    -- optimising for trailing zeroes makes a truly *huge* difference
    while remainder(n0,10)=0 do
        n0 /= 10
        digits &= '0' -- (these be static, aka forever past "l")
    end while

    bool r5 = remainder(n0,5)=0,    -- ten-fold improvement on some
         r11 = remainder(n0,11)=0   -- took 165 from 1min 25s to 6s,
                                    -- (even faster now r5 working)
    if r5 then {digits,l} = rackup5(digits,l) end if
    if r11 then {digits,l} = rackup11(digits,l,r5) end if

    atom t1 = time()+1
    while true do

        -- calculate remainder(digits,n) digit-wise; faster than mpz
        integer rem = 0, rn = 1
        for i=1 to length(digits) do -- (nb not "l")
            k = digits[-i]-'0'
            rem = remainder(rem+rn*k,n)
            rn = remainder(rn*10,n)
        end for
        if rem=0 then exit end if
        
        -- (only triggers on eg 202, 222, 271 and higher)
        if time()>t1 then t1 = time()+1; ?{digits,n} end if

        if not r11 then

            integer d = 0  -- decrementable digit position
            for i=l to 1 by -1 do
                if d=0 and digits[i]>'0' then
                    d = i
                elsif d and digits[i]<'9' then
                    digits[d] -= 1
                    digits[i] += 1
                    digits[i+1..l] = reverse(digits[i+1..l])
                    exit
                elsif i=1 then
                    -- (so digits[1]=9 or no decrementable)
                    digits[d] -= 1
                    digits[1..l] = reverse(digits[1..l])
                    digits = prepend(digits,'1')
                    l += 1
                    exit
                end if
            end for

        else
            -- Same as above but with additional rules
            {digits,l} = nextup11(digits,l)

        end if
    end while
    mpz z = mpz_init(digits)
    assert(mpz_fdiv_q_ui(z, z, n)=0)
    string res = mpz_get_str(z)
    return res
end function

function rackup5(string digits, integer l)
    --
    -- 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.
    --
    integer d = digits[l]
    if d!='5' then
        assert(d='9')               -- eg 299 -> 295    ie -4
        digits[l] = '5'             -- or 799 -> 795    ""
        d = digits[1]
        if d<='5' then
            digits[1] = d+4         -- eg 295 -> 695    == +4
        else
            digits[1] = '9'
            digits = d-5 & digits   -- eg 795 -> 2995   ie +2+2
            l += 1
        end if
    end if
    return {digits,l-1}
end function

function swarpp11(string s)
    --
    -- special pairwise swapping/reversal for divisible by 11 numbers, eg:
    --
    --  | 7654321 | , | 653421 | , | 54321 | , | 4321 | , | 321 | , | 21 | , | 1 |
    --  > 1234567 <   > 213465 <   > 12345 <   > 2143 <   > 123 <   > 21 <   > 1 <
    --
    -- (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.)
    --
    integer l = length(s), i = 1
    if odd(l) then return reverse(s) end if
    while l-i>=3 do
        integer si = s[i], j=l-1
        s[i] = s[j]
        s[j] = si   
        i += 1
        si = s[i]
        s[i] = s[l]
        s[l] = si
        i += 1
        l -= 2
    end while
    return s
end function

function nextup11(string digits, integer l)
    --
    -- 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)
    --
    integer d,          -- a digit
            dd = 0,     -- decrementable digit position (scratch)
            ddd,        -- decrementable digit value       """
            td = 0,     -- total decrementable digits
            ti = 0,     -- total incrementable digits
            od = 0,     -- decrementable odd digit position
            ed = 0,     -- decrementable even digit position
            dod = 0,    -- decrementable odd digit value
            ded = 0,    -- decrementable even digit value
            tod = 0,    -- total odd decrementable digits
            ted = 0,    -- total even decrementable digits
            iod = 0,    -- total odd incrementable digits
            ied = 0     -- total even incrementable digits

    bool bIncAbleFound = false,
         bTransferable11
    string wasdig = digits, transdigits

    for i=l to 1 by -1 do
        d = digits[i]-'0'
        if odd(i) then
            tod += d
            iod += 9-d
            if od=0 and d>0 then
                od = i
                dod = d
            else
                dd = od
                ddd = dod
                bIncAbleFound = d<9 and dd
            end if
            bTransferable11 = iod>=11 and ted>=11
        else
            ted += d
            ied += 9-d
            if ed=0 and d>0 then
                ed = i
                ded = d
            else
                dd = ed
                ddd = ded
                bIncAbleFound = d<9 and dd
            end if
            bTransferable11 = ied>=11 and tod>=11
        end if
        if bTransferable11 then
            {od,ed} = iff(odd(l)=odd(i)?{l,l-1}:{l-1,l})
            {ti,td} = {11,11}
            transdigits = digits
            integer t
            while ti do
                assert(od>0)
                t = min('9'-digits[od],ti)
                ti -= t
                transdigits[od] += t
                od -= 2
            end while
            while td do
                assert(ed>0)
                t = min(digits[ed]-'0',td)
                td -= t
                transdigits[ed] -= t
                ed -= 2
            end while
            transdigits[i+1..l] = swarpp11(transdigits[i+1..l])                 
            if transdigits<=digits then
                bTransferable11 = false
            elsif not bIncAbleFound then
                digits = transdigits
                exit
            end if
        end if              
        if bIncAbleFound then
            digits[dd] = ddd-1+'0'
            digits[i] = d+'1'
            digits[i+1..l] = swarpp11(digits[i+1..l])
            if bTransferable11 and transdigits<digits then
                digits = transdigits
            end if
            exit
        elsif i=1 then
            -- (so digits[1]=9 or no o/e decrementable)
            {dd,ddd} = iff(odd(l)?{ed,ded}:{od,dod})
            digits[dd] = ddd-1+'0'
            digits[1..l] = reverse(digits[1..l])
            digits = prepend(digits,'1')
            l += 1
            exit
        end if
    end for
    return {digits,l}
end function

function rackup11(string digits, integer l, bool r5=false)
    --
    -- Converts digits to next number divisible by 11, while
    -- maintaining the exact same sum of digits unaltered, eg
    -- 29 -> 209, 499 -> 2299, 6999 -> 42999, 89999 -> 449999,
    -- 1999999 -> 6499999, 39999999 -> 66999999, 599999999 ->
    -- 869999999, 7999999999 -> 8899999999, 99999999999 ->
    -- 1098999999999, 2999999999999 -> 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.
    --
    if r5 then l += 1 end if
    integer od = remainder(sum(sq_sub(extract(digits,tagset(l,1,2)),'0')),11),
            ed = remainder(sum(sq_sub(extract(digits,tagset(l,2,2)),'0')),11)
    assert(od+ed=0 or od+ed=11)
    if r5 then l -= 1 end if

    if od!=ed then
        --
        -- 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>9) for odd-od busted.
        --
        integer d,  -- a digit
                woed = ed, weed = ed, -- work vars for odd+ed, even-ed
                wood = od, weod = od, -- work vars for odd-od, even+od
                loed = l -- new value for l should we switch
        string odd_ed = digits -- (odd-od done in digits direct)
        for i=1 to l do
            if odd(i) then
                d = min('9'-odd_ed[i],woed)     -- add ed to odd digits
                odd_ed[i] += d
                woed -= d
                d = min(digits[i]-'0',wood)     -- subtract od from ""
                digits[i] -= d
                wood -= d
            else
                d = min(odd_ed[i]-'0',weed)     -- subtract ed from even
                odd_ed[i] -= d
                weed -= d
                d = min('9'-digits[i],weod)     -- add od to even digits
                digits[i] += d
                weod -= d
            end if
        end for
        if woed or weed then
            odd_ed = weed+'0' & odd_ed
            loed += 1
            if woed then
                odd_ed = woed+'0' & odd_ed
                loed += 1
            end if
        end if
        if wood or weod then
            digits = weod+'0' & digits
            l += 1
            if wood then
                digits = wood+'0' & digits
                l += 1
            end if
        end if
        if loed<l
        or weod>9 
        or wood>9 
        or (loed=l and odd_ed<digits) then
            digits = odd_ed
            l = loed
        end if
    end if
    return {digits,l}
end function

atom t0 = time()
for n=1 to 200 do -- 0.7s
--for n=1 to 274 do -- 12.8s, but mmnn(275) takes 2 minutes and 25s
--for n=1 to 369 do -- 2 minutes 31s, but I gave up on 370
--for n=1 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
    if remainder(n,iff(n<=100?10:5))=1 then printf(1,"\n%3d:",n) end if
    printf(1," %-11s",{mmnn(n)})
--end if
end for
printf(1,"\n1,000,000: %s\n",{shorten(mmnn(1e6))}) -- (0.0s)
?elapsed(time()-t0)
Output:
  1: 1           1           1           1           1           1           1           1           1           19
 11: 19          4           19          19          13          28          28          11          46          199
 21: 19          109         73          37          199         73          37          271         172         1333
 31: 289         559         1303        847         1657        833         1027        1576        1282        17497
 41: 4339        2119        2323        10909       11111       12826       14617       14581       16102       199999
 51: 17449       38269       56413       37037       1108909     142498      103507      154981      150661      1333333
 61: 163918      322579      315873      937342      1076923     1030303     880597      1469116     1157971     12842857
 71: 4084507     5555554     6849163     37027027    13333333    11710513    11686987    11525641    12656962    374999986
 81: 12345679    60852439    72168553    82142857    117647047   93022093    103445977   227272726   112247191   1111111111
 91: 658010989   652173913   731172043   849893617   2947368421  2083333228  1030927834  3969377551  11101010101 199999999999
101: 28900990099 5881372549  6796115533  18173076922 27619047619
106: 18679245283 18691495327 36111111111 44862385321 1090909090909
111: 79009009009 80356249999 78761061946 87710526307 426086956513
116: 258620688793 255547008547 414406779661 411756302521 4999999999999
121: 2809909090909 811475409754 730081300813 2419193548387 5599999999999
126: 2380873015873 3148818897637 5468749999921 5348836434031 46076923076923
131: 6106793893129 28030303030303 6766917293233 22388058880597 37037037037037
136: 44044117647058 56919700729927 36231884057971 49568345323741 571427857142857
141: 63822694964539 140140838028169 391606993006993 277777777777777 482751724137931
146: 471917801369863 401360544217687 1081081081081081 536912751677851 13333333333333333
151: 1258278145629139 3217105263157894 1307189477124183 3830512987012987 5161290322516129
156: 4423076923076923 3821656050955414 6202531582278481 5660371069181761 124999999999999993
161: 12415527950310559 12345679012345679 18404907975398773 48773170731707317 430303030303030303
166: 48186144578313253 53233532874251497 119041666666666666 59165680473372781 588235235294117647
171: 169590643216374269 290691860465116279 289017341039884393 344827586206895977 1142857142857142857
176: 511363636363636363 507903954802259887 1123594938202247191 1061452513966424581 11111111111111111111
181: 2154143646408839779 3845989010989010989 3278142075956284153 5380434239130434782 37027027027027027027
186: 9677419354838172043 5347053475935828877 20744680845744680851 20105291005291005291 157894731578947368421
191: 15706806282722513089 41666666666666666614 36269424870466321243 46391752577319535567 153845641025641025641
196: 147959183673469382653 101517766497461928934 101010101010101010101 201005025125628040201 19999999999999999999999
1,000,000: 19999999999999999999...99999999999999999999 (111,112 digits)
"0.7s"

As shown commented out, it will carry on a fair bit further, but I gave up on 275 370, and it looks to me like some quite wierd patterns are starting to appear 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.

201: 293532338308407960199 1900990099009900990099 438374384235960591133 490195588235294117647 1902439024390243902439
206: 1407766990291213592233 966183574879227052657 2836538461538461538461 10526315784688995215311 23809047619047619047619
211: 2843601895260663507109 4716933490566037735849 4225305164318779342723 9345794387803738317757 27441855813953488372093
216: 18518518518518518518518 18433179262672811059447 27518348623848623853211 27397210045662100456621 1090909090909090909090909
221: 36199049773710407239819 259009009009009009009009 40358744394618834080713 223169642857142857142812 311111111111111111111111
226: 216371681415929203539823 220264317180615859030837 307017543859649122368421 301310043668117903930131 3043434782608695652173913
231: 1904329004329004329004329 1293103448275861637931034 429184549351931330472103 1282047008547008547008547 2978723404255319148893617
236: 2923728813135593220338983 2531223628270042194092827 3361302521008403361302521 3682004184100418410041841 41666666666666666666666662
241: 4149377593360995846473029 19421487603305785123553719 4115226337448559670781893 20491803278688483606557377 32648979591836734693877551
246: 35731300813008130081300813 32388258704048582995951417 80604838306451612903225806 35742971887550200803212851 1999999999999999999999999999
251: 79641434262549800796812749 119047619047619047619047619 260830039525691699604743083 236220472047244094488188937 352941176470196078431372549
256: 390624999999999999999960898 311284046688715953307392607 348837209301937984496124031 1081003861003861003861003861 11534576923076923076923076923
261: 766283524904210727969348659 1908014885496183206106870229 1520912547528517110266121673 2992424242424242424242424242 7546792452452830188679245283
266: 3007481203007518796992481203 3333333295880149812734082397 10820895485074626865671641791 7397769516728620817843866171 37037037037037037037037037037
271: 31690036900369003690036900369 25735294117647055147058823529 29263003663003663003663003663 29197007299270072992700729927 1126909090909090909090909090909
276: 36231880434782608695652173913 36101083032490974729238266787 107910071942446039568345323741 71684229390681003584229390681 1428571428571428571428571428571
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"

much simpler, to 1000[edit]

Uses dynamic programming, at least I think it does. Maintains a grid of digit sum against remainder in the form of the (final) digit that got us there first (so it's the smallest) along with a (parent) link to the chain of preceding digits. In effect, we are simply performing a breadth first search of unvisited nodes to get from {0,0} aka "" to {n,0} ie a digital sum of n with no remainder. The clever (ok, obvious if you prefer) maths bit is remainder(<parent's remainder>*10,n) when appending each individual digit.

While a fair bit slower on most individual numbers (esp under pwa/p2js) it hits far fewer bottlenecks such as that 275 above, and at least past 200 turns out to be quite a bit faster. However there is no equivalent trailing zero optimisation that I can see, and it caps out at 1e4 on 32 bit, 2e4 on 64 bit, for obvious reasons the square root of the hard limits of the above (assuming a number the code above doesn't pick a fight with).
Translation of the C++ code on A002998 but with the additional final divide for A131382 and significantly clearer imnsho.

with javascript_semantics
include mpfr.e -- (for the final divide only)
function mmnn(integer n)
    if n<=0 then return "0" end if -- (edge case)
    string digits = repeat(' ',n*(n+1)), res = "0"
    sequence parent = repeat(0,n*(n+1)), queue = {}
    integer dsum = 0, residue = 0, pdx = 0
    while true do -- (found or queue not empty at end of loop)
        for digit=0 to 9 do
            if dsum>n then exit end if
            if dsum=n and residue=0 then    -- success!!
                res[1] = '0'+digit
                while pdx do
                    res = digits[pdx] & res
                    pdx = parent[pdx]
                end while
                mpz z = mpz_init(res)
                assert(mpz_fdiv_q_ui(z, z, n)=0)
                res = mpz_get_str(z)
                return res
            end if
            integer drx = dsum*n+residue+1
            if digits[drx]=' ' then
                digits[drx] = '0'+digit
                parent[drx] = pdx
                queue = append(queue,{dsum,residue})
            end if
            dsum += 1
            residue = remainder(residue+1,n)
        end for
        if length(queue)=0 then return "FAIL" end if
        {dsum,residue} = queue[1]
                 queue = queue[2..$]
        pdx = dsum*n+residue+1
        residue = remainder(residue*10,n)   
    end while
    return "what???"
end function

puts(1,"")
atom t0 = time()
integer llen = 5
for n=1 to 200 do   -- 1.2s (15.4s under pwa/p2js)
--for n=1 to 274 do -- 3.1s
--for n=1 to 369 do -- 7.1s
--for n=1 to 500 do -- 19s
--for n=1 to 1000 do -- 2 mins 29s
    string res = mmnn(n)
    llen += length(res)
    bool bCR = iff(n<=101?remainder(n,10)=1:llen>118)
    if bCR then printf(1,"\n%3d:",n) llen = 5+length(res) end if
    printf(1," %-11s",{res})
--  printf(1,"%d %s\n",{n,mmnn(n)}) // Generate b-file for A131382 (1..1000)
end for
--printf(1,"%d %s\n",{1e3,mmnn(1e3)}) -- 0.6s
--printf(1,"%d %s\n",{1e4,mmnn(1e4)}) -- 1min 8s
--printf(1,"%d %s\n",{2e4,mmnn(2e4)}) -- crashes on 32 bit, 6 minutes and 18s on 64 bit
--printf(1,"%d %s\n",{1e6,mmnn(1e6)}) -- not a chance!
printf(1,"\n")
?elapsed(time()-t0)
Output:

Coincidentally taking exactly as long to get to 1000 as the above took to get to 369, as above with slightly different line breaks, plus

<snip>
995: 2010040201005025125628140703517587939698492462311557788944723618090452261306532663316582914572864321608040201
996: 1907630522088353413654618473895481927710843373493975903614457831325301204819277108433734939759036144578313253
997: 1003009027081243731193580742226579739217652958876629889669007021063189568706118355065195586760279839518555667
998: 2004008016032064128256513026052104208416833667234468937875751503006012024048096192384769539078156312625250501
999: 1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001
1000: 1999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
"2 minutes and 29s"

Prolog[edit]

Works with: SWI Prolog
main:-
    between(1, 40, N),
    min_mult_dsum(N, M),
    writef('%6r', [M]),
    (0 is N mod 10 -> nl ; true),
    fail.
main.

min_mult_dsum(N, M):-
    min_mult_dsum(N, 1, M).

min_mult_dsum(N, M, M):-
    P is M * N,
    digit_sum(P, N),
    !.
min_mult_dsum(N, K, M):-
    L is K + 1,
    min_mult_dsum(N, L, M).

digit_sum(N, Sum):-
    digit_sum(N, Sum, 0).

digit_sum(N, Sum, S1):-
    N < 10,
    !,
    Sum is S1 + N.
digit_sum(N, Sum, S1):-
    divmod(N, 10, M, Digit),
    S2 is S1 + Digit,
    digit_sum(M, Sum, S2).
Output:
     1     1     1     1     1     1     1     1     1    19
    19     4    19    19    13    28    28    11    46   199
    19   109    73    37   199    73    37   271   172  1333
   289   559  1303   847  1657   833  1027  1576  1282 17497

Python[edit]

'''A131382'''

from itertools import count, islice


# a131382 :: [Int]
def a131382():
    '''An infinite series of the terms of A131382'''
    return (
        elemIndex(x)(
            productDigitSums(x)
        ) for x in count(1)
    )


# productDigitSums :: Int -> [Int]
def productDigitSums(n):
    '''The sum of the decimal digits of n'''
    return (digitSum(n * x) for x in count(0))


# ------------------------- TEST -------------------------
# main :: IO ()
def main():
    '''First 40 terms of A131382'''

    print(
        table(10)([
            str(x) for x in islice(
                a131382(),
                40
            )
        ])
    )


# ----------------------- GENERIC ------------------------

# chunksOf :: Int -> [a] -> [[a]]
def chunksOf(n):
    '''A series of lists of length n, subdividing the
       contents of xs. Where the length of xs is not evenly
       divisible, the final list will be shorter than n.
    '''
    def go(xs):
        return (
            xs[i:n + i] for i in range(0, len(xs), n)
        ) if 0 < n else None
    return go


# digitSum :: Int -> Int
def digitSum(n):
    '''The sum of the digital digits of n.
    '''
    return sum(int(x) for x in list(str(n)))


# elemIndex :: a -> [a] -> (None | Int)
def elemIndex(x):
    '''Just the first index of x in xs,
       or None if no elements match.
    '''
    def go(xs):
        try:
            return next(
                i for i, v in enumerate(xs) if x == v
            )
        except StopIteration:
            return None
    return go


# table :: Int -> [String] -> String
def table(n):
    '''A list of strings formatted as
       right-justified rows of n columns.
    '''
    def go(xs):
        w = len(xs[-1])
        return '\n'.join(
            ' '.join(row) for row in chunksOf(n)([
                s.rjust(w, ' ') for s in xs
            ])
        )
    return go


# MAIN ---
if __name__ == '__main__':
    main()
Output:
    1     1     1     1     1     1     1     1     1    19
   19     4    19    19    13    28    28    11    46   199
   19   109    73    37   199    73    37   271   172  1333
  289   559  1303   847  1657   833  1027  1576  1282 17497

Raku[edit]

sub min-mult-dsum ($n) { (1..∞).first: (* × $n).comb.sum == $n }

say .fmt("%2d: ") ~ .&min-mult-dsum for flat 1..40, 41..70;
Output:
 1: 1
 2: 1
 3: 1
 4: 1
 5: 1
 6: 1
 7: 1
 8: 1
 9: 1
10: 19
11: 19
12: 4
13: 19
14: 19
15: 13
16: 28
17: 28
18: 11
19: 46
20: 199
21: 19
22: 109
23: 73
24: 37
25: 199
26: 73
27: 37
28: 271
29: 172
30: 1333
31: 289
32: 559
33: 1303
34: 847
35: 1657
36: 833
37: 1027
38: 1576
39: 1282
40: 17497
41: 4339
42: 2119
43: 2323
44: 10909
45: 11111
46: 12826
47: 14617
48: 14581
49: 16102
50: 199999
51: 17449
52: 38269
53: 56413
54: 37037
55: 1108909
56: 142498
57: 103507
58: 154981
59: 150661
60: 1333333
61: 163918
62: 322579
63: 315873
64: 937342
65: 1076923
66: 1030303
67: 880597
68: 1469116
69: 1157971
70: 12842857

Sidef[edit]

var e = Enumerator({|f|
    for n in (1..Inf) {

        var k = 0
        while (k.sumdigits != n) {
            k += n
        }

        f(k/n)
    }
})

var N = 60
var A = []

e.each {|v|
    A << v
    say A.splice.map { '%7s' % _ }.join(' ') if (A.len == 10)
    break if (--N <= 0)
}
Output:
      1       1       1       1       1       1       1       1       1      19
     19       4      19      19      13      28      28      11      46     199
     19     109      73      37     199      73      37     271     172    1333
    289     559    1303     847    1657     833    1027    1576    1282   17497
   4339    2119    2323   10909   11111   12826   14617   14581   16102  199999
  17449   38269   56413   37037 1108909  142498  103507  154981  150661 1333333

Swift[edit]

import Foundation

func digitSum(_ num: Int) -> Int {
    var sum = 0
    var n = num
    while n > 0 {
        sum += n % 10
        n /= 10
    }
    return sum
}

for n in 1...70 {
    for m in 1... {
        if digitSum(m * n) == n {
            print(String(format: "%8d", m), terminator: n % 10 == 0 ? "\n" : " ")
            break
        }
    }
}
Output:
       1        1        1        1        1        1        1        1        1       19
      19        4       19       19       13       28       28       11       46      199
      19      109       73       37      199       73       37      271      172     1333
     289      559     1303      847     1657      833     1027     1576     1282    17497
    4339     2119     2323    10909    11111    12826    14617    14581    16102   199999
   17449    38269    56413    37037  1108909   142498   103507   154981   150661  1333333
  163918   322579   315873   937342  1076923  1030303   880597  1469116  1157971 12842857

Wren[edit]

Library: Wren-math
Library: Wren-seq
Library: Wren-fmt
import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt

var res = []
for (n in 1..70) {
    var m = 1
    while (Int.digitSum(m * n) != n) m = m + 1
    res.add(m)
}
for (chunk in Lst.chunks(res, 10)) Fmt.print("$,10d", chunk)
Output:
         1          1          1          1          1          1          1          1          1         19
        19          4         19         19         13         28         28         11         46        199
        19        109         73         37        199         73         37        271        172      1,333
       289        559      1,303        847      1,657        833      1,027      1,576      1,282     17,497
     4,339      2,119      2,323     10,909     11,111     12,826     14,617     14,581     16,102    199,999
    17,449     38,269     56,413     37,037  1,108,909    142,498    103,507    154,981    150,661  1,333,333
   163,918    322,579    315,873    937,342  1,076,923  1,030,303    880,597  1,469,116  1,157,971 12,842,857

XPL0[edit]

func SumDigits(N);      \Return sum of digits in N
int  N, S;
[S:= 0;
while N do
    [N:= N/10;
    S:= S + rem(0);
    ];
return S;
];

int  C, N, M;
[C:= 0; N:= 1;
repeat  M:= 1;
        while SumDigits(N*M) # N do M:= M+1;
        IntOut(0, M);
        C:= C+1;
        if rem (C/10) then ChOut(0, 9\tab\) else CrLf(0);
        N:= N+1;
until   C >= 40+30;
]
Output:
1       1       1       1       1       1       1       1       1       19
19      4       19      19      13      28      28      11      46      199
19      109     73      37      199     73      37      271     172     1333
289     559     1303    847     1657    833     1027    1576    1282    17497
4339    2119    2323    10909   11111   12826   14617   14581   16102   199999
17449   38269   56413   37037   1108909 142498  103507  154981  150661  1333333
163918  322579  315873  937342  1076923 1030303 880597  1469116 1157971 12842857