Die digitale Wurzel (auch wiederholte digitale Summe) einer positiven Ganzzahl ist der (einstellige) Wert, der durch einen iterativen Prozess zum Summieren von Ziffern bei jeder Iteration unter Verwendung des Ergebnisses der vorherigen Iteration zur Berechnung einer Ziffernsumme erhalten wird. Der Vorgang wird fortgesetzt, bis eine einstellige Zahl erreicht ist.

Zum Beispiel kann die digitale Wurzel 65536 ist 7 , weil 6 + 5 + 5 + 3 + 6 = 25 und 2 + 5 = 7 .

Das Sortieren aller digitalen Wurzeln ist wenig sinnvoll, da es nur mit unendlich vielen 1 beginnen würde s beginnen würde.

Stattdessen erstellen wir Listen aller einstelligen Ganzzahlen mit ihren digitalen Wurzeln, dann aller zweistelligen Zahlen mit ihren digitalen Wurzeln, dann der dreifachen, vierfachen und so weiter.

Für jede dieser Listen sortieren wir sie so, dass zuerst alle Ganzzahlen mit digitalen Wurzeln von 1 und dann alle Ganzzahlen mit digitalen Wurzeln von 2 und so weiter angezeigt werden. Die Sortierung ist stabil, sodass die Liste der Ganzzahlen mit bestimmten digitalen Wurzeln nach der Sortierung aufsteigend sortiert sein sollte.

Schließlich werden wir diese Listen zu einer einzigen Sequenz verketten. Diese Sequenz beginnt mit allen einstelligen Zahlen, dann allen zweistelligen Zahlen (sortiert nach ihrer digitalen Wurzel), dann allen dreistelligen Zahlen und so weiter.

Herausforderung:

Nehmen Sie eine positive ganze Zahl n als Eingabe und geben Sie die n -te Zahl in der oben beschriebenen Reihenfolge aus. Sie können wählen, ob die Liste ist 0 von 1 ist indiziert ist.

Die Sequenz sieht folgendermaßen aus:

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

Testfälle:

Die Testfälle sind 1-indiziert.

   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

Einfacher zu kopieren:

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

Klarstellungen:

• Sie können möglicherweise nicht alle n ersten Elemente ausgeben . Du sollst nur das ausgeben n -te aus.
• Der Code muss theoretisch für alle ganzen Zahlen bis 10 ^ 9 funktionieren , aber es ist in Ordnung, wenn bei Eingaben über 999 eine Zeitüberschreitung bei TIO (oder anderen Interpretern mit zeitlichen Einschränkungen) auftritt .
• Erklärungen sind erwünscht.

Es ist Code-Golf , also gewinnt der kürzeste Code in jeder Sprache! Lassen Sie sich nicht von anderen Lösungen in der Sprache entmutigen, in der Sie Golf spielen möchten, auch wenn sie kürzer sind als Sie es schaffen!

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

-6 Bytes dank GB .
-1 Byte danke an Jakob .

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

Probieren Sie es online!

Endlich eine geschlossene Form erreicht, 1-indiziert.

Python 2 , 78 Bytes

0-indiziert.

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

Probieren Sie es 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)

Probieren Sie es online!

1-indiziert. Dies ist das Beste, was ich in Python 3 erreichen konnte (nun, mit Ausnahme des 78-Bytes , das ein Port meiner Python 2-Lösung ist; ich denke jedoch, dass diese viel cooler ist). Python 2-Vollprogramme sind für diese besondere Herausforderung von Vorteil, da input()eine Konvertierung intin Python 3 (+5 Byte) erforderlich execist, eine Funktion und keine Anweisung (+2 Byte) ist und /standardmäßig eine Ganzzahldivision durchführt, wenn die Argumente Ganzzahlen sind Py 2 (+1 Byte), das ist also definitiv kürzer als Portierung die Antwort von ovs .

Wie es funktioniert

Installieren

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

Dies definiert eine rekursive Funktion f , die ein ganzzahliges Argument i und ein anderes, k , verwendet, das standardmäßig den Wert 1 hat . Während k ≤ i , wird die Funktion f kehrt f (i, 10K) , Multiplikation k von 10 jedes Mal , bis es wird größer als i .

Zielbereich und korrekte Indizierung

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

