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

"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.

Thanks to Martin Ender for the Leaderboard Snippet

• This title made my brain hurt. – Fatalize Jun 1 '16 at 12:26

05AB1E, 1917 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
# implicitly print

Try it online

Edit: Saved 9 bytes thanks to @Adnan

• SO is a shorter way to get the sum of digits (instead of J)O). Also, without variable assignment, you can do [>DSO¹Q# :). – Adnan Jun 1 '16 at 10:54
• @Adnan. Nice! I totally missed S. Should have realized I didn't need the variables. – Emigna Jun 1 '16 at 11:06

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).

Retina, 39 31 bytes

r1{1,9}
$.& Td_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. • So Retina won't allow Integer input or just can't handle Integer arithmetic? – levanth Jun 1 '16 at 13:37 • @levanth There is no arithmetic at all in Retina - the entire language is based on string processing via regular expressions, so all the arithmetic is usually done on unary representations. Retina could take decimal integer input and convert it to unary first, but that costs 6 additional bytes, and our policies allow unary input unless the challenge specifies decimal. (If you would rather require all answers to take decimal input, feel free to say so in the specification and I'll update my answer.) – Martin Ender Jun 1 '16 at 15:04 • no no its okay ^^ I was just curious about the unary input – levanth Jun 1 '16 at 15:15 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 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 ;) • At least you outgolfed SQL? – Rɪᴋᴇʀ Jun 2 '16 at 16:52 • Meh, only twice as large as most python/ruby answers here, so I don't feel too bad for Java right now. It would've been nice to beat C though :P – Geobits Jun 2 '16 at 16:53 • :/ Oops, got that from my class block. I must be rusty at this. – Geobits Jun 2 '16 at 17:05 • @Geobits It would probably beat C--. – gcampbell Jun 2 '16 at 17:05 • @Fry Completely forgot about that trick. Thanks, that put me ahead of C at least ;) – Geobits Jun 2 '16 at 17:08 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 • Clever use of V!U +1 from me. That should go in our list of MATL idioms. – Suever Jun 2 '16 at 0:20 • @Suever Yes, that gets used quite often – Luis Mendo Jun 2 '16 at 6:47 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) Python 3, 1289484 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) • For starters, there are a lot of spaces that can be removed. Before/after =+() for example. – Emigna Jun 1 '16 at 13:00 • Also you can replace print(m) with return m (doesn't save any bytes but you don't have to print in the function itself). You can still print the output function return with print(r(n)) to test your function – levanth Jun 1 '16 at 13:02 • You can also remove lots of newlines; m=n+1;f=1 and if s==n:f=0 – Blue Jun 1 '16 at 13:03 • When replacing print with return, you can do it directly in the if-statement and remove f as well as the else-statement. – Emigna Jun 1 '16 at 13:04 • You can still remove f and just use while 1: and also remove the space between int(c) and for – Emigna Jun 1 '16 at 13:13 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 • This answer is great because it's flirty (;)) – Nic Hartley Jun 2 '16 at 14:28 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.) • You can drop both occurrences of int, saving 8 bytes. – Lynn Jun 1 '16 at 16:48 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. 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! • Wow! I didn't expect that! – levanth Jun 2 '16 at 14:25 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 • I like the way that this formulation avoids the leading zero. – Neil Jun 1 '16 at 19:14 • @Neil the other one could avoid it by using eval – Blue Jun 2 '16 at 16:50 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.

• You can save 3 bytes: param($n)for($a=$n+1;([char[]]"$a"-join'+'|iex)-$n){$a++}$a – mazzy Sep 18 '18 at 10:16 Pyke, 98 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 • Tested again, your solution gives not the correct output for the inputs 1 to 8 – levanth Jun 1 '16 at 12:17 • I think I broke it... Works except for the number 1. Btw why does Missing arg to Equals, evaling input come up? I mean I give it an input number – levanth Jun 1 '16 at 17:53 • @levanth That happens because by default the web interface has warnings turned on. I've just coded a way to turn that off (like 10 mins ago). As for why it didn't work for 1, I was checking to see if the number was bigger than 10 and if so continuing. – Blue Jun 1 '16 at 18:29 JavaScript (ES2015), 4539 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) • ~~(v/9) => v/9|0, '1'+v-1 => v+9 – Qwertiy Jun 1 '16 at 14:55 • @Qwertiy Thank you very much. I need to learn more about bitwise operators. About the second change, it looks like I overcomplicated the case for v <= 9. I'll think if I can return all numeric values, which could be another byte-saver (no .repeat() and wrapping return value in +()). – Leibrug Jun 1 '16 at 16:47 • You don't need to name the function as per our rules – Conor O'Brien Jun 1 '16 at 17:44 • v>9 is 2 bytes shorter, string.repeat will floor a decimal value no |0 needed – Shaun H Jun 1 '16 at 19:24 • Also differs from my answer by not using ** of course. – Neil Jun 2 '16 at 17:07 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) • What does the '...+0' do...? Does it cast the input to an integer? – Yytsi Jun 3 '16 at 13:10 • Yep, to a number (Lua before 5.3 only used doubles, like JavaScript). Lua will automatically convert strings to numbers in expressions, but not comparisons. So in order for n>9 to work properly it needs to be coerced to a number first. – PiGuy Jun 3 '16 at 16:37 • +1! I see. So ...+0>9 would work? – Yytsi Jun 3 '16 at 16:43 • Yep! It would :) – PiGuy Jun 3 '16 at 16:49 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))) 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$..\ • This seems to work? Still looks golfable. – FryAmTheEggman Jun 6 '16 at 15:35 • @FryAmTheEggman Nice work! 2 minutes after posting this I thought of a much better way to do, well, pretty much everything. Tunnel vision, probably? I'm working on a revised version. – Sok Jun 6 '16 at 15:37 • Thanks :) Just an FYI people often chat about Hexagony in the esoteric programming languages room. Join in if you want :) – FryAmTheEggman Jun 6 '16 at 15:43 • Managed to smoosh it in a bit more: hexagony.tryitonline.net/… – FryAmTheEggman Jun 6 '16 at 20:15 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 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` • If anyone is interested: The fix would be seven bytes longer, replace String c(int n){return""+(n>9?(n%9)+s(n):n+9);} with int c(int n){return Integer.parseInt((n>9?(n%9)+s(n):n+9));} – levanth Jun 1 '16 at 10:31 • @levanth I've edited it in. Btw, you forgot the ""+ in int c(int n){return Integer.parseInt(""+(n>9?(n%9)+s(n):n+9));} – Kevin Cruijssen Jun 1 '16 at 10:56 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} • I don't know ruby that much but is the -> at the start an anonymous function? – levanth Jun 1 '16 at 14:38 • @levanth: yes. I will clarify above – MegaTom Jun 1 '16 at 14:40 • Does not work for n=9 – G B Sep 19 '18 at 11:05 • @GB thank you for pointing that out. It is now fixed. – MegaTom Sep 20 '18 at 1:12 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 • I know this is an older answer, but you can solve it in 7 bytes now with implicit input (just skip the first k). – maxb Sep 27 '18 at 12:00 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. 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; } PHP, 77 characters$n=$argv[1];$m=$n+1;while(1){if(array_sum(str_split($m))==$n)die("$m");$m++;} 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 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) Japt, 9 bytes @¶Xìx}aUÄ Try it 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)