Find the smallest positive integer which ends in n, is divisible by n and whose digits sum to n

Question

It's all in the title...

Take as input a positive integer n>=12 and... do what the title says.

Yes, this is on OEIS A187924.

Some test cases

12 -> 912  
13 -> 11713  
14 -> 6314  
15 -> 915  
16 -> 3616  
17 -> 15317  
18 -> 918  
19 -> 17119 
20 -> 9920  
40 -> 1999840   
100-> 99999999999100

This is code-golf. Shortest code in bytes wins!

Answer 1

Befunge, 81 bytes

&>00p0v<!%g0<
v%"d":_>1+:0^
>00g->#^_:0v
0g10g-#^_.@1>
>0p:55+/\:v>
^1+g01%+55_$^

Try it online!

Can handle up to n = 70 at least, after which some values will start overflowing the stack cell size on most implementations, and on those that don't, it'll take so long that it's not worth waiting to find out.

Given those constraints, we don't even bother trying to handle values of n greater than 99, which means we can more easily test if the value ends in n with by simply comparing the value modulo 100 with n.

Below is more detailed breakdown of the code.

Read n from stdin and save in memory.
Initialize the test value v to 0 and start the main loop, incrementing v up front.
Test if v%n == 0, and if not return to the start of the main loop.
Test if v%100 == n, and if not return to the start of the main loop.
Sum the digits in v by repeatedly adding v modulo 10 and dividing v by 10.
Test if the sum is equal to n, and if not return to the start of the main loop.
Otherwise output v and exit.

Answer 2

JavaScript (ES6), 55 54 bytes

f=(s,p=0,a=p+s)=>a%s|eval([...a].join`+`)-s?f(s,p+1):a

<input type=number min=12 oninput=o.textContent=f(this.value)><pre id=o>

Takes input as a string. Needs a browser with tail recursion support for the larger results. Edit: Saved 1 byte thanks to @Arnauld.

Answer 3

05AB1E, 14 bytes

