A raiz digital (também soma digital repetida) de um número inteiro positivo é o valor (um dígito) obtido por um processo iterativo de soma de dígitos, em cada iteração usando o resultado da iteração anterior para calcular uma soma de dígitos. O processo continua até que um número de um dígito seja alcançado.

Por exemplo, a raiz digital de 65536 é 7 , porque 6 + 5 + 5 + 3 + 6 = 25 e 2 + 5 = 7 .

Classificar todas as raízes digitais não faz muito sentido, uma vez que começaria com infinitos 1 s.

Em vez disso, criaremos listas de todos os números inteiros de um dígito, juntamente com suas raízes digitais, depois todos os números de dois dígitos, juntamente com suas raízes digitais, depois os triplos, quádruplos e assim por diante.

Agora, para cada uma dessas listas, classificaremos para que todos os números inteiros com raízes digitais de 1 apareçam primeiro, depois todos os números inteiros com raízes digitais de 2 e assim por diante. A classificação será estável, de modo que a lista de números inteiros com determinadas raízes digitais deve estar em ordem crescente após a classificação.

Por fim, concatenaremos essas listas em uma única sequência. Essa sequência começará com todos os números de um dígito, depois todos os números de dois dígitos (classificados por sua raiz digital), depois todos os números de três dígitos e assim por diante.

Desafio:

Pegue um número inteiro positivo n como entrada e imprima o número n- ésimo na sequência descrita acima. Você pode escolher se a lista é 0 - indexada a 1 - indexada.

A sequência é assim:

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

Casos de teste:

Os casos de teste são 1 indexados.

   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

Mais fácil de copiar:

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

Esclarecimentos:

• Você não pode produzir todos os n primeiros elementos. Você deve apenas produzir o n 'ésimo.
• Teoricamente, o código deve funcionar para todos os números inteiros até 10 ^ 9 , mas não há problema se o tempo limite exceder o TIO (ou outros intérpretes com restrições de tempo) para entradas maiores que 999 .
• As explicações são incentivadas.

É código-golfe , então o código mais curto em cada idioma vence! Não desanime com outras soluções no idioma em que deseja jogar golfe, mesmo que sejam menores do que o que você pode gerenciar!

Python 2 , _{78 60 52 46} 45 bytes

-6 bytes graças a GB .
-1 byte graças a Jakob .

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

Experimente online!

Finalmente chegou a um formulário fechado, indexado em 1.

Python 2 , 78 bytes

Indexado a 0.

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

Experimente online!

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)

Experimente online!

1 indexado. Este é o melhor que eu pude gerenciar no Python 3 (bem, exceto pelo 78-byter , que é uma porta da minha solução Python 2 abaixo; acho que este é muito mais interessante). Os programas completos do Python 2 são vantajosos para esse desafio em particular, porque input()precisa de uma conversão para intno Python 3 (+5 bytes), execé uma função, e não uma instrução (+2 bytes) e /executa a divisão inteira por padrão se seus argumentos forem inteiros em Py 2 (+1 byte), então isso é definitivamente mais curto do que responder à resposta dos ovs .

Como funciona

Configuração

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

Isso define uma função recursiva f que recebe um argumento inteiro ie outro, k , cujo padrão é 1 . Enquanto k ≤ i , a função f retorna f (i, 10k) , multiplicando k por 10 a cada vez até que se torne maior que i .

Alcance alvo e indexação correta

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

Após esse conjunto de operações, ficamos com i , a entrada inicial e a variável k, que representa a menor potência de 10 maior que i . Dessa forma, somos capazes de gerar o intervalo (inteiro) [floor (k / 10), k) , que basicamente inclui todos os números inteiros que são:

• maior ou igual à potência mais alta de 10 menor ou igual a i
• menor que k , a menor potência de 10 maior que i

Como desconsideramos os números inteiros menores que x = floor (k / 10) , devemos mudar a indexação para que contabilizemos os números ausentes. A maneira óbvia é subtrair sua contagem, x , de i , para indexarmos na lista (após a classificação, que é descrita abaixo), tendo, portanto, ix . No entanto, como a lista contém 9k / 10 , itens e a indexação em uma lista no índice -y, para alguns y positivos, produz o y- ^ésimo elemento do final do Python, isso é simplesmente equivalente à indexação com ik , economizando 4 bytes.

Classificando cada pedaço pela raiz digital

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

A fórmula da função raiz digital é 1 + ((n-1) mod 9) (consulte a seção Fórmula de congruência deste artigo da Wikipedia ). Como 1 seria adicionado a cada um deles, é supérfluo ao classificar, então ficamos com o (n-1) mod 9 . A maneira como o %operador do Python funciona quando recebem números negativos no RHS é muito conveniente, porque podemos usar n pymod -9 para salvar ainda mais um byte.

Python 2 , 72 bytes

Inspirado pela submissão de Chas Brown .

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

Experimente online!

Python 2 , 73 71 70 bytes

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

Experimente online!

2 bytes thx para o Sr. XCoder ; e 1 byte thx para H.PWiz .

Este é o índice 0.

Geléia ,  15 14 10  9 bytes

D,Ḣ$‘Ḍḅ9’

Experimente online!

Quão?

Usa uma versão em golf da solução de formulário fechado criada por ovs em sua resposta em Python ...

A fórmula exposta por ovs é: 9 * (n% b) + (n / b) + b - 1 que b = 10 ^{andar (log (n, 10))}

