Find the smallest number bigger than the input whose digital sum is the input

Question

"Digital sum" refers to the sum of all the digits in a number.

For example, the digital sum of 1324 is 10, because 1+3+2+4 = 10.

The challenge is to write a program/function to calculate the smallest number bigger than the input whose digital sum is the input.

Example with walkthrough

As an example, take the number 9 as the input:

9 = 1+8 -> 18
9 = 2+7 -> 27
9 = 3+6 -> 36
...
9 = 8+1 -> 81
9 = 9+0 -> 90

The valid output would be the smallest number above, which is 18.

Specs

Note that 9 is not the valid output for this example, because the reversed number must be greater than the original number.

Note that the input will be positive.

Test-Cases:

 2 => 11      (2 = 1 + 1)
 8 => 17      (8 = 1 + 7)
12 => 39     (12 = 3 + 9)
16 => 79     (16 = 7 + 9)
18 => 99     (18 = 9 + 9)
24 => 699    (24 = 6 + 9 + 9)
32 => 5999   (32 = 5 + 9 + 9 + 9)

References:

This is OEIS A161561.

Edit: Added an additional Testcase (18)

Thanks to Martin Ender for the Leaderboard Snippet

var QUESTION_ID=81047,OVERRIDE_USER=31373;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

05AB1E, 19 17 8 bytes

Code:

[>DSO¹Q#

Explained:

[            # start infinite loop
 >           # increase loop variable, will initially be input
  DSO        # make a copy and sum the digits
     ¹Q#     # if it equals the input, break
             # else return to start of loop
             # implicitly print

Try it online

Edit: Saved 9 bytes thanks to @Adnan

Answer 2

Python 2, 33 bytes

lambda n:[n+9,`n%9`+n/9*'9'][n>9]

A direct expression. Makes a number string with 9's at the end and the remainder at the beginning. Except, for single-digit n, gives n+9.

Some outputs have leading zeroes (099 for 18).

Answer 3

Retina, 39 31 bytes

r`1{1,9}
$.&
T`d`_d`^.$
^.$
1$&

Takes input in unary.

Try it online! (The first two lines allows running several test cases at once and converts from decimal to unary for convenience.)

This doesn't actually search for the result linearly, but computes it explicitly:

• If the input n is greater than 9, we replace it with n % 9 followed by n / 9 (floored) nines.
• Otherwise, we replace it with n + 9.

---

Using ! (or anything else that isn't 1) as the unary digit, I can save one more byte with the following approach:

^!(?!!{9})
1
r`!{0,9}
$.&
0\B

But this input format is a bit of a stretch, I think.

Answer 4

Pyth, 8 bytes

fqQsjT;h

Test suite.

fqQsjT;h

f      h first number T from (input+1) onward where:
 qQ          the input is equal to
   s         the sum of
    jT;      the base-10 representation of T

Answer 5

Java 7, 68 61 bytes

int f(int n){return n>9?-~(n%9)*(int)Math.pow(10,n/9)-1:n+9;}

Does roughly the same thing as many of the other answers here. Wanted to show the Java approach without using string manipulation and loops.

Thanks to FryAmTheEggman for reminding me that I'm dumb ;)

Answer 6

MATL, 10 9 bytes

`QtV!UsG-

Try it online!

Explanation

`        % Do...while
  Q      %   Add 1. Takes input implicitly the first time
  t      %   Duplicate
  V!Us   %   To string, transpose, to number, sum. Gives sum of digits
  G-     %   Subtract input. If 0, the loop ends and the stack is implicitly displayed

Answer 7

Python 3, 128 94 84 74 Bytes

Without output, direct approach, beginner codegolfer ;)

def r(n):
 m=n
 while 1:
  m+=1
  if sum(map(int,str(m)))==n:return(m)

Answer 8

JavaScript (ES7), 32 bytes

n=>(n%9+1)*10**(n/9|0)-(n>9||-8)

38 bytes as ES6:

n=>parseFloat(n%9+1+'e'+n/9)-(n>9||-8)

Answer 9

Actually, 17 bytes

╗1`;$♂≈Σ╜;)=)>*`╓

Try it online!

Explanation:

╗1`;$♂≈Σ╜;)=)>*`╓
╗                  save input to reg0
 1`;$♂≈Σ╜;)=)>*`╓  first integer n (>= 0) where:
   ;$♂≈Σ╜;)=         the base-10 digital sum equals the input and
            )>*      is greater than the input

Answer 10

C 73 65 bytes

A macro with a helper function.

e(y){return y?10*e(y-1):1;}
#define F(n) n<9?n+9:(1+n%9)*e(n/9)-1

The e function just calculates powers of ten, and the F macro uses the same solving method as this ruby, and this python answer. sadly, it is longer than about the same length as both those answers put together. But it is the first C answer.

(8 bytes saved by Lynn's trick of removing int.)

Answer 11

Brachylog, 8 bytes (Non-competing)

<.=:ef+?

= was modified after this challenge got posted, so that it now works on possibly infinite domains, which is the case here.

Explanation

<.       Output > Input
  =      Label the Output (i.e. unify it with an integer)
   :ef   Get the list of digits of the Output
      +? Input is the sum of all those digits

This will backtrack on = until the value of Output makes this whole predicate true.

Answer 12

TSQL(sqlserver 2012), 107 99 bytes

DECLARE @ INT = 32

,@2 char(99)WHILE @>0SELECT
@2=concat(x,@2),@-=x FROM(SELECT IIF(@>9,9,IIF(@2>0,@,@-1))x)y PRINT @2

Try it online!

Answer 13

MathGolf, 8 7 bytes

Æ)_Σk=▼

Try it online!

Implicit input yay.

Explanation:

          Implicit input
 Æ     ▼  Do while false loop that pops the condition
  )       Increment top of stack
   _      Duplicate
    Σ     Get the digit sum
     k    Get input
      =   Is equal?
          Implicit output

Answer 14

Pyke, 9 8 7 bytes, non-competing - uses more recent version

.fhsq)h

Try it here!

.f      - first where true:
  h     - n+1
   sq    - digital_root(^) == input()
      h - that number +1

Answer 15

Python 2, 39 bytes

lambda n:[n+9,(1+n%9)*10**(n/9)-1][n>9]

Pure integer arithmetic.

Full program with output

f=lambda n:[n+9,(1+n%9)*10**(n/9)-1][n>9]

print(f(2))
print(f(8))
print(f(12))
print(f(16))
print(f(17))
print(f(18))
print(f(24))
print(f(32))

Output:

11
17
39
79
89
99
699
5999

Answer 16

Java 10, 114 62 bytes

n->{var r="";for(int i=0;i++<n/9;r+=9);return(n>9?n%9:n+9)+r;}

Try it online.

EDIT: 130 73 bytes without leading zeros (Thanks to @levanth`):