[NI«ÐIÖsSOIQ*#

Try it online!

Explanation

Solutions requiring large prefixes will time out on TIO

[                # start a loop
 NI«             # append input to current iteration number
    Ð            # triplicate
     IÖ          # is the first copy evenly divisible by input?
       sSOIQ     # is the digit sum of the second copy equal to the input?
            *    # multiply
             #   # if true, break loop
                 # output the third copy

Answer 4

Brachylog v2, 12 10 bytes

a₁.;A×?≜ẹ+

Try it online!

This is a function submission that takes input via . and produces output via ? (the opposite of the normal convention; all Brachylog functions have exactly two arguments, which can be input or output arguments, but the language doesn't enforce any particular argument usage). We don't normally consider conventions for argument usage to be relevant at PPCG.

Explanation

A previous version of this solution had a special case (Ḋ|, i.e. "return digits literally") for single digits, but the question apparently states that you don't have to check for that (thanks @DLosc for catching this), so I removed it. (The solution as written won't work on single digits as Brachylog won't consider 1 as a possibility for an unknown in a multiplication, to prevent infinite loops; its multiplications are arbitrary-arity.)

So this answer now goes for a pretty much direct translation of the specification. Starting with ? (the output / number we're trying to find; a Brachylog predicate always implicitly starts with ?) we use a₁. to assert that it has . (the input) as a suffix. Then ;A×? means that we can multiply (×) the result by something (;A) to produce ? (the output). Finally, ẹ+ sums (+) the digits (ẹ) of ?, and there's by default an implicit assertion at the end of every Brachylog program that the final result produces .. So in other words, this program is ". is a suffix of ?, . multiplied by something is ?, . is the digit sum of ?", which is very close to a literal translation of the original program.

The ≜ is necessary for the digit sum requirement to be enforced. I assume something about ẹ doesn't like unknowns, so the ≜ tells Brachylog to use a brute-force approach for that part of the program rather than algebra.

Answer 5

Alice, 35 bytes

/o
\i@/!w?+.?~\ & /-$K..?\ L z $ /K

Try it online!

Explanation

This program has a really nice mix and interaction between Cardinal (integer-processing) and Ordinal (string-processing) mode.

The usual framework for challenges with decimal I/O which operate largely in Cardinal mode:

/o 
\i@/...

And the actual program:

!     Store the input N on the tape.
      We'll use an implicit zero on top of the stack as our iterator variable X,
      which searches for the first valid result.
w     Store the current IP position on the return address stack. This marks
      the beginning of the main search loop. We can avoid the divisibility
      test by going up in increments of N. To check the other two 
      conditions, we'll use individual conditional loop ends that skip to 
      the next iteration. Only if both checks pass and all loop ends are 
      skipped will the search terminate.

  ?+    Increment the iterator X by N.
  .     Duplicate X.
  ?~    Put a copy of N underneath.
  \     Switch to Ordinal mode.
  &     Implicitly convert X to a string, then fold the next command over its
        characters, i.e. its digits. Here, "fold" means that each character
        is pushed to the stack in turn, followed by one execution of that
        next command.
  /     Switch back to Cardinal mode (this is not a command).
  -     Fold subtraction over the digits. This implicitly converts each 
        digit back to its numerical value and subtracts it from N. If the
        digit sum of X is equal to N, this will result in 0.
  $K    Jump back to the w if the digit sum of X isn't N.
  ..    Duplicate X twice.
  ?     Get a copy of N.
  \     Switch to Ordinal mode.
  L     Shortest common superstring. Implicitly converts X and N to strings
        and gives the shortest string that starts with X and ends with N. 
        This will be equal to X iff X already ends with N. Call this Y.
  z     Drop. If X contains Y, this deletes everything up to and including
        Y from X. This can only happen if they are equal, i.e. if X ended
        with N. Otherwise X remains unchanged.
  $     Skip the next command if the string is empty, i.e. if X ended with N.
  /     Switch back to Cardinal mode.
  K     Jump back to w if X didn't end with N.

Answer 6

Haskell, 72 bytes

f n=[x|x<-[n,n+lcm n(10^length(show n))..],sum[read[j]|j<-show x]==n]!!0

Try it online!

Note that the found number minus n must be a multiple of both n and 10^length(n).

Inspired by Laikoni and totallyhuman

Answer 7

Java (OpenJDK 8), 136 110 103 92 bytes

-26 thanks to JollyJoker

-7 again thanks to JollyJoker

-11 thanks to Oliver Grégoire

a->{for(int i=a;!(""+a).endsWith(""+i)|i!=(""+a).chars().map(x->x-48).sum();a+=i);return a;}

Try it online!

Gotta love Java! It could well be that I am using an inefficient approach, but not having a built in checksum function and the double conversion to String to check for the end of the number costs bytes...

Ungolfed:

  a->{                                                       //input n (as integer)
      for (int i = a;                                        //initiate loop
           !("" + a).endsWith("" + i)                        //check if the calculated number ends with the input
           | i != ("" + a).chars().map(x -> x - 48).sum();   //check if the checksum is equal to the input
           a += i)                                           //for every iteration, increase i by the input to save checking for divisibility
        ;                                                    //empty loop body, as everything is calculated in the header
    return a;                                                //return number
}

Answer 8

Mathematica, 72 bytes

(t=#;While[Mod[t,10^IntegerLength@#]!=#||Tr@IntegerDigits@t!=#,t+=#];t)&  

-18 bytes from @MartinEnder

Try it online!

Here is another version from Martin Ender
This approach can go up to n=40 (41 exceeds the default iteration limit)

Mathematica, 65 bytes

#//.t_/;Mod[t,10^IntegerLength@#]!=#||Tr@IntegerDigits@t!=#:>t+#&

Try it online!

Answer 9

Husk, 20 19 17 bytes

ḟȯ=⁰Σdfȯ€d⁰ṫdm*⁰N

Thanks @Zgarb for -2 bytes!

Try it online!

Answer 10

C (gcc) 71 69 bytes , fails on 100

I tried with long and %1000 but times out

-2 bytes thanks to steadybox

s,i,j;f(n){for(j=0;s^n|j%100!=n;)for(s=0,i=j+=n;i;i/=10)s+=i%10;j=j;}

Try it online

Answer 11

Python 2, 74 bytes

This solution assumes that n <= sys.maxint.

n=x=input()
while sum(map(int,str(x)))-n*str(x).endswith(`n`):x+=n
print x

Try it online!

Answer 12

C# (.NET Core), 90 84 83 + 18 = 101 bytes

using System.Linq;
n=>{for(int i=n;!(""+n).EndsWith(""+i)|n%i>0|(""+n).Sum(c=>c-48)!=i;n++);return n;}

Try it online!

• 6 bytes saved thanks to Emigna and my uncanny ability to write (""+n) in some places and n.ToString() in others.

Answer 13

Julia, 70 bytes

f(x)=(n=x;while(sum(digits(n))!=x||x!=n%(10^length("$x")));n+=x;end;n)

Answer 14

Ohm v2, 16 bytes

£^›u³↔ξ³¥s}Σ³E*‽

Try it online!

Answer 15

Pip, 18 bytes

T!y%a&$+y=aY++i.ay

Algorithm inspired by Emigna's answer. Try it online!

How it works

                    a is 1st cmdline arg, i is 0, y is "" (implicit)
T                   Loop until
 !y%a&              y%a is 0 and
      $+y=a         sum of y is a:
            ++i      Increment i
           Y   .a    and yank (i concat a) into y
                 y  After the loop exits, autoprint y

Answer 16

JavaScript REPL (ES5), 60 59 bytes

for(n=prompt(i=0);eval([].join.call(t=++i+n,'+'))-n|t%n;);t

Answer 17

Haskell, 75 bytes

f n=[x|x<-[0,n..],sum[read[d]|d<-show x]==n,mod x(10^length(show n))==n]!!0

Try it online!

Explanation:

f n=[x|                                      ]!!0 -- Given input n, take the first x
       x<-[0,n..],                                -- which is a multiple of n,
                  sum[read[d]|d<-show x]==n,      -- has a digital sum of n
                  mod x(10^length(show n))==n     -- and ends in n.

I wonder whether the "ends in n" part can be shortened. I also tried show n`elem`scanr(:)""(show x), but it's longer.

Answer 18

Haskell, 75 bytes

f n=[i|i<-[n,n+10^length(show$n)..],i`mod`n<1,sum[read[j]|j<-show$i]==n]!!0

Try it online!

Answer 19

Ruby, 65 63 54 53 bytes

->n{a=n;a+=n until/#{n}$/=~a.to_s&&a.digits.sum==n;a}

Try it online!

Answer 20

Pyth,  22  21 bytes

fq2-/,%T^;l`QsjT;Q%TQ

Try it here!

Answer 21

Perl 5, 46 44 + 1 ( -p ) = 45 bytes

2 bytes saved thanks to Xcali, couldn't find better

($\=++$t.$_)%$_|$_-eval$\=~s//+/gr.0&&redo}{

first answer

$\=++$x.$_;eval$\=~s//+/gr."-$_"|$\%$_&&redo}{

Try it online

Answer 22

PowerShell, 84 bytes

for($n=$i=$args[0];$i%$n-or$i-notmatch"$n$"-or([char[]]"$i"-join'+'|iex)-$n){$i++}$i

Try it online!

Simple construction but lengthy commands. Times out on TIO for n=100, but if we explicitly set i to be close, it outputs correctly.

This is just a simple for loop that keeps going so long as any one of the conditions is true. The three conditions are 1) $i%$n, i.e., we have a remainder; 2) $i-notmatch"$n$", i.e., it doesn't regex match the last couple of digits; and 3) ([char[]]"$i"-join'+'|iex)-$n, i.e., the digits summed together is not equal to $n (here checked by simple subtraction, since nonzero values are truthy). Inside the loop we're simply incrementing $i.

Thus, if we don't have a remainder, the regex matches, and the numbers are equal, all three conditions are $false and we exit the loop. As a result, we just can leave $i on the pipeline, and output is implicit.

Answer 23

PHP, 73+1 bytes

while(array_sum(str_split($i+=$n=$argn))-$n|$i%10**strlen($n)-$n);echo$i;

Run as pipe with -R.

loops $i through multiples of <input> until sum_of_digits-<input> and tail_of_i-$n are falsy; then prints i.

Answer 24

m4, 210 bytes

define(d,define)d(i,ifelse)d(s,`i($1,,0,`eval(substr($1,0,1)+s(substr($1,1)))')')d(k,`r($1,eval($2+1))')d(r,`i(s($2),$1,i(regexp($2,$1$),-1,`k($1,$2)',i(eval($2%$1),0,$2,`k($1,$2)')),`k($1,$2)')')d(f,`r($1,1)')

Defines a macro f which computes the answer. It's a bit slow—unusably so—but I promise it works.

I thought m4 would be nice because it treats integers as strings by default, but this is pretty bad.

Answer 25

Scala, 120 bytes

def a(n:Int)={val b=math.pow(10,math.ceil(math.log10(n))).##;var c=b+n;while(c%n!=0||(0/:c.toString)(_+_-'0')!=n)c+=b;c}

This works until n = 70, after which integers overflow. For one extra character, the Int can change to a Long and allow values for n > 100 to be computed.

Here is the slightly longer ungolfed version:

def golfSourceLong(n: Long): Long = {
  val delta = math.pow(10, math.ceil(math.log10(n))).toInt
  var current = delta + n
  while (current % n != 0 || current.toString.foldLeft(0)(_ + _ - '0') != n) {
    current += delta
  }
  current
}

Answer 26

R, 115 bytes

function(n,d=nchar(n):1){while(sum(D<-F%/%10^((k=nchar(F)):1-1)%%10)-n|any(D[k-d+1]-n%/%10^(d-1)%%10)|F%%n)F=F+n
F}

Try it online!

Terrible R function. Increments F (starts at 0) by n until a value is found that satisfies the required properties, which it then returns. The use of any on a double expression sends out a warning for each iteration of the loop, but does not affect the correctness.

Times out on TIO for large enough inputs (n=55 or higher) but should correctly compute the solution given enough time/space.

Answer 27

Jelly, 22 21 bytes

DS=³a³ḍaDṫ³DLC¤Ḍ=³ø1#

Try it online!

Edit: compressed to a single line

Explanation

DS=³a³ḍaDṫ³DLC¤Ḍ=³ø1#
                  ø1#  Evaluate the condition before this and increment a counter until it is met then output the counter                     
D                      Digits of incremented variable as a list
 S                     Sum
  =³                   Equals argument of program?
    a                  Logical and
     ³ḍ                Does arg divide incremented variable?
       a               Logical and
        Dṫ     Ḍ       Last n digits of inc. var. where n is number of digits in program input
          ³DLC         1 - (number of digits of program input)
              ¤        Book ends above nilad
                =³     Equals program input?

This took me many hours to write because I'm learning Jelly but now that I'm done I'm so satisfied. For a long time I didn't realize I needed the ¤ and I just couldn't get it to work. Looking at [this][1] well explained code helped me seal the deal. Lots of other Jelly answers in PPCG guided me too.

Answer 28

Javascript, 224 bytes function getNumber(x){if(x<12){return!1};const sumDigits=(x)=>x.toString().split('').map(Number).reduce((a,b)=>a+b,0);for(let i=2;i<9999;i++){if((x*i-x)%(Math.pow(10,x.toString().length))==0&&sumDigits(x*i)==x){return x*i}}} Un-golf:

function getNumber(x){
 if (x<12) {return false};
 const sumDigits = (x) => x.toString().split('').map(Number).reduce((a,b)=>a+b, 0);
 for (let i=2; i<9999; i++){
  if((x*i-x)%(Math.pow(10, x.toString().length))==0 && sumDigits(x*i)==x){
   return x*i;
}
}
}

Usage: 1. getNumber(12) 2. getNumber(13) 3. ....

Answer 29

J, 37 33 bytes

+^:(((=1#."."0)*:(e.".\.))":)^:_~

Try it online!

                                ~    A = N
+^:                          ^:_     while(...)A+=N; return A
   (                      ":)        A to string
   (((    "."0)          )  )        digits of A
   ((( 1#.    )          )  )        sum
   (((=       )          )  )        equals N
   ((            (e.".\.))  )        N is one of the suffixes of A-string
   ((          *:        )  )        not AND

Prepending the iteration counter is ~5 times faster but 5 bytes longer:

(]+[((=1#.,.&.":)<:|),~&.":)^:_&1,&":]

Try it online!

Incrementing by 100, 27 bytes:

(]+100*(=1#.,.&.":)<:|)^:_~

Try it online!

Answer 30

Python 2, 70 bytes

f=lambda n,x=0:x*(x%n<sum(map(int,`x`))==n==x%10**len(`n`))or f(n,x+n)

Try it online!