Nach diesem Satz von Operationen bleiben i , die anfängliche Eingabe und die Variable k übrig , die die kleinste Potenz von 10 darstellt, die größer als i ist . Auf diese Weise können wir den (ganzzahligen) Bereich [Etage (k / 10), k) generieren , der im Grunde alle ganzen Zahlen umfasst, die sind:

• größer als oder gleich der höchsten Potenz von 10 kleiner als oder gleich i
• kleiner als k , die kleinste Potenz von 10 größer als i

Da wir die Ganzzahlen, die kleiner als x = floor (k / 10) sind , nicht berücksichtigen, müssen wir die Indizierung verschieben, damit wir die fehlenden Zahlen berücksichtigen. Der naheliegende Weg besteht darin, ihre Anzahl x von i zu subtrahieren , so dass wir in die Liste (nach dem Sortieren, das unten beschrieben wird) indexieren und daher haben ix haben . Da die Liste jedoch 9k / 10 Elemente enthält und die Indizierung in einer Liste mit dem Index -y für ein positives y das y- ^te Element vom Ende in Python ergibt , entspricht dies einfach der Indizierung mit ik , wodurch 4 Bytes gespart werden.

Sortieren jedes Chunks nach der digitalen Wurzel

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

Die Formel für die digitale Wurzelfunktion lautet 1 + ((n-1) mod 9) (siehe Abschnitt Kongruenzformel in diesem Wikipedia-Artikel ). Da 1 auf diese Weise zu jedem von ihnen hinzugefügt wird, ist es beim Sortieren überflüssig, so dass (n-1) mod 9 übrig bleibt . Die Art und Weise, wie der %Operator von Python funktioniert, wenn negative Zahlen in der RHS eingegeben werden, ist sehr praktisch, da wir stattdessen n pymod -9 verwenden können, um noch ein weiteres Byte zu speichern.

Python 2 , 72 Bytes

Inspiriert von Chas Browns Vorlage .

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

Probieren Sie es online!

Python 2 , 73 71 70 Bytes

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

Probieren Sie es online!

2 Bytes danke an Mr. XCoder ; und 1 Byte thx bis H.PWiz .

Dies ist 0-indiziert.

Jelly ,  15 14 10  9 Bytes

D,Ḣ$‘Ḍḅ9’

Probieren Sie es online!

Wie?

Verwendet eine Golf-Version der geschlossenen Lösung, die Ovs in ihrer Python-Antwort erstellt haben ...

Die Formel, die durch ovs angezeigt wird, lautet: 9 * (n% b) + (n / b) + b - 1, wobei b = 10 ^{Etage (log (n, 10))}

Nun , wenn c die Anzahl der Dezimalziffern ist aus n dann b-1 ist c-1 Neunen in Dezimal.
Dies ist das Neunfache des Wertes von c-1 in Dezimalzahl (z 111*9=999. B. ).

Außerdem ist n / b die führende Ziffer von n und n% b ist der Rest der Ziffern als Dezimalzahl.

Eine Formel wie b * x + y kann als Umwandlung von [x,y]der Basis b
(dh b ^ 1 * x + b ^ 0 * y = b * x + y ) implementiert werden.

Als solche können wir eine Zahl n (zum Beispiel 7045) nehmen, sie in führende und nachfolgende Ziffern aufteilen, die führende Ziffer am Ende platzieren ( [[0,4,5],7]) und eine zu allen Ziffern des ersten Elements hinzufügen, um die Hinzufügung von zu berücksichtigen b-1 ( [[1,5,6],7]) konvertiert diese von Dezimallisten in Ganzzahlen ( [156,7]) und konvertiert diese von Basis neun (1411 ).

