Minimum multiple of m where digital sum equals m: Difference between revisions
m (→much faster: mini tidy of final loop) |
m (→much faster: coupla comment tweaks) |
||
Line 1,215: | Line 1,215: | ||
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'5'</span> <span style="color: #008080;">then</span> |
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'5'</span> <span style="color: #008080;">then</span> |
||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- eg 299 -> 295 ie -4</span> |
||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'5'</span> |
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'5'</span> <span style="color: #000080;font-style:italic;">-- or 799 -> 795 ""</span> |
||
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'5'</span> <span style="color: #008080;">then</span> |
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'5'</span> <span style="color: #008080;">then</span> |
||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span> |
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span> <span style="color: #000080;font-style:italic;">-- eg 295 -> 695 == +4</span> |
||
<span style="color: #008080;">else</span> |
<span style="color: #008080;">else</span> |
||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'9'</span> |
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'9'</span> |
||
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">-</span><span style="color: #000000;">5</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">digits</span> |
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">-</span><span style="color: #000000;">5</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">digits</span> <span style="color: #000080;font-style:italic;">-- eg 795 -> 2995 ie +2+2</span> |
||
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 1,419: | Line 1,419: | ||
<span style="color: #000000;">odd_ed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span> |
<span style="color: #000000;">odd_ed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span> |
||
<span style="color: #000000;">weed</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span> |
<span style="color: #000000;">weed</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span> |
||
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">weod</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- add od to |
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">weod</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- add od to even digits</span> |
||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span> |
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span> |
||
<span style="color: #000000;">weod</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span> |
<span style="color: #000000;">weod</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d</span> |
Revision as of 14:21, 14 February 2022
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
AWK
<lang AWK>
- 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)
} </lang>
- 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
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)
-- 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"
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