La racine numérique (également la somme numérique répétée) d'un entier positif est la valeur (à un chiffre) obtenue par un processus itératif de sommation de chiffres, à chaque itération en utilisant le résultat de l'itération précédente pour calculer une somme de chiffres. Le processus se poursuit jusqu'à ce qu'un nombre à un chiffre soit atteint.

Par exemple, la racine numérique de 65536 est 7 , car 6 + 5 + 5 + 3 + 6 = 25 et 2 + 5 = 7 .

Le tri de toutes les racines numériques n'a pas beaucoup de sens, car il ne ferait que commencer par une infinité de 1 s.

Au lieu de cela, nous allons créer des listes de tous les entiers à un chiffre avec leurs racines numériques, puis tous les nombres à deux chiffres avec leurs racines numériques, puis le triple, le quadruple et ainsi de suite.

Maintenant, pour chacune de ces listes, nous allons le trier de sorte que tous les entiers avec des racines numériques de 1 apparaissent en premier, puis tous les entiers avec des racines numériques de 2 et ainsi de suite. Le tri sera stable, de sorte que la liste des entiers avec certaines racines numériques devrait être dans l'ordre croissant après le tri.

Enfin, nous allons concaténer ces listes en une seule séquence. Cette séquence commencera avec tous les numéros à un chiffre, puis tous les numéros à deux chiffres (triés par leur racine numérique), puis tous les numéros à trois chiffres et ainsi de suite.

Défi:

Prendre un positif entier n en entrée, et la sortie du n -ième nombre dans la séquence décrite ci - dessus. Vous pouvez choisir si la liste est indexée sur 0 ou indexée sur 1 .

La séquence se déroule comme suit:

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

Cas de test:

Les cas de test sont indexés 1.

   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

Plus facile à copier:

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

Précisions:

• Vous ne pouvez pas afficher tous les n premiers éléments. Tu ne la sortie n « e.
• Le code doit théoriquement fonctionner pour tous les entiers jusqu'à 10 ^ 9 , mais c'est OK s'il expire sur TIO (ou d'autres interprètes avec des restrictions de temps) pour des entrées supérieures à 999 .
• Des explications sont encouragées.

C'est le code-golf , donc le code le plus court dans chaque langue gagne! Ne soyez pas découragé par d'autres solutions dans la langue dans laquelle vous voulez jouer au golf, même si elles sont plus courtes que ce que vous pouvez gérer!

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

-6 octets grâce à GB .
-1 octet merci à Jakob .

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

Essayez-le en ligne!

Enfin atteint une forme fermée, 1-indexée.

Python 2 , 78 octets

0 indexé.

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

Essayez-le en ligne!

Python 3 , 80 octets

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)

Essayez-le en ligne!

