Minimum multiple of m where digital sum equals m: Difference between revisions
Not a robot (talk | contribs) Add ABC |
Added Quackery. |
||
Line 2,323: | Line 2,323: | ||
19 109 73 37 199 73 37 271 172 1333 |
19 109 73 37 199 73 37 271 172 1333 |
||
289 559 1303 847 1657 833 1027 1576 1282 17497</pre> |
289 559 1303 847 1657 833 1027 1576 1282 17497</pre> |
||
=={{header|Quackery}}== |
|||
<code>from</code>, <code>index</code> and <code>and</code>are defined at [[Loops/Increment loop index within loop body#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> [ 0 swap |
|||
[ 10 /mod |
|||
rot + swap |
|||
dup 0 = until ] |
|||
drop ] is digitsum ( n --> n ) |
|||
[] 40 times |
|||
[ i^ 1+ 1 from |
|||
[ dup dup index * |
|||
digitsum = if |
|||
[ index swap end ] ] |
|||
drop join ] |
|||
echo</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 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 ]</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
Revision as of 23:06, 2 July 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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
11l
F digit_sum(=n)
V sum = 0
L n > 0
sum += n % 10
n I/= 10
R sum
L(n) 1..70
L(m) 1..
I digit_sum(m * n) == n
print(‘#8’.format(m), end' I n % 10 == 0 {"\n"} E ‘ ’)
L.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
ALGOL 68
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
ABC
HOW TO RETURN digit.sum n:
PUT 0 IN sum
WHILE n>0:
PUT sum + (n mod 10) IN sum
PUT floor (n/10) IN n
RETURN sum
HOW TO RETURN a131382 n:
PUT 1 IN m
WHILE n <> digit.sum (m*n): PUT m+1 IN m
RETURN m
FOR n IN {1..70}:
WRITE (a131382 n)>>9
IF n mod 10=0: WRITE /
- 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
{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
# 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
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
- Output:
Same as FreeBASIC entry.
BBC BASIC
FOR N%=1 TO 70
PRINT FNa131382(N%);
IF N% MOD 10 == 0 PRINT
NEXT
END
DEF FNa131382(n%) LOCAL m%
m%=1
WHILE n% <> FNdigit_sum(m% * n%)
m%+=1
ENDWHILE
=m%
DEF FNdigit_sum(n%) LOCAL sum%
WHILE n%
sum%+=n% MOD 10
n%/=10
ENDWHILE
=sum%
Chipmunk Basic
100 cls
110 c = 0
120 n = 1
130 while c < 70
140 m = 1
150 while 1
160 nm = n*m
170 t = 0
180 while nm
190 t = t + nm mod 10
200 nm = floor(nm / 10)
210 wend
220 if t = n then exit while
230 m = m +1
240 wend
260 c = c +1
270 print using "########"; m;
280 if c mod 10 = 0 then print
290 n = n +1
300 wend
310 end
- Output:
Same as FreeBASIC entry.
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
- 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
Gambas
Public Sub Main()
Dim c As Integer = 0, n As Integer = 1
Do While c < 70
Dim m As Integer = 1
Do
Dim nm As Integer = n * m, t As Integer = 0
While nm
t += nm Mod 10
nm = Floor(nm / 10)
Wend
If t = n Then Break
m += 1
Loop
c += 1
Print Format(m, "######## ");
If c Mod 10 = 0 Then Print
n += 1
Loop
End
PureBasic
Procedure.i floor(n.d)
Result = (n*2.0-0.5)
ProcedureReturn Result >> 1
EndProcedure
OpenConsole()
c.i = 0
n.i = 1
While c < 70
m.i = 1
Repeat
nm.d = n*m
t.d = 0
While nm
t = t + Mod(nm, 10)
nm = floor(nm/10)
Wend
If t = n
Break
EndIf
m + 1
ForEver
c + 1
Print(RSet(Str(m), 8) + " ")
If Mod(c, 10) = 0
PrintN("")
EndIf
n + 1
Wend
Input()
CloseConsole()
- Output:
Same as FreeBASIC entry.
True BASIC
LET c = 0
LET n = 1
DO WHILE c < 70
LET m = 1
DO
LET nm = n*m
LET t = 0
DO WHILE nm<>0
LET t = t+REMAINDER(nm,10)
LET nm = IP(nm/10)
LOOP
IF t = n THEN EXIT DO
LET m = m+1
LOOP
LET c = c+1
PRINT USING "######## ": m;
IF REMAINDER(c,10) = 0 THEN PRINT
LET n = n+1
LOOP
END
XBasic
PROGRAM "program name"
VERSION "0.0000"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
c = 0
n = 1
DO WHILE c < 70
m = 1
DO WHILE 1
nm = n * m
t = 0
DO WHILE nm
t = t + nm MOD 10
nm = INT((nm / 10)+.5)
LOOP
IF t = n THEN EXIT DO
INC m
LOOP
INC c
PRINT FORMAT$("######## ", m);
IF c MOD 10 = 0 THEN PRINT
INC n
LOOP
END FUNCTION
END PROGRAM
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
- Output:
Same as FreeBASIC entry.
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;
}
- 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++
#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
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
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
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
/* 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
Delphi
function SumDigits(N: integer): integer;
{Sum the integers in a number}
var T: integer;
begin
Result:=0;
repeat
begin
T:=N mod 10;
N:=N div 10;
Result:=Result+T;
end
until N<1;
end;
procedure MinimumMultipleM(Memo: TMemo);
{Find N's where DigitSum(N X M) = N.}
var N,M: integer;
var S: string;
begin
S:='';
for N:=1 to 70 do
for M:=1 to High(integer) do
begin
if SumDigits(M * N) = N then
begin
S:=S+Format('%8d',[M]);
if N mod 10 = 0 then S:=S+#$0D#$0A;
break;
end;
end;
Memo.Lines.Add(S);
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 115797112842857
EasyLang
fastfunc f n .
m = 1
repeat
h = m * n
sum = 0
while h > 0
sum += h mod 10
h = h div 10
.
until sum = n
m += 1
.
return m
.
for n = 1 to 70
write f n & " "
.
F#
// 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
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
: 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
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
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
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
Java
public final class MinimumMultipleDigitSum {
public static void main(String[] aArgs) {
for ( int n = 1; n <= 70; n++ ) {
int k = 0;
while ( digitSum(k += n) != n );
System.out.print(String.format("%8d%s", k / n, ( n % 10 ) == 0 ? "\n" : " "));
}
}
private static int digitSum(int aN) {
int sum = 0;
while ( aN > 0 ) {
sum += aN % 10;
aN /= 10;
}
return sum;
}
}
- 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
Jakt
Output format follows the C++ solution with a small difference in the leading whitespace.
fn digital_sum(anon n: i64, accumulator: i64 = 0) -> i64 => match n {
0 => accumulator
else => digital_sum(n: n / 10, accumulator: accumulator + n % 10)
}
fn main() {
for n in 1..71 {
for m in (1..) {
if digital_sum(n * m) == n {
print("{: 9}", m)
if n % 10 == 0 {
println()
}
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
jq
Works with jq and gojq, the C and Go implementations of jq
Apart from a small tweak to the `lpad` function, the following program also works with jaq, the Rust implementation of jq.
Assuming `digitSum` has been suitably defined to yield the sum of the digits of a decimal number, a jq expression for computing the $nth-term in the series is:
1 | until((. * $n) | digitSum == $n; . + 1)
Let's abstract that into a self-contained jq function:
def minimum_integer_multiple:
def digitSum:
def add(s): reduce s as $_ (0; .+$_);
add(tostring | explode[] | . - 48);
. as $n
| 1 | until((. * $n) | digitSum == $n; . + 1);
To display the first several values of the series in rows of 10 values, we could first capture them as a single array, but to avoid allocating unnecessary memory and to highlight jq's support for stream-oriented processing, we shall instead use the following function for grouping the items in a (possibly non-finite) stream into arrays of length at most $max:
# This function assumes that nan can be taken as the eos marker
def nwise(stream; $n):
foreach (stream, nan) as $x ([];
if length == $n then [$x] else . + [$x] end)
| if (.[-1] | isnan) and length>1 then .[:-1]
elif length == $n then .
else empty
end;
The tasks can then be accomplished as follows:
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
nwise(
range(1; 71) | minimum_integer_multiple;
10)
| map(lpad(9)) | join(" ")
- 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
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
- 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
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
Nim
import std/strutils
func digitSum(n: Natural): int =
## Return the sum of digits of "n".
var n = n
while n != 0:
result.inc n mod 10
n = n div 10
iterator a131382(count: Natural): (int, int) =
## Yield the index and value of the first "count" elements
## of the sequence.
for n in 1..count:
var m = 1
while digitSum(m * n) != n:
inc m
yield (n, m)
for idx, n in a131382(70):
stdout.write align($n, 9)
if idx mod 10 == 0: stdout.write '\n'
- 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
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.
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
#!/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
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)
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
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"
PL/M
... under CP/M (or an emulator)
100H: /* FIND THE SMALLEST M WHERE M*N = DIGIT SUM OF N, N IN 1 .. 70 */
/* CP/M BDOS SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
/* TASK */
DECLARE TRUE LITERALLY '0FFH', FALSE LITERALLY '0';
DIGIT$SUM: PROCEDURE( N )ADDRESS; /* RETURNS THE DIGIT SUM OF N */
DECLARE N ADDRESS;
IF N < 10 THEN RETURN N;
ELSE DO;
DECLARE ( RESULT, V ) ADDRESS;
RESULT = N MOD 10;
V = N / 10;
DO WHILE V > 0;
RESULT = RESULT + ( V MOD 10 );
V = V / 10;
END;
RETURN RESULT;
END;
END DIGIT$SUM ;
/* SHOW THE MINIMUM MULTIPLE OF N WHERE THE DIGIT SUM OF THE MULTIPLE IS N */
DECLARE ( M, N ) ADDRESS;
DECLARE FOUND$MULTIPLE BYTE;
DO N = 1 TO 39;
FOUND$MULTIPLE = FALSE;
M = 0;
DO WHILE NOT FOUND$MULTIPLE;
M = M + 1;
IF DIGIT$SUM( M * N ) = N THEN DO;
FOUND$MULTIPLE = TRUE;
CALL PR$CHAR( ' ' );
IF M < 10000 THEN DO;
CALL PR$CHAR( ' ' );
IF M < 1000 THEN DO;
CALL PR$CHAR( ' ' );
IF M < 100 THEN DO;
CALL PR$CHAR( ' ' );
IF M < 10 THEN CALL PR$CHAR( ' ' );
END;
END;
END;
CALL PR$NUMBER( M );
IF N MOD 8 = 0 THEN CALL PR$NL;
END;
END;
END;
EOF
- 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
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
'''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
Quackery
from
, index
and and
are defined at Loops/Increment loop index within loop body#Quackery.
[ 0 swap
[ 10 /mod
rot + swap
dup 0 = until ]
drop ] is digitsum ( n --> n )
[] 40 times
[ i^ 1+ 1 from
[ dup dup index *
digitsum = if
[ index swap end ] ]
drop join ]
echo
- 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
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
Refal
$ENTRY Go {
= <Table MinMult 1 70 10 10>;
};
MinMult {
s.N = <MinMult s.N 1>;
s.N s.M, <DigSum <* s.M s.N>>: s.N = s.M;
s.N s.M = <MinMult s.N <+ s.M 1>>;
};
DigSum {
0 = 0;
s.N, <Symb s.N>: s.D e.R = <+ <Numb s.D> <DigSum <Numb e.R>>>;
};
Cell {
s.Size e.X, <Lenw e.X>: s.Cur e.Y,
<Compare s.Cur s.Size>: '-' = <Cell s.Size ' 'e.X>;
s.Size e.X = e.X;
};
Table {
s.F s.N s.Max s.Width s.CW =
<Table s.F s.N s.Max s.Width s.CW s.Width ()>;
s.F s.N s.Max s.Width s.CW 0 (e.Line) =
<Prout e.Line>
<Table s.F s.N s.Max s.Width s.CW s.Width ()>;
s.F s.N s.Max s.Width s.CW s.Col (e.Line), <Compare s.N s.Max>: '+' =
<Prout e.Line>;
s.F s.N s.Max s.Width s.CW s.Col (e.Line) =
<Table s.F <+ s.N 1> s.Max s.Width s.CW <- s.Col 1>
(e.Line <Cell s.CW <Symb <Mu s.F s.N>>>)>;
};
- 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
RPL
≪ 0 SWAP WHILE DUP REPEAT 10 MOD LAST / FLOOR SWAP ROT + SWAP END DROP ≫ ‘∑DIG’ STO ≪ 0 DO 1 + DUP2 * UNTIL ∑DIG 3 PICK == END SWAP DROP ≫ ‘A131382’ STO
≪ { } 1 40 FOR j j A131382 + NEXT ≫ EVAL
- Output:
1: { 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 }
Runs in 98 minutes on a HP-28S.
Ruby
a131382 = (0..).lazy.map{|n| (1..).detect{|m|(n*m).digits.sum == n} }
a131382.take(70).each_slice(10){|slice| puts "%8d"*slice.size % slice }
- Output:
1 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
SETL
program minimum_multiple_of_m_where_digit_sum_equals_m;
loop for n in [1..70] do
putchar(lpad(str minmult n, 9));
if n mod 10=0 then print; end if;
end loop;
op minmult(m);
n := 1;
(while digsum(n*m) /= m) n +:= 1; end;
return n;
end op;
op digsum(n);
return +/[[n mod 10, n div:=10](1) : until n=0];
end op;
end program;
- 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
Sidef
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
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
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)
}
Fmt.tprint("$,10d", res, 10)
- 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
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
- Programming Tasks
- Solutions by Programming Task
- 11l
- ALGOL 68
- ABC
- APL
- AWK
- BASIC
- BASIC256
- BBC BASIC
- Chipmunk Basic
- FreeBASIC
- Gambas
- PureBasic
- True BASIC
- XBasic
- Yabasic
- C
- C++
- CLU
- COBOL
- Cowgol
- Draco
- Delphi
- SysUtils,StdCtrls
- EasyLang
- F Sharp
- FOCAL
- Forth
- Go
- Go-rcu
- Haskell
- J
- Java
- Jakt
- Jq
- Julia
- MAD
- Nim
- Pascal
- Free Pascal
- Perl
- Phix
- Phix/online
- PL/M
- Prolog
- Python
- Quackery
- Raku
- Refal
- RPL
- Ruby
- SETL
- Sidef
- Swift
- Wren
- Wren-math
- Wren-seq
- Wren-fmt
- XPL0