Jede Zahl kann mit einer unendlich langen Restsequenz dargestellt werden. Zum Beispiel, wenn wir die Zahl 7, nehmen und ausführen 7mod2
, dann 7mod3
, dann 7mod4
, und so weiter, wir bekommen 1,1,3,2,1,0,7,7,7,7,....
.
Wir brauchen jedoch die kürzestmögliche verbleibende Teilsequenz, die noch verwendet werden kann, um sie von allen niedrigeren Zahlen zu unterscheiden. Das erneute Verwenden von 7 [1,1,3]
ist die kürzeste Untersequenz, da nicht alle vorherigen Untersequenzen mit Folgendem beginnen [1,1,3]
:
0: 0,0,0,0...
1: 1,1,1,1...
2: 0,2,2,2...
3: 1,0,3,3...
4: 0,1,0,4...
5: 1,2,1,0...
6: 0,0,2,1...
Beachten Sie, dass [1,1]
die Darstellung von 7 nicht funktioniert, da sie auch zur Darstellung [1]
von 1 verwendet werden kann. Sie sollten jedoch mit einer Eingabe von 1 ausgeben .
Input-Output
Ihre Eingabe ist eine nicht negative Ganzzahl. Sie müssen eine Sequenz oder Liste der Restsequenz mit minimaler Länge wie oben definiert ausgeben.
Testfälle:
0: 0
1: 1
2: 0,2
3: 1,0
4: 0,1
5: 1,2
6: 0,0,2
7: 1,1,3
8: 0,2,0
9: 1,0,1
10: 0,1,2
11: 1,2,3
12: 0,0,0,2
30: 0,0,2,0
42: 0,0,2,2
59: 1,2,3,4
60: 0,0,0,0,0,4
257: 1,2,1,2,5,5
566: 0,2,2,1,2,6,6
1000: 0,1,0,0,4,6,0,1
9998: 0,2,2,3,2,2,6,8,8,10
9999: 1,0,3,4,3,3,7,0,9,0
Hier sind die ersten 10.000 Sequenzen , falls Sie interessiert sind (die Zeilennummern sind um 1 versetzt).
Dies ist ein Code-Golf , also mach es so kurz wie möglich in deiner Lieblingssprache. Gefälschte Bonuspunkte für schnelle Antworten!
quelle
Antworten:
Mathematica,
6053 BytesEtwas schnell (es verarbeitet 10000 in ~ 0,1 Sekunden, aber wahrscheinlich wird der Speicher für 100000 ausgehen).
Der Code löst einen Fehler aus, berechnet das Ergebnis jedoch korrekt.
Erläuterung
Wir haben zuvor im Chat festgestellt, dass die erforderlichen Teiler immer als die kürzeste Liste bestimmt werden können,
{1, 2, ..., n}
deren kleinstes gemeinsames Vielfaches die Eingabe überschreitet. Ein kurzes Argument, warum das so ist: Wenn die LCM kleiner als die Eingabe ist, bleiben beim Subtrahieren der LCM von der Eingabe alle Divisoren unverändert, sodass die Darstellung nicht eindeutig ist. Für alle Eingaben, die kleiner als der LCM sind, sind die Reste jedoch eindeutig, da der Unterschied zwischen zwei Zahlen mit gleichen Resten ein kleineres Vielfaches aller Teiler wäre.Was den Code angeht ... wie immer ist die Lesereihenfolge von Mathematica ein bisschen lustig.
Dies bringt uns eine Liste
[1, 2, 3, ..., n+2]
zur Eingaben
. Damit+2
soll sichergestellt werden, dass es für0
und richtig funktioniert1
.Map
2~Range~#
(syntaktischer Zucker fürRange[2,#]
) über diese Liste, so bekommen wirDies sind Kandidaten-Divisor-Listen (natürlich ist das im Allgemeinen viel mehr, als wir brauchen werden). Jetzt finden wir den ersten von ihnen, dessen LCM die Eingabe mit überschreitet:
Weitere Syntax:
x_
ist ein Muster, das mit einer der Listen übereinstimmt und diese aufruftx
. Das/;
hängt eine Bedingung an dieses Muster an. Diese Bedingung ist ,LCM@@x>#
wo@@
gilt die Funktion in die Liste, dhLCM@@{1,2,3}
MittelLCM[1,2,3]
.Schließlich haben wir einfach alle die Reste erhalten, die Tatsache zunutze machen , die
Mod
istListable
, dh es automatisch eine Liste Karten über , wenn eines der Argumente eine Liste (oder wenn beide Listen der gleichen Länge sind):quelle
Jelly , 14 Bytes
Dies nutzt die Tatsache, dass die Lösung (falls vorhanden) eines Systems linearer Kongruenzen einzigartig ist, modulo das LCM der Module. Probieren Sie es online! oder überprüfen Sie alle Testfälle .
Wie es funktioniert
quelle
MATL , 24 Bytes
Vielen Dank an @nimi für den Hinweis auf einen Fehler in einer früheren Version dieser Antwort (jetzt korrigiert)
Dies hat nicht genügend Speicher im Online-Compiler für die beiden größten Testfälle (funktioniert jedoch auf einem Computer mit 4 GB RAM).
Probieren Sie es online!
Erläuterung
Dies wendet die Definition auf einfache Weise an. Für die Eingabe
n
berechnet sie einen 2D - Array enthält ,mod(p,q)
mitp
von0
zun
undq
von1
zun+1
. Jedesp
ist eine Spalte und jedesq
ist eine Zeile. Bei der Eingabe istn=7
dieses Array beispielsweiseNun ist die letzte Spalte, die die Reste von enthält, im
n
Vergleich zu jeder Spalte dieses Arrays elementweise. Dies ergibtwo
1
gibt Gleichheit. Die letzte Spalte ist offensichtlich gleich sich selbst und enthält somit alle. Wir müssen die Spalte finden, die die größte Anzahl von Anfangsspalten außer der letzten hat, und diese Anzahl von Anfangsspalten notierenm
. (In diesem Fall ist es die zweite Spalte, diem=3
anfängliche enthält ). Zu diesem Zweck berechnen wir das kumulative Produkt jeder Spalte:dann die Summe jeder Spalte
und dann nicht zunehmend sortieren und den zweiten Wert nehmen, der ist
3
. Dies ist der gewünschte Wertm
, der angibt, wie viele Reste ausgewählt werden müssen.quelle
Jelly ,
1311 BytesDies wird keine Geschwindigkeit Brownie Punkte gewinnen ... Probieren Sie es online! oder überprüfen Sie die kleineren Testfälle .
Wie es funktioniert
quelle
Python 3.5,
1179578 BytesBenötigt Python 3.5 und sympy (
python3 -m pip install --user sympy
). Dank an @Dennis, um mich zu benachrichtigen, dass Python 3.5 den*l
Trick mit Standardargumenten zulässt .quelle
M>n and l
zul*(M>n)
.Python 2,
73706965 BytesEin volles Programm. @Dennis sparte 4 Bytes, indem die Art und Weise, wie mit Null umgegangen wird, verbessert wurde.
quelle
Haskell,
66605150 BytesAnwendungsbeispiel:
f 42
->[0,0,2,2]
. Es ist der in @Martin Büttners Antwort beschriebene Algorithmus .Ich werde die vorherige Version als Referenz behalten, weil es ziemlich schnell ist:
Haskell, 51 Bytes
Bei
f (10^100)
meinem fünf Jahre alten Laptop dauert es 0,03s .Edit: @xnor hat ein zu speicherndes Byte gefunden. Vielen Dank!
quelle
h i=mod i<$>[2..2+sum[1|l<-scanl1 lcm[2..i],l<=i]]
Pyth,
51 Bytes66 BytesVersuch es!
Viel höhere Geschwindigkeit 39-Byte-Version (funktioniert nicht für 0-2):
Es scheint für absurd große Zahlen wie 10 10 3 zu funktionieren
Hinweis: Diese Antwort funktioniert nicht für 0, 1 und 2.Behoben!quelle
JavaScript (ES6),
81,77ByteDies baut die Antwort rekursiv auf, bis die LCM die ursprüngliche Zahl überschreitet. Die GCD wird natürlich auch rekursiv berechnet.
Bearbeiten: 4 Bytes dank @ user81655 gespeichert.
quelle
Ruby, 52 Bytes
Diese Lösung prüft alles Mögliche
m
ab 2, die den Rest ausmachen, der die Sequenz einzigartig macht. Was das letztem
einzigartig macht, ist nicht der Rest selbst, sondernm
das letzte Mitglied des kleinsten Bereichs,(2..m)
in dem das kleinste gemeinsame Vielfache (LCM) dieses Bereichs größer ist alsn
. Dies ist auf das chinesische Resttheorem zurückzuführen. Um dien
Anzahl der Reste eindeutig zu bestimmen , muss der LCM dieser Reste größer sein alsn
(bei Auswahln
von(1..n)
; bei Auswahln
vona..b
muss der LCM nur größer sein alsb-a
).Hinweis: Ich habe
a<<n%m
am Ende des Codes wegenuntil n<t=t.lcm(m+=1)
Kurzschlüssen vora
das letzte Element erhalten haben, um ihn eindeutig zu machen.Wenn jemand Golfvorschläge hat, lass es mich bitte in den Kommentaren oder im PPCG-Chat wissen .
Ungolfing:
quelle
Julia,
3633 BytesProbieren Sie es online!
quelle
Python 3.5,
194181169152149146 Bytes:( Danke an @ Sherlock9 für 2 Bytes! )
Funktioniert perfekt und ist auch ziemlich schnell. Berechnung für die minimale Restsequenz von
100000
Ausgaben[0, 1, 0, 0, 4, 5, 0, 1, 0, 10, 4, 4]
dauerte nur ca. 3 Sekunden. Es war sogar in der Lage, die Reihenfolge für die Eingabe1000000
(1 Million), Ausgabe zu berechnen[0, 1, 0, 0, 4, 1, 0, 1, 0, 1, 4, 1, 8, 10, 0, 9]
, und es dauerte ungefähr 60 Sekunden.Erläuterung
Grundsätzlich erstellt diese Funktion zunächst eine Liste
y
mit allen Stellen , anj mod i
denenj
sich jede ganze Zahl im Bereich0=>7
(einschließlich 7) undi
jede ganze Zahl im Bereich befindet0=>100
. Das Programm geht dann in einewhile
Endlosschleife und vergleicht die gleiche Anzahl von Inhalten jeder Unterliste in der ersten bis zur vorletzten Unterliste vony
(y[:-1:]
) mit der gleichen Anzahl von Elementen in der letzten Unterliste (y[-1]
) von listy
. Wenn sublisty[-1]
ist anders als jeder anderer Subliste, wird die Schleife aus gebrochen, und die korrekten minimalen Rest - Sequenz zurückgeführt wird.Wenn zum Beispiel die Eingabe 3 ist,
y
wäre dies:Wenn es dann in die while-Schleife eintritt, vergleicht es jede Unterliste in der Liste
y[:-1:]
mit der gleichen Anzahl von Elementen in der Unterlistey[-1]
. Zum Beispiel würde es zuerst vergleichen[[0],[1],[0]]
und[1]
. Da sich die letzte Unterliste im Rest von befindety
, würde es weitergehen und dann vergleichen[[0,0],[0,1],[0,2]]
und[1,0]
. Da[1,0]
jetzt NICHT mehr iny
dieser bestimmten Reihenfolge vorkommt , ist dies die minimale Erinnerungssequenz und[1,0]
würde daher korrekt zurückgegeben.quelle
y[:c:]
ist dasselbe wiey[:c]
C89, 105 Bytes
Kompiliert (mit Warnungen) mit
gcc -std=c89
. Nimmt eine einzelne Zahl auf stdin und gibt die durch Leerzeichen auf stdout getrennte Folge von Resten aus.quelle
C 89 Bytes
Kompiliere mit gcc. Probieren Sie es online aus: n = 59 , n = 0 .
quelle