1 indexé. C'est le meilleur que j'ai pu gérer en Python 3 (enfin, à l'exception du 78 octets , qui est un port de ma solution Python 2 ci-dessous; je pense que celui-ci est beaucoup plus cool, cependant). Les programmes complets Python 2 sont avantagés pour ce défi particulier, car input()nécessite une conversion inten Python 3 (+5 octets), execest une fonction plutôt qu'une instruction (+2 octets) et /effectue une division entière par défaut si ses arguments sont des entiers dans Py 2 (+1 octet), donc c'est certainement plus court que le portage de la réponse des ovs .

Comment ça marche

Installer

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

Ceci définit une fonction récursive f qui prend un argument entier i et un autre, k , par défaut à 1 . Alors que k ≤ i , la fonction f renvoie f (i, 10k) , multipliant k par 10 à chaque fois jusqu'à ce qu'elle devienne supérieure à i .

Plage cible et indexation correcte

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

Après cet ensemble d'opérations, on se retrouve avec i , l'entrée initiale et la variable k qui représente la plus petite puissance de 10 supérieure à i . De cette façon, nous pouvons générer la plage (entière) [floor (k / 10), k) , qui comprend essentiellement tous les entiers qui sont:

• supérieur ou égal à la puissance la plus élevée de 10 inférieur ou égal à i
• inférieur à k , la plus petite puissance de 10 supérieure à i

Puisque nous ne tenons pas compte des entiers inférieurs à x = plancher (k / 10) , nous devons décaler l'indexation pour tenir compte des nombres manquants. La façon la plus évidente est de soustraire leur nombre, x , de i , de sorte que nous indexions dans la liste (après le tri, qui est décrit ci-dessous), ayant donc ix . Cependant, étant donné que la liste contient 9k / 10 , les éléments et l' indexation dans une liste à l' index -y pour certaines positives y donne le y ^ième élément de la fin en Python, cela est tout simplement équivalent à l' indexation avec ik , d'où un gain de 4 octets.

Tri de chaque morceau par la racine numérique

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

La formule de la fonction racine numérique est 1 + ((n-1) mod 9) (voir la section Formule de congruence de cet article Wikipedia ). Comme 1 serait ainsi ajouté à chacun d'eux, il est superflu lors du tri, nous nous retrouvons donc avec (n-1) mod 9 . La façon dont l' %opérateur de Python fonctionne avec des nombres négatifs sur le RHS est très pratique, car nous pouvons utiliser n pymod -9 à la place pour enregistrer encore un octet d'anthère.

Python 2 , 72 octets

Inspiré par la soumission de Chas Brown .

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

Essayez-le en ligne!

Python 2 , 73 71 70 octets

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

Essayez-le en ligne!

2 octets de thx à M. XCoder ; et 1 octet thx à H.PWiz .

Ceci est indexé 0.

Gelée ,  15 14 10  9 octets

D,Ḣ$‘Ḍḅ9’

Essayez-le en ligne!

Comment?

Utilise une version golfée de la solution de forme fermée créée par les ovs dans leur réponse Python ...

La formule exposée par ovs est: 9 * (n% b) + (n / b) + b - 1 où b = 10 ^{étage (log (n, 10))}

Maintenant, si c est le nombre de chiffres décimaux de n, alors b-1 est c-1 neuf en décimal.
C'est la même chose que neuf fois la valeur de c-1 en décimal (par exemple 111*9=999).

De plus, n / b est le premier chiffre de n et n% b est le reste des chiffres sous forme de nombre décimal.

Une formule comme b * x + y peut être implémentée comme une conversion de la [x,y]base b
(c'est-à-dire b ^ 1 * x + b ^ 0 * y = b * x + y )

En tant que tel, nous pouvons prendre un nombre, n (par exemple 7045), le diviser en [[0,4,5],7]chiffres de début et de fin, en plaçant le chiffre de tête à la fin ( ), ajouter un à tous les chiffres du premier élément pour répondre à l'ajout de b-1 ( [[1,5,6],7]) les convertit des listes décimales en entiers ( [156,7]), et les convertit en base neuf ( 1411).

Dans l'implémentation ci-dessous, nous ajoutons un à tous les chiffres des deux éléments lors de la restauration de b-1 ( [[0,4,5],8]), convertissons des listes décimales en nombres entiers ( [156,8]), convertissons de la base neuf ( 1412), puis soustrayons celui ajouté par ce processus ( 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

Précédent, 14 octets:

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

Essayez-le en ligne!

Celui-ci construit la liste jusqu'à la puissance suivante de 10 au-dessus de l'entrée en triant ces nombres naturels [digitalRoot, digitCount]puis trouve la valeur à l'index entré.

Haskell , 94 88 octets

([n|x<-[0..],i<-[1..9],n<-[10^x..10^(x+1)-1],until(<10)(sum.map(read.pure).show)n==i]!!)

Essayez-le en ligne! 0 indexé.

Explication:

La compréhension de la liste génère la séquence sous forme de liste infinie dans laquelle nous indexons avec !!:

• x est un de moins que le nombre actuel de chiffres et est tiré de la liste infinie [0,1,2,3, ...]
• iitère sur la plage de 1à 9et est utilisé pour le tri par les racines numériques
• nitère sur tous les nombres avec des x+1chiffres
• until(<10)(sum.map(read.pure).show)calcule la racine numérique ( voir ici pour une explication )
• nest ajouté à la liste si sa racine numérique est égale à i.

Rétine , 65 octets

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

Essayez-le en ligne! 1 indexé. Explication:

.
9
.+
*
L$`
$`

Construisez une liste de lignes de _s de 0 jusqu'à la prochaine puissance de 10 (exclusif).

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

Triez-les tous par ordre de racine numérique.

_+
$.&

Convertissez de unaire en décimal.

N$`
$.&

Triez-les par ordre de longueur.

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

Extraire le ne élément.

Pyth ,  36 31 25 24 23  22 octets

1 indexé.

@o%tN9rFK^LThBlt`Q-QhK

Suite de tests!

Comment ça marche (obsolète)

@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 octets

Port de ma réponse Python .

-6 octets (!) Grâce à Kevin Cruijssen .

g<°©‰`9*®O<

Essayez-le en ligne!

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 octets

@o%tN9rF_mJ^TsdtBl`Q-QJ

Essayez-le ici.

-3 grâce à M. Xcoder

1 indexé.

Perl 6 ,  68  58 octets

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

Testez -le sur la base de 0

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

Testez-le 1

Étendu:

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

Rubis , 43 38 octets

->x{9*(x%b=10**~-x.to_s.size)+x/b+b-1}

Essayez-le en ligne!

Initialement, un port de l'excellente réponse Python par ovs, puis simplifié un peu plus.

Java 8, 68 octets

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

Port ennuyeux de la réponse Python 2 de @ovs , alors assurez-vous de lui donner un vote positif!
-1 octet grâce à @Jakob

Essayez-le en ligne.

K4 , 38 octets

Solution:

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

Exemples:

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

Explication:

Port de la solution de Jonathan Allan alors que je manque de mémoire pour construire les racines numériques de 1 à 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

Prime:

La traduction de la solution ovs est plus simple mais plus longue:

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

Gelée , 19 octets

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

Essayez-le en ligne!

-1 grâce à M. Xcoder .

1 indexé.

J, 24 octets

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

Cette expression tacite est entourée de parens pour signifier qu'elle doit être traitée seule plutôt que comme faisant partie d'une expression suivante (comme les arguments).

L'expression '] /:' ordonne (ascendant '/:') le tableau d'origine ']' par la somme '+ /' des chiffres L'expression

". &> ":

convertit un nombre en un vecteur de caractères avec '":', puis applique son inverse '".' - caractère à numéro - appliqué à chaque élément '&>'. Donc, 65536 -> '65536' -> 6 5 5 3 6.

La conjonction de puissance '^:' vers la fin de l'expression applique le code que nous venons d'expliquer (à gauche) un nombre spécifié de fois. Dans ce cas, le nombre spécifié de fois est l'infini «_», ce qui signifie de continuer à appliquer jusqu'à ce que le résultat cesse de changer.

Le dernier «0» signifie appliquer l'expression entière à gauche à chaque élément scalaire (0 dimensionnel) à droite, qui serait le tableau de nombres auquel nous voulons l'appliquer.

Elixir , 239 octets

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

Essayez-le en ligne!

Explication entrante (lentement)! Je ne pense pas que cela puisse être beaucoup plus court que cela, mais je suis toujours ouvert aux suggestions

Perl 5 -pF , 27 octets

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

Essayez-le en ligne!

Utilise la formule de @ ovs et les explications de @ JonathanAllen pour trouver un joli morceau de code compact.