In der folgenden Implementierung addieren wir für b-1 ( [[0,4,5],8]) eine zu allen Ziffern beider Elemente , konvertieren von Dezimallisten in Ganzzahlen ( [156,8]), konvertieren von Basis neun ( 1412) und subtrahieren dann die von diesem Prozess hinzugefügte ( 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

Zurück, 14 byter:

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

Probieren Sie es online!

Dies baut die Liste bis zum nächsten Einschalten von 10 über dem Eingang durch diese natürlichen Zahlen durch das Sortieren [digitalRoot, digitCount]dann den Wert auf dem eingegebenen Index findet.

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

Probieren Sie es online! 0-indiziert.

Erläuterung:

Das Listenverständnis erzeugt die Reihenfolge als unendliche Liste, in der wir indizieren mit !!:

• x ist eins weniger als die aktuelle Anzahl von Ziffern und wird aus der unendlichen Liste gezogen [0,1,2,3, ...]
• iiteriert über den Bereich von 1bis9 und wird zum Sortieren nach den digitalen Wurzeln verwendet
• nDurchläuft alle Zahlen mit x+1Ziffern
• until(<10)(sum.map(read.pure).show)berechnet die digitale Wurzel ( siehe hier für eine Erklärung )
• nwird der Liste hinzugefügt, wenn die digitale Wurzel gleich ist i.

Netzhaut , 65 Bytes

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

Probieren Sie es online! 1-indiziert. Erläuterung:

.
9
.+
*
L$`
$`

Erstellen Sie eine Liste von Zeilen mit _s von 0 bis zur nächsten Potenz von 10 (exklusiv).

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

Sortieren Sie sie alle in der Reihenfolge der digitalen Wurzel.

_+
$.&

Konvertiert von unär zu dezimal.

N$`
$.&

Sortieren Sie sie in der Reihenfolge ihrer Länge.

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

Extrahieren Sie das nth-Element.

Pyth ,  36 31 25 24 23  22 Bytes

1-indiziert.

@o%tN9rFK^LThBlt`Q-QhK

Testsuite!

Wie es funktioniert (veraltet)

@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 meiner Python-Antwort .

-6 Bytes (!) Dank Kevin Cruijssen .

g<°©‰`9*®O<

Probieren Sie es 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^TsdtBl`Q-QJ

Probieren Sie es hier aus.

-3 danke an Herrn Xcoder

1-indiziert.

Perl 6 ,  68  58 Bytes

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

Testen Sie es 0-basiert

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

Teste es 1-basiert

Erweitert:

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

Probieren Sie es online!

Ursprünglich eine Portierung der exzellenten Python-Antwort von Ovs, dann noch etwas vereinfacht.

Java 8, 68 Bytes

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

Langweiliger Port von @ovs 'Python 2-Antwort , also stelle sicher, dass du ihn positiv bewertest!
-1 Byte danke an @Jakob

Probieren Sie es online aus.

K4 , 38 Bytes

Lösung:

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

Beispiele:

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

Erläuterung:

Port von Jonathan Allans Lösung, da mir der Speicher ausgeht und ich die digitalen Wurzeln von 1 bis 1e9 aufbaue.

-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:

Die Übersetzung der Lösung von ovs ist einfacher, aber länger:

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

Jelly , 19 Bytes

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

Probieren Sie es online!

-1 danke an Herrn Xcoder .

1-indiziert.

J, 24 Bytes

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

Dies stillschweigend Ausdruck wird in parens eingeschlossen, um anzuzeigen, dass er für sich allein behandelt werden soll und nicht als Teil eines folgenden Ausdrucks (wie die Argumente).

Der Ausdruck '] /:' ordnet (aufsteigend) '/:' das ursprüngliche Array ']' nach der Summe '+ /' der Ziffern. Der Ausdruck

". &> ":

wandelt eine Zahl mit '":' in einen Zeichenvektor um und wendet dann die Umkehrung '" an.' - Zeichen zu Nummer - wird auf jedes '&>' Element angewendet. Also 65536 -> '65536' -> 6 5 5 3 6.

Die Potenzkonjunktion '^:' am Ende des Ausdrucks wendet den soeben (links) erläuterten Code eine festgelegte Anzahl von Malen an. In diesem Fall ist die angegebene Anzahl unendlich '_', was bedeutet, dass die Anwendung fortgesetzt wird, bis sich das Ergebnis nicht mehr ändert.

Die abschließende "0" bedeutet, dass der gesamte Ausdruck links auf jedes skalare (0-dimensionale) Element rechts angewendet wird. Dies wäre das Array von Zahlen, auf das wir dies anwenden möchten.

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

Probieren Sie es online!

Erklärung eingehend (langsam)! Ich denke nicht, dass es viel kürzer werden kann, aber ich bin immer offen für Vorschläge

Perl 5 -pF , 27 Bytes

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

Probieren Sie es online!

Verwendet die Formel von @ ovs und die Erklärungen von @ JonathanAllen, um einen schönen kompakten Code zu erhalten.