# Integers sorted by their digital roots

The digital root (also repeated digital sum) of a positive integer is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.

For example, the digital root of 65536 is 7, because 6 + 5 + 5 + 3 + 6 = 25 and 2 + 5 = 7.

Sorting all digital roots doesn't make much sense, since it would just start with infinitely many 1s.

Instead, we'll create lists of all the single digits integers along with their digital roots, then all double digit numbers along with their digital roots, then the triple, quadruple and so on.

Now, for each of those lists, we'll sort it so that all the integers with digital roots of 1 appear first, then all integers with digital roots of 2 and so on. The sorting will be stable, so that the list of integers with a certain digital roots should be in ascending order after the sorting.

Finally we'll concatenate these lists into one single sequence. This sequence will start with all single digit numbers, then all double digit numbers (sorted by their digital root), then all triple digit numbers and so on.

### Challenge:

Take a positive integer n as input, and output the n'th number in the sequence described above. You may choose if the list is 0-indexed of 1-indexed.

The sequence goes like this:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 28, 37, 46, 55, 64, 73, 82, 91, 11, 20, 29 ...
72, 81, 90, 99, 100, 109, 118, ...
981, 990, 999, 1000, 1009, 1018, 1027, ...


### Test cases:

The test cases are 1-indexed.

   n   f(n)
9      9
10     10
11     19
40     13
41     22
42     31
43     40
44     49
45     58
600    105
601    114
602    123
603    132
604    141
605    150
4050   1453
4051   1462
4052   1471
4053   1480
4054   1489
4055   1498


Easier to copy:

n =    9, 10, 11, 40, 41, 42, 43, 44, 45, 600, 601, 602, 603, 604, 605, 4050, 4051, 4052, 4053, 4054, 4055,
f(n) = 9, 10, 19, 13, 22, 31, 40, 49, 58, 105, 114, 123, 132, 141, 150, 1453, 1462, 1471, 1480, 1489, 1498


### Clarifications:

• You may not output all n first elements. You shall only output the n'th.
• The code must theoretically work for all integers up to 10^9, but it's OK if it times out on TIO (or other interpreters with time restrictions) for inputs larger than 999.
• Explanations are encouraged.

It's , so the shortest code in each language wins! Don't be discouraged by other solutions in the language you want to golf in, even if they are shorter than what you can manage!

• Fun note: this is not in OEIS yet – apnorton Jun 19 '18 at 2:57

# Python 2, 78 60 52 46 45 bytes

-6 bytes thanks to G B.
-1 byte thanks to Jakob.

n=input()
b=10**~-len(n)
print~-b+n/b+n%b*9


Try it online!

Finally reached a closed form, 1-indexed.

# Python 2, 78 bytes

0-indexed.

d=10;k=1
exec'\nk+=9\nif k>d+7:k=d;d*=10\nif k>=d:k-=d/10*9-1'*input()
print k


Try it online!

