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!
Antworten:
Python 2 ,
7860524645 Bytes-6 Bytes dank GB .
-1 Byte danke an Jakob .
Probieren Sie es online!
Endlich eine geschlossene Form erreicht, 1-indiziert.
Python 2 , 78 Bytes
0-indiziert.
Probieren Sie es online!
quelle
Python 3 , 80 Bytes
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 Konvertierungint
in Python 3 (+5 Byte) erforderlichexec
ist, 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
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
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:
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
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 .
Probieren Sie es online!
quelle
Python 2 ,
737170 BytesProbieren Sie es online!
2 Bytes danke an Mr. XCoder ; und 1 Byte thx bis H.PWiz .
Dies ist 0-indiziert.
quelle
i%9
sollte ausreichen, anstatti%9+1
... auf diese Weise haben Sie meinen 72-Byter geschlagen: DD:len(`~i`)
sollte funktionierenJelly ,
15 14 109 BytesProbieren 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
).Zurück, 14 byter:
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.quelle
Haskell ,
9488 BytesProbieren 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, ...]
i
iteriert über den Bereich von1
bis9
und wird zum Sortieren nach den digitalen Wurzeln verwendetn
Durchläuft alle Zahlen mitx+1
Ziffernuntil(<10)(sum.map(read.pure).show)
berechnet die digitale Wurzel ( siehe hier für eine Erklärung )n
wird der Liste hinzugefügt, wenn die digitale Wurzel gleich isti
.quelle
Netzhaut , 65 Bytes
Probieren Sie es online! 1-indiziert. Erläuterung:
Erstellen Sie eine Liste von Zeilen mit
_
s von 0 bis zur nächsten Potenz von 10 (exklusiv).Sortieren Sie sie alle in der Reihenfolge der digitalen Wurzel.
Konvertiert von unär zu dezimal.
Sortieren Sie sie in der Reihenfolge ihrer Länge.
Extrahieren Sie das
n
th-Element.quelle
Pyth ,
36 31 25 24 2322 Bytes1-indiziert.
Testsuite!
Wie es funktioniert (veraltet)
quelle
05AB1E ,
1911 BytesPort meiner Python-Antwort .
-6 Bytes (!) Dank Kevin Cruijssen .
Probieren Sie es online!
quelle
g<°©÷¹®%9*®O<
. Hier die Erklärung, die ich dafür posten wollte .Pyth , 23 Bytes
Probieren Sie es hier aus.
-3 danke an Herrn Xcoder
1-indiziert.
quelle
Perl 6 ,
6858 BytesTesten Sie es 0-basiert
Teste es 1-basiert
Erweitert:
quelle
Ruby ,
4338 BytesProbieren Sie es online!
Ursprünglich eine Portierung der exzellenten Python-Antwort von Ovs, dann noch etwas vereinfacht.
quelle
Java 8, 68 Bytes
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.
quelle
K4 , 38 Bytes
Lösung:
Beispiele:
Erläuterung:
Port von Jonathan Allans Lösung, da mir der Speicher ausgeht und ich die digitalen Wurzeln von 1 bis 1e9 aufbaue.
Bonus:
Die Übersetzung der Lösung von ovs ist einfacher, aber länger:
quelle
Jelly , 19 Bytes
Probieren Sie es online!
-1 danke an Herrn Xcoder .
1-indiziert.
quelle
J, 24 Bytes
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.
quelle
Elixier , 239 Bytes
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
quelle
Perl 5
-pF
, 27 BytesProbieren Sie es online!
Verwendet die Formel von @ ovs und die Erklärungen von @ JonathanAllen, um einen schönen kompakten Code zu erhalten.
quelle