Der polygonale Zahlensatz von Fermat besagt, dass jede positive ganze Zahl als die Summe von höchstens -gonalen Zahlen ausgedrückt werden kann. Dies bedeutet, dass jede positive ganze Zahl als Summe von bis zu drei Dreieckszahlen, vier Quadratzahlen, fünf Fünfeckzahlen usw. ausgedrückt werden kann. Ihre Aufgabe ist es, eine positive ganze Zahl und eine ganze Zahl und die auszugeben -gonale ganze Zahlen, die sich zu summieren .
Die - te -gonal ganze Zahl, wobei und , können in ein paar Arten definiert werden. Der nicht-mathematische Weg ist, dass die te eckige Zahl als reguläres Polygon mit Seiten mit jeweils der Länge n konstruiert werden kann . Zum Beispiel für s = 3 (Dreieckszahlen):
Sehen Sie hier für Beispiele mit einem größeren .
Die Mathematik-y - Definition wird durch die Formel für die Verwendung von , die die Ausbeuten -te -gonal Nummer:
Das ist in der Wikipedia-Seite hier angegeben .
Eingang
Zwei positive ganze Zahlen und mit der Bedingung . Sie können diese Ganzzahlen in der natürlichsten Darstellung in Ihrer Sprache eingeben (Dezimal-, Unär-, Kirchenzahlen, Gleitkommazahlen mit ganzzahligen Werten usw.).
Ausgabe
Eine Liste von ganzen Zahlen, , mit einer maximalen Länge von , wobei die Summe von gleich ist , und alle ganzen Zahlen in sind -gonal ganze Zahlen sind . Auch hier können die Ganzzahlen in der natürlichen Darstellung in Ihrer Sprache mit einem eindeutigen, konsistenten Trennzeichen ausgegeben werden (also Nicht-Dezimalzeichen für die Dezimalausgabe, ein Zeichen, das sich von dem für die unäre Ausgabe usw. unterscheidet).
Regeln
- Die Ein- oder Ausgänge überschreiten niemals die Ganzzahlgrenze für Ihre Sprache
- muss nicht bestellt werden
- Bei mehreren möglichen Ausgaben sind einige oder alle akzeptabel
- Das ist Code-Golf, also gewinnt der kürzeste Code in Bytes
Testfälle
x, s => L
1, s => 1
2, s => 1, 1
5, 6 => 1, 1, 1, 1, 1
17, 3 => 1, 6, 10
17, 4 => 1, 16
17, 5 => 5, 12
36, 3 => 36
43, 6 => 15, 28
879, 17 => 17, 48, 155, 231, 428
4856, 23 => 130, 448, 955, 1398, 1925
quelle
x=17, s=5
könnten wir5,12,0,0,0
statt nur ausgeben5,12
?Q
meiner Einreichung eine hinzufügen ?Antworten:
Haskell ,
78 8077 BytesWir berechnen das kartesische Produkt der erstenn s-gonal Zahlen und finden dann den ersten Eintrag , dass Summen n .
Probieren Sie es online!
quelle
JavaScript (ES6),
83-80ByteEine schnelle rekursive Suche, die den kleinsten Ausdruck der Ausgabe maximiert.
Übernimmt die Eingabe als
(s)(x)
.Probieren Sie es online!
Formel
Das kann in 14 Bytes geschrieben werden:
Kommentiert
quelle
05AB1E ,
1413 BytesPort of Jonathan Allans Gelee Antwort .
Probieren Sie es online!
quelle
Haskell , 55 Bytes
Probieren Sie es online!
Gibt alle möglichen Lösungen aus. Definiert die s-gonalen Zahlen als die kumulative Summe des arithmetischen Fortschritts
quelle
Gelee , 17 Bytes
Eine (sehr sehr ineffiziente) dyadische Linkannahme
s
links undx
rechts, die die kürzestmögliche Antwort als Liste von Ganzzahlen liefert (aufsteigend sortiert).Probieren Sie es online! - nicht viel Sinn, es für viel höhere Werte zu versuchen!
Wie?
quelle
⁸
Ruby , 79 Bytes
Probieren Sie es online!
quelle
Python 3 , 105 Bytes
Probieren Sie es online!
Port of Arnauld's JavaScript-Antwort , also stelle sicher, dass du ihn positiv bewertest!
quelle
Netzhaut , 111 Bytes
Probieren Sie es online! Link enthält Testfälle. Übernimmt die Eingabe in der Reihenfolge
s n
. Erläuterung:In Unary konvertieren.
Behandeln Sie die verbleibenden Phasen nach der Verarbeitung wie ein Retina-Programm und führen Sie sie an derselben Eingabe aus.
Dupliziere die Linie.
Ersetzen Sie die erste Kopie durch einen regulären Ausdruck, der die erste Zahl überspringt und dann mit
s
s
-gonalen Zahlen übereinstimmt. Die Zahlen selbst werden in ungeraden Erfassungsgruppen erfasst und die geraden Erfassungsgruppen werden verwendet, um sicherzustellen, dass alle Zahlens
-gonal sind.Ersetzen Sie die zweite Kopie durch eine durch Leerzeichen getrennte Liste der ungeraden Erfassungsgruppen.
Der generierte Code für eine Eingabe von
5 17
lautet beispielsweise wie folgt:quelle
APL (NARS), 149 Zeichen, 298 Byte
falls nicht, Lösungen "0 = ≢b" finden, dann n mal 1 für (ns) -Eingabe zurückgeben; sonst würde es die Summe von s Zahlen zurückgeben, die weniger addend hat ...
Prüfung:
Das Problem dabei: Es gibt keine Lösung, einige Zahlen wiederholen sich in der Summe ...
quelle
C ++ (clang) , 198 Bytes
Probieren Sie es online!
quelle