• I was hoping to see a solution that didn't create the entire sequence. Well done :-) – Stewie Griffin Jun 18 '18 at 8:56
• How did you derive the closed form solution? (edit: looks like there's an explanation on wikipedia) – sevko Jun 18 '18 at 16:30
• @sevko The 78-byter was my original solution (somewhat ungolfed variant here). This already works without calculating any cube roots, but rather by generating the sequence number by number, based on rules I observed in the sequence. Based on this iterative calculations one can count how many times each expression gets executed. – ovs Jun 18 '18 at 17:24
• @sevko with the help of WolframAlpha I was able to construct a closed form. At first the program using the closed form was a lot longer (~95 bytes) but with some golfing and WolframAlpha this got to its current form. – ovs Jun 18 '18 at 17:27

# Python 3, 80 bytes

f=lambda i,k=1:k>i and sorted(range(k//10,k),key=lambda n:n%-9)[i-k]or f(i,k*10)


Try it online!

1-indexed. This is the best I could manage in Python 3 (well, except for the 78-byter, which is a port of my Python 2 solution below; I think this one is much cooler, though). Python 2 full programs are advantaged for this particular challenge, because input() needs a conversion to int in Python 3 (+5 bytes), exec is a function, rather than a statement (+2 bytes) and / performs integer division by default if its arguments are integers in Py 2 (+1 byte), so this is definitely shorter than porting ovs' answer.

## How it works

Setup

f=lambda i,k=1:k>i and ... or f(i,k*10)


This defines a recursive function f that takes one integer argument i and another one, k, which defaults to 1. While k ≤ i, the function f returns f(i,10k), multiplying k by 10 each time until it becomes greater than i.

Target range and correct indexing

...range(k//10,k)...[i-k]


After this set of operation, we're left with i, the initial input and the variable k which represents the smallest power of 10 greater than i. This way, we are able to generate the (integer) range [floor(k/10), k), which basically includes all integers that are:

• greater than or equal to the highest power of 10 less than or equal to i
• less than k, the smallest power of 10 greater than i

Since we disregard the integers smaller than x = floor(k/10), we must shift the indexing so that we account for the missing numbers. The obvious way is to subtract their count, x, from i, so that we index into the list (after sorting, which is described below), therefore having i-x. However, since the list contains 9k/10, items, and indexing in a list at index -y for some positive y yields the yth element from the end in Python, this is simply equivalent to indexing with i-k, hence saving 4 bytes.

Sorting each chunk by the digital root

sorted(...,key=lambda n:n%-9)


The formula for the digital root function is 1+((n-1) mod 9) (see the Congruence formula section of this Wikipedia article). As 1 would this way be added to each of them, it is superfluous when sorting, so we're left with (n-1) mod 9. The way Python's % operator works when given negative numbers on the RHS is very convenient, because we can use n pymod -9 instead to save yet anther byte.

# Python 2, 72 bytes

Inspired by Chas Brown's submission.

lambda i:sorted(range(1,10**len(i)),key=lambda n:(len(n),n%-9))[i-1]


Try it online!

# Python 2, 7371 70 bytes

lambda n:sorted(range(10**len(n)),key=lambda i:(len(~i),i%9))[n]+1


Try it online!

2 bytes thx to Mr. XCoder; and 1 byte thx to H.PWiz.

This is 0-indexed.

• Well, i%9 should be sufficient instead of i%9+1... this way you beat my 72 byter :DD: – Mr. Xcoder Jun 17 '18 at 19:15
• @Mr.Xcoder: Ha! You're right... – Chas Brown Jun 17 '18 at 19:16
• len(~i) should work – H.PWiz Jun 17 '18 at 20:48

# Jelly,  15 14 10  9 bytes

D,Ḣ$‘Ḍḅ9’  Try it online! ### How? Uses a golfed version of the closed-form solution created by ovs in their Python answer... The formula exposed by ovs is: 9*(n%b) + (n/b) + b - 1 where b=10floor(log(n,10)) Now if c is the count of decimal digits of n then b-1 is c-1 nines in decimal. This is the same as nine times the value of c-1 ones in decimal (e.g. 111*9=999). Furthermore n/b is the leading digit of n and n%b is the rest of the digits as a decimal number. A formula like b*x+y may be implemented as a conversion of [x,y] from base b (i.e. b^1*x + b^0*y = b*x+y) As such we can take a number, n (for example 7045), split it into the leading and trailing digits, placing the leading digit at the end ([[0,4,5],7]), add one to all of the digits of the first item to cater for the addition of b-1 ([[1,5,6],7]) convert these from decimal lists to integers ([156,7]), and convert that from base nine (1411). In the implementation below we add one to all of the digits of both items when catering for b-1 ([[0,4,5],8]), convert from decimal lists to integers ([156,8]), convert from base nine (1412) and then subtract the one this process added (1411). D,Ḣ$‘Ḍḅ9’ - Link: positive integer, n    e.g. 4091
D         - to base ten                       [4, 0, 9, 1]
$- last two links as a monad: Ḣ - head (modifies the list too) 4 , - pair (the modified list) with [[0, 9, 1], 4] ‘ - increment (vectorises) [[1, 10, 2], 5] Ḍ - from base ten (vectorises) [202, 5] (since 1*10^2+10*10^1+2*10^0 = 100+100+2 = 202) ḅ9 - convert from base 9 1823 (since 202*9^1 + 5*9^0 = 202*9 + 6*9 = 1818 + 5 = 1823) ’ - decrement 1822  Previous, 14 byter: æċ⁵DL,’%9ƊƲÞị@  Try it online! This one builds the list up to the next power of 10 above the input by sorting these natural numbers by [digitalRoot, digitCount] then finds the value at the inputted index. # Haskell, 94 88 bytes ([n|x<-[0..],i<-[1..9],n<-[10^x..10^(x+1)-1],until(<10)(sum.map(read.pure).show)n==i]!!)  Try it online! 0-indexed. Explanation: The list comprehension generates the sequence as infinite list in which we index with !!: • x is one less than the current number of digits and is drawn from the infinite list [0,1,2,3, ...] • i iterates over the range from 1 to 9 and is used for sorting by the digital roots • n iterates over all numbers with x+1 digits • until(<10)(sum.map(read.pure).show) computes the digital root (see here for an explanation) • n is added to the list if its digital root equals i. # Retina, 65 bytes . 9 .+ * L$
$ O$_(_{9})*(_*)
$2 _+$.&
N$$.&
"$+L^|\d+"^~G  Try it online! 1-indexed. Explanation: . 9 .+ * L$
$  Build up a list of lines of _s from 0 until the next power of 10 (exclusive). O$_(_{9})*(_*)
$2  Sort them all in order of digital root. _+$.&


Convert from unary to decimal.

N$$.&


Sort them in order of length.

"$+L^|\d+"^~G  Extract the nth element. # Pyth, 36 31 25 24 23 22 bytes 1-indexed. @o%tN9rFK^LThBltQ-QhK  Test suite! ### How it works (outdated) @smo%tN9dcU^TKhs.lQT^LTSK – Full program. Q = input. Khs.lQT – Take floor(log10(Q))+1 and store it in K. U^T – Generate [0 ... T^K). c – Cut at locations... ^LTSK – Of the powers of 10 less than K. m d – Map over those. o N – Sort them by... %t 9 – Themselves decremented, modulo 9. @s – Flatten the result and retrieve the Q'th entry.  # 05AB1E, 19 11 bytes Port of my Python answer. -6 bytes(!) thanks to Kevin Cruijssen. g<°©‰9*®O<  Try it online! Code Explanation Stack implicit input [n] g length [len(n)] < decrement [len(n)-1] ° 10 ** a [10**(len(n) - 1)] © store value [10**(len(n) - 1)] ‰ divmod [[n // 10**(len(n) - 1), n % 10**(len(n) - 1)]]  push items to stack [n // 10**(len(n) - 1), n % 10**(len(n) - 1)] 9* multiply by 9 [n // 10**(len(n) - 1), n % 10**(len(n) - 1) * 9] ® retrieve value [n // 10**(len(n) - 1), n % 10**(len(n) - 1) * 9, 10**(len(n) - 1)] O sum the stack [n // 10**(len(n) - 1) + n % 10**(len(n) - 1) * 9 + 10**(len(n) - 1)] < decrement [n // 10**(len(n) - 1) + n % 10**(len(n) - 1) * 9 + 10**(len(n) - 1) - 1] implicit output  # Pyth, 23 bytes @o%tN9rF_mJ^TsdtBlQ-QJ  Try it here. -3 thanks to Mr. Xcoder 1-indexed. # Perl 6, 68 58 bytes {({|(10**$++..^10**++$).sort({({.comb.sum}…*==*).tail})}…*)[$_]}


Test it 0-based

{sort({.chars,({.comb.sum}…*==*).tail},^10**.chars)[$_]}  Test it 1-based ## Expanded: { # bare block lambda with implicit parameter$_

sort(
{
.chars,         # sort by the length first

(  # generate sequence to find digital sum

{ .comb.sum } # one round of digital sum
… * == *      # stop when the digital sum matches itself (1..9)

).tail          # get the last value
},

^                 # Range up to (and excluding)
10 ** .chars    # the next power of 10

)[ $_ ] # index into the sequence }  # Ruby, 43 38 bytes ->x{9*(x%b=10**~-x.to_s.size)+x/b+b-1}  Try it online! Originally a port of the excellent Python answer by ovs, then simplified some more. # Java 8, 68 bytes n->{int b=(int)Math.pow(10,(n+"").length()-1);return~-b+n/b+n%b*9;}  Boring port of @ovs' Python 2 answer, so make sure to upvote him! -1 byte thanks to @Jakob Try it online. # K4, 38 bytes Solution: -1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:  Examples: q)k)-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:40 13 q)k)-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:601 114 q)k)-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:4051 1462  Explanation: Port of Jonathan Allan's solution as I run out of memory building the digital roots from 1 to 1e9. -1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\: / the solution 10\: / convert to base 10 1+ / add 1 x: / save as x # / take from x ( ) / do together #x / count x c: / save as c 1+ / add 1 1_ / drop the first _ / cut at these indices ( ; ) / 2-item list c-1 / length - 1 0 / .. zero 10/:' / convert each from base 10 9/: / convert from base 9 -1+ / subtract 1  Bonus: Translation of ovs' solution is simpler but longer: -1+b+/1 9*(_%;.q.mod).\:x,b:10 xexp#1_$x:

• It's explicitly stated that: "The code must theoretically work for all integers up to 10^9". It appears this does not...? – Stewie Griffin Jun 19 '18 at 12:26
• Urgh. Then I'll use one of the bonus answers as I'll run out of memory trying to calculate up to 10e6 let alone 10e9. Will fix later. – streetster Jun 19 '18 at 14:22

# Jelly, 19 bytes

æḟ©ræċɗ⁵Ṗ%Þ-9⁸‘_®¤ị


Try it online!

-1 thanks to Mr. Xcoder.

1-indexed.

# J, 24 bytes

(]/:([:+/[:".&>":)^:_"0)


This tacit expression is wrapped in parens to signify that it should be treated on its own rather than as part of any following expression (like the arguments).

The phrase ']/:' orders (ascending '/:') the original array ']' by the sum '+/' of the digits The expression

". &> ":


converts a number to a character vector with '":', then applies its inverse '".' - character to number - applied to each '&>' item. So, 65536 -> '65536' -> 6 5 5 3 6.

The power conjunction '^:' near the end of the expression applies the code we just explained (on the left) a specified number of times. In this case, the specified number of times is infinity '_' which means to keep applying until the result stops changing.

The final '"0' means to apply the whole expression on the left to each scalar (0-dimensional) item on the right, which would be the array of numbers to which we want to apply this.

• How are you creating the input list(s)? I'm writing a solution in K but half the answer is generating the lists... – streetster Jun 18 '18 at 19:57
• I assumed the lists are input externally. I don't see where creating the list is part of the problem. – DevonMcC Jun 25 '18 at 15:06
• "Take a positive integer n as input, and output the n'th number in the sequence described above." You have to create the sequence (or find a way to get around generating the sequence - see other answers). – streetster Jun 25 '18 at 18:26

# Elixir, 239 bytes

q=:math
e=Enum
r=fn x,f->cond do
x<10->x
1->f.(e.sum(Integer.digits x),f)end end
fn p->e.at(e.at(Stream.unfold({0,[0]},fn {a,c}->{c,{a+1,c++e.sort(trunc(q.pow 10,a)..trunc(q.pow 10,a+1)-1,&r.(&1,r)<=r.(&2,r))}}end),1+trunc q.log10 p),p)end


Try it online!

Explanation incoming (slowly)! I don't think it can get much shorter than this, but I'm always open to suggestions

# Perl 5-pF, 27 bytes

$_=9x$#F+$_%10**$#F*9+\$F[0]


Try it online!

Uses @ovs's formula and @JonathanAllen's explanations to come up with a nice compact piece of code.