n->{var r="";for(int i=0;i++<n/9;r+=9);return new Long((n>9?n%9:n+9)+r);}

Try it online.

Explanation:

n->                           // Method with integer parameter and long return-type
  var r="";                   //  Result-String, starting empty
  for(int i=0;i++<n/9;r+=9);  //  Append `n` integer-divided by 9 amount of 9's to `r`
  return new Long(            //  Cast String to number to remove any leading zeroes:
    (n>9?                     //   If the input `n` is 10 or larger
      n%9                     //    Use `n` modulo-9
     :                        //   Else (`n` is smaller than 10):
      n+9)                    //    Use `n+9`
    +r);}                     //   And append `r`

Answer 17

JavaScript (ES2015), 45 39 33 bytes

Saved another 6 bytes thanks to @Conor O'Brien and @Shaun H.
I think I'll leave it as is, because this version differs from @Neil's answer by using String.repeat().

v=>+(v>9?v%9+'9'.repeat(v/9):v+9)

Previous version (saved 6 bytes thanks to @Qwertiy):

f=v=>+(v/9>1?v%9+'9'.repeat(v/9|0):v+9)

First version:

f=v=>+(v/9>1?v%9+'9'.repeat(~~(v/9)):'1'+v-1)

Answer 18

PowerShell v2+, 62 bytes

param($n)for($a=$n+1;([char[]]"$a"-join'+'|iex)-ne$n;$a++){}$a

Takes input $n then executes a for loop. We initialize the loop by setting our target number, $a, to be one larger than $n (since it has to be bigger, plus this ensures 1..9 work correctly). Each loop we increment $a++. Nothing happens in the loop proper, but the conditional is where the program logic happens. We're literally taking the target number as a string, casting it as a char-array, -joining the array with + and then piping it to iex (similar to eval). We test whether that's equal to our input number or not, and continue looping accordingly. Once we've exited the loop, we've reached where our target number is digit-sum equal to our input number, so $a is placed on the pipeline and output is implicit.

---