Agora, se c é a contagem de dígitos decimais de n, então b-1 é c-1 noves em decimal.
É igual a nove vezes o valor de c-1 ones em decimal (por exemplo 111*9=999).

Além disso, n / b é o dígito à frente de n e n% b é o restante dos dígitos como um número decimal.

Uma fórmula como b * x + y pode ser implementada como uma conversão da [x,y]base b
(ou seja, b ^ 1 * x + b ^ 0 * y = b * x + y )

Como tal, podemos pegar um número, n (por exemplo 7045), dividi-lo nos dígitos inicial e final, colocando o dígito inicial no final ( [[0,4,5],7]), adicionar um a todos os dígitos do primeiro item para atender à adição de b-1 ( [[1,5,6],7]) converte-os das listas decimais em números inteiros ( [156,7]) e converte-os da base nove (1411 ).

Na implementação abaixo, adicionamos um a todos os dígitos de ambos os itens ao atender b-1 ( [[0,4,5],8]), convertemos de listas decimais em números inteiros ( [156,8]), convertemos da base nove ( 1412) e subtraímos o que esse processo adicionou ( 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

Anterior, 14 byter:

æċ⁵DL,’%9ƊƲÞị@

Experimente online!

Este constrói a lista até a próxima potência de 10 acima da entrada, classificando esses números naturais e, em [digitalRoot, digitCount]seguida, localiza o valor no índice inserido.

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]!!)

Experimente online! Indexado a 0.

Explicação:

A compreensão da lista gera a sequência como lista infinita na qual indexamos !!:

• x é um a menos que o número atual de dígitos e é extraído da lista infinita [0,1,2,3, ...]
• iitera no intervalo de 1a9 e é utilizado para a classificação por as raízes digitais
• nitera sobre todos os números com x+1dígitos
• until(<10)(sum.map(read.pure).show)calcula a raiz digital ( veja aqui uma explicação )
• né adicionado à lista se sua raiz digital for igual i.

Retina , 65 bytes

.
9
.+
*
L$`
$`
O$`_(_{9})*(_*)
$2
_+
$.&
N$`
$.&
"$+L`^|\d+"^~G`

Experimente online! 1 indexado. Explicação:

.
9
.+
*
L$`
$`

Construa uma lista de linhas de _s de 0 até a próxima potência de 10 (exclusiva).

O$`_(_{9})*(_*)
$2

Classifique todos eles em ordem de raiz digital.

_+
$.&

Converta de unário para decimal.

N$`
$.&

Classifique-os em ordem de comprimento.

"$+L`^|\d+"^~G`

Extraia o nelemento th.

Pitão ,  36 31 25 24 23  22 bytes

1 indexado.

@o%tN9rFK^LThBlt`Q-QhK

Suíte de teste!

Como funciona (desatualizado)

@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

Porta da minha resposta Python .

-6 bytes (!) Graças a Kevin Cruijssen .

g<°©‰`9*®O<

Experimente 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

Pitão , 23 bytes

@o%tN9rF_mJ^TsdtBl`Q-QJ

Experimente aqui.

-3 graças a Mr. Xcoder

1 indexado.

Perl 6 ,  68  58 bytes

{({|(10**$++..^10**++$).sort({({.comb.sum}…*==*).tail})}…*)[$_]}

Teste com base em 0

{sort({.chars,({.comb.sum}…*==*).tail},^10**.chars)[$_]}

Teste com base em 1

Expandido:

{  # 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}

Experimente online!

Originalmente, uma porta da excelente resposta Python de ovs e depois simplificava um pouco mais.

Java 8, 68 bytes

n->{int b=(int)Math.pow(10,(n+"").length()-1);return~-b+n/b+n%b*9;}

Porta chata da resposta do @ovs 'Python 2 , portanto, certifique-se de votar nele!
-1 byte graças a @Jakob

Experimente online.

K4 , 38 bytes

Solução:

-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:

Exemplos:

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

Explicação:

A solução do porto de Jonathan Allan, quando eu ficar sem memória, construindo as raízes digitais de 1 a 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

Bônus:

A tradução da solução dos ovs é mais simples, mas mais longa:

-1+b+/1 9*(_%;.q.mod).\:x,b:10 xexp#1_$x:

Geléia , 19 bytes

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

Experimente online!

-1 graças a Mr. Xcoder .

1 indexado.

J, 24 bytes

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

Este tácito expressão é agrupada em parênteses para significar que deve ser tratada por si só e não como parte de qualquer expressão a seguir (como os argumentos).

A frase '] /:' ordena (ascendente '/:') a matriz original ']' pela soma '+ /' dos dígitos A expressão

". &> ":

converte um número em um vetor de caracteres com '":' e aplica seu inverso '".' - caractere para número - aplicado a cada item '&>'. Portanto, 65536 -> '65536' -> 6 5 5 3 6.

A conjunção de potência '^:' perto do final da expressão aplica o código que acabamos de explicar (à esquerda) um número especificado de vezes. Nesse caso, o número especificado de vezes é o infinito '_', o que significa continuar aplicando até que o resultado pare de mudar.

O final "" 0 "significa aplicar toda a expressão à esquerda em cada item escalar (0-dimensional) à direita, que seria a matriz de números à qual queremos aplicar isso.

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

Experimente online!

Explicação recebida (lentamente)! Acho que não pode ficar muito mais curto que isso, mas estou sempre aberto a sugestões

Perl 5 -pF , 27 bytes

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

Experimente online!

Usa a fórmula de @ ovs e as explicações de @ JonathanAllen para criar um bom código compacto.