Integers sorted by their digital roots

Question

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 code-golf, 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!

Answer 1

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!

Answer 2

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 y^th 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!

Answer 3

Python 2, 73 71 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.

Answer 4

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=10^{floor(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.

Answer 5

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.

Answer 6

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.

Answer 7

Pyth,  36 31 25 24 23  22 bytes

1-indexed.

@o%tN9rFK^LThBlt`Q-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.

Answer 8

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

Answer 9

Pyth, 23 bytes

@o%tN9rF_mJ^TsdtBl`Q-QJ

Try it here.

-3 thanks to Mr. Xcoder

1-indexed.

Answer 10

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
}

Answer 11

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.

Answer 12

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.

Answer 13

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:

Answer 14

Jelly, 19 bytes

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

Try it online!

-1 thanks to Mr. Xcoder.

1-indexed.

Answer 15

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.

Answer 16

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

Answer 17

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.