For reference, here's the "construct a string with the appropriate number of 9's" method that other folks have done, at 67 bytes

param($n)(($n+9),(+(""+($n%9)+'9'*(($n/9)-replace'\..*'))))[$n-gt9]

or the "pure integer arithmetic" method that other folks have done, at 70 bytes

param($n)(($n+9),("(1+$n%9)*1e$(($n/9)-replace'\..*')-1"|iex))[$n-gt9]

Neither of which are shorter, but both of which are more interesting.

Answer 19

Ruby, 33 bytes

This is a int arithmetic version that just happens to be the same as xnor's python answer. It is an anonymous function that takes and returns an int.

->n{n<10?n+9:(1+n%9)*10**(n/9)-1}

Answer 20

Lua, 52 bytes

n=...+0
print(n>9 and(n%9)..string.rep(9,n/9)or n+9)

Meant to be saved in a file and run with the Lua interpreter, e.g. lua <file> <input number>

You can also try it here: https://repl.it/CXom/1

(On repl.it the input number is hard-coded for ease of testing)

Answer 21

Racket 70 characters, 71 bytes

Same algorithm as most of the others pretty much. Pretty sad about not having % for modulo, or ** for expt, or integer division by default, otherwise this could be a lot shorter and I could've outgolfed C and Java. Still love the language though

(λ(x)(if(> x 9)(-(*(+(modulo x 9)1)(expt 10(floor(/ x 9))))1)(+ x 9)))

Answer 22

Hexagony, 40 31 30 bytes

<_:->.(.+><.'!.\@"9!%>!/{.}|.?

Or, if you prefer your code to be a little less linear and a little more polygonal:

    < _ : -
   > . ( . +
  > < . ' ! .
 \ @ " 9 ! % >
  ! / { . } |
   . ? . . .
    . . . .

Try it online!

Thanks to @FryAmTheEggman for some ideas and inspiration :o)

Previous version: <.:->+_.!(..'!.\><9!%>@.{.}|.?"

Previouser version: <><.-_|@"'!{|(.9+!8=@>{/".'/:!?$.%\1$..\

Answer 23

Perl 6,  38  29 bytes

{$_>9??(1+$_%9)*10**Int($_/9)-1!!$_+9}
{first *.comb.sum==$_,$_^..*}

_{^{( apparently the direct approach is shorter )}}

Explanation:

{
  first
    *.comb.sum == $_, # lambda that does the check
    $_ ^.. *          # Range.new: $_, Inf, :excludes-min
}

Test:

#! /usr/bin/env perl6

use v6.c;
use Test;

my @tests = (
   2 => 11,
   8 => 17,
   9 => 18,
  12 => 39,
  16 => 79,
  18 => 99,
  24 => 699,
  32 => 5999,
);

plan +@tests;

my &next-digital-sum = {first *.comb.sum==$_,$_^..*}

for @tests -> $_ ( :key($input), :value($expected) ) {
  is next-digital-sum($input), $expected, .gist;
}

1..8
ok 1 - 2 => 11
ok 2 - 8 => 17
ok 3 - 9 => 18
ok 4 - 12 => 39
ok 5 - 16 => 79
ok 6 - 18 => 99
ok 7 - 24 => 699
ok 8 - 32 => 5999

Answer 24

Japt, 9 bytes

@¶Xìx}aUÄ

Try it

Answer 25

Powershell, 54 bytes

$args|%{(($_+9),+(''+$_%9+'9'*(($_-$_%9)/9)))[$_-gt9]}

Test script:

$f = {

$args|%{(($_+9),+(''+$_%9+'9'*(($_-$_%9)/9)))[$_-gt9]}

}

@(
    ,(  1,  10   )
    ,(  2 , 11   )
    ,(  8 , 17   )
    ,(  9 , 18   )
    ,( 10,  19   )
    ,( 11,  29   )
    ,( 12 , 39   )
    ,( 16 , 79   )
    ,( 18 , 99   )
    ,( 19 , 199  )
    ,( 24 , 699  )
    ,( 27 , 999  )
    ,( 32 , 5999 )
    ,( 52 , 799999 )
    ,( 128, 299999999999999 )
) | % {
    $a,$e = $_
    $r = &$f $a
    "$($r-eq$e): $r"
}

Output:

True: 1 : 10
True: 2 : 11
True: 8 : 17
True: 9 : 18
True: 10 : 19
True: 11 : 29
True: 12 : 39
True: 16 : 79
True: 18 : 99
True: 19 : 199
True: 24 : 699
True: 27 : 999
True: 32 : 5999
True: 52 : 799999
True: 128 : 299999999999999

Expalantion

• if [$_-gt9] returns a first digit and a tail
  • a first digit is the difference between $_ and the sum of 9 ($_%9)
  • a tail is a few nines - '9'*(($_-$_%9)/9))
  • finally, converts a result string into a number to remove the leading 0
