Minimum multiple of m where digital sum equals m
Minimum multiple of m where digital sum equals m is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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
<lang algol68>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</lang>
- 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
<lang APL>{n←⍵ ⋄ (+∘1)⍣{n=+/10⊥⍣¯1⊢⍺×n}⊢0 } ¨ 7 10⍴⍳70</lang>
- 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
BASIC
BASIC256
<lang BASIC256>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</lang>
- Output:
Igual que la entrada de FreeBASIC.
FreeBASIC
<lang freebasic>#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 </lang>
- 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
<lang yabasic>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</lang>
- Output:
Igual que la entrada de FreeBASIC.
C
<lang c>#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;
}</lang>
- 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++
<lang cpp>#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;
}
}
}
}</lang>
- 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
<lang clu>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</lang>
- 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
<lang cobol> 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.</lang>
- 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
<lang cowgol>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;</lang>
- 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
<lang draco>/* 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</lang>
- 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#
<lang fsharp> // 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 "") </lang>
- 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
<lang focal>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</lang>
- 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
<lang forth>: 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</lang>
- 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
Haskell
<lang haskell>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</lang>
- 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
Implementation:
<lang J> findfirst=: Template:($:@((+1+i.@+:)@
A131382=: {{y&Template:X = sumdigits x*y findfirst}}"0
sumdigits=: +/@|:@(10&#.inv)</lang>
Task example: <lang J> 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</lang>
Stretch example: <lang J> 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</lang>
Julia
<lang julia>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
</lang>
- 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
<lang MAD> 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</lang>
- 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
Free Pascal
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.
<lang pascal>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.</lang>
- @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
<lang perl>#!/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;</lang>
- 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
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
(Not that the above is particularly slow, but you certainly wouldn't want to push it much past 70)
with javascript_semantics include mpfr.e -- (for the final divide only) 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 string digits = k&repeat('9',l) -- eg n=14 -> "59" l += 1 -- optimising for trailing zeroes makes a truly *huge* difference integer n0 = n while remainder(n0,10)=0 do n0 /= 10 digits &= '0' -- (these be static, aka forever past "l") end while bool r5 = remainder(n0,10)=5 -- not quite so much (maybe 30%) 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 if time()>t1 then t1 = time()+1; ?{digits,n} end if while true do -- (r5 optimisation at "end while") integer dd = 0, -- decrementable digit position ddd -- decrementable digit value bool bIncAbleFound = false for i=l to 1 by -1 do integer d = digits[i]-'0' if dd=0 and d>0 then dd = i ddd = d else bIncAbleFound = d<9 and dd end if if bIncAbleFound or i=1 then digits[dd] = ddd-1+'0' if bIncAbleFound then digits[i] = d+'1' digits[i+1..l] = reverse(digits[i+1..l]) else -- (i=1, so digits[1]=9 or no decrementable) digits[1..l] = reverse(digits[1..l]) digits = prepend(digits,'1') l += 1 end if exit end if end for if not r5 or find(digits[l],"05") then exit end if end while end while mpz z = mpz_init(digits) assert(mpz_fdiv_q_ui(z, z, n)=0) return mpz_get_str(z) end function atom t0 = time() for n=1 to 100 do -- 0.4s if remainder(n,10)=1 then printf(1,"\n%3d:",n) end if printf(1," %-11s",{mmnn(n)}) end for for n=101 to 164 do -- 0.7s, but mmnn(165) takes 1mins 25s --for n=101 to 274 do -- 1mins 50s (most from 165, gave up on 275) if remainder(n,5)=1 then printf(1,"\n%3d:",n) end if printf(1," %-11s",{mmnn(n)}) end for printf(1,"\n1,000,000: %s\n",{shorten(mmnn(1e6))}) -- (0.0s) ?elapsed(time()-t0) -- 1.1s
- 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 1,000,000: 19999999999999999999...99999999999999999999 (111,112 digits) "1.1s"
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.
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 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 "1 minute and 50s"
Prolog
<lang 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).</lang>
- 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
<lang python>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()</lang>
- 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
<lang perl6>sub min-mult-dsum ($n) { (1..∞).first: (* × $n).comb.sum == $n }
say .fmt("%2d: ") ~ .&min-mult-dsum for flat 1..40, 41..70;</lang>
- 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
Swift
<lang swift>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
}
}
}</lang>
- 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
<lang ecmascript>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)</lang>
- 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
<lang XPL0>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; ]</lang>
- 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