• else returns ($_+9)

Answer 26

Shakespeare Programming Language, 456 bytes

,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Enter Ajax and Ford]Ford:Listen tothy.Ajax:You be I.[Exit Ajax][Enter Page]Scene V:.Page:You be the sum ofyou a cat.Remember you.Ford:You zero.Scene X:.Ford:You be the sum ofyou the remainder of the quotient betweenI twice the sum ofa cat a big big cat.Page:You be the quotient betweenyou twice the sum ofa cat a big big cat.Be you nicer zero?If solet usScene X.Recall.Am I as big as Ajax?If notlet usScene V.Open heart

Try it online!

Answer 27

GolfScript, 22 bytes

~:x{).10base{+}*x=!}do

Try it online!

Any tips are appreciated--I feel like this could be shorter.

Explanation

~:x{).10base{+}*x=!}do
~                       Eval the input (casting from string to integer)
 :x                     Store a copy in x
   {               }do  Run a do...while loop using this block:
    )                    Increment
     .                   Duplicate
      10base             Convert the number to a list of base-10 digits
            {+}*         Fold on + (sum the digits)
                x        Push x (the original input)
                 =       Test if the sum equals the original input
                  !      Negate, so the loop condition is true while the sum does *not* equal the
                         original input

When the loop exits, we have a number on the stack whose digit sum equals the original input. It is guaranteed to be greater than the original input because the loop, which begins by incrementing the number, executes at least once. Finally, when the program terminates, the stack is autoprinted.

Answer 28

Haskell, 44 bytes

f x|x>9=(2+mod(x-1)9)*10^div(x-1)9-1|x>0=9+x

Try it online!

Uses math. In pseudocode:

If x > 9, return:
  ((x-1) mod 9 + 2) * 10 ^ ((x-1) / 9) - 1
Else if x > 0, return:
  9 + x

Answer 29

Ruby, 38 bytes

f=->n{n<11?n+9:"#{n<19?n-9:f.(n-9)}9"}

This answer returns a string or int depending on input size. It is a recursive solution that asks for a solution for 9 less then adds a "9" to the end.

---

Ruby, 39 bytes

f=->n{n<11?n+9:(n<19?n-9:f.(n-9))*10+9}

For one more byte, this answer always returns an int. same algorithm as above but with numbers.

Answer 30

C, 80 bytes

i;s;g(j){s=0;for(;j;j/=10)s+=j%10;return s;}f(n){i=n;while(n-g(i))i++;return i;}

Ungolfed try online

int g(int j)
{
    int s=0;
    for(;j;j/=10) s += j%10;
    return s;
}

int f(int n)
{
    int i=n;
    for(;n-g(i);i++);
    return i;
}

Answer 31

PHP, 77 characters

$n=$argv[1];$m=$n+1;while(1){if(array_sum(str_split($m))==$n)die("$m");$m++;}

Answer 32

Oracle SQL 11.2, 165 bytes

SELECT l FROM(SELECT LEVEL l,TO_NUMBER(XMLQUERY(REGEXP_REPLACE(LEVEL,'(\d)','+\1')RETURNING CONTENT)) s FROM DUAL CONNECT BY 1=1)WHERE s=:1 AND l!=s AND rownum=1;

Un-golfed

SELECT l   
FROM   (
         SELECT LEVEL l, -- Number to evaluate
                XMLQUERY( 
                          REGEXP_REPLACE(LEVEL,'(\d)','+\1')  -- Add a + in front of each digit 
                          RETURNING CONTENT
                        ).GETNUMBERVAL()s                     -- Evaluate le expression generated by the added + 
                FROM DUAL 
                CONNECT BY 1=1 -- Run forever            
       )
WHERE s=:1      -- The sum must be equal to the input
  AND l!=s      -- The sum must not be the input 
  AND rownum=1  -- Keep only the first result

Answer 33

Python 3 55 Bytes

Takes two arguments that are the same

f=lambda a,b:a if sum(map(int,str(a)))==b else f(-~a,b)

i.e. to call it you would use f(x,x)