Ich habe diese Sequenz während der Arbeit an Evolution of OEIS gefunden , bin aber nie dazu gekommen, sie als Antwort zu veröffentlichen. Nachdem ich eine Referenzimplementierung in Mathematica geschrieben hatte, dachte ich, dass dies eine lustige Übung ist, die als separate Herausforderung zu tun ist.

Bauen wir einen numerischen Spaltreaktor! Betrachten Sie eine positive ganze Zahl N. Als Beispiel schauen wir uns an 24. Um diese Zahl zu spalten, müssen wir die größte Anzahl aufeinanderfolgender positiver Ganzzahlen finden, die sich summieren N. In diesem Fall ist das so 7 + 8 + 9 = 24. Also haben wir uns 24in drei neue Zahlen aufgeteilt. Ohne Kettenreaktionen wäre dies jedoch kein großer Spaltreaktor. Wiederholen wir den Vorgang also rekursiv für diese Komponenten:

       24
       /|\
      / | \
     /  |  \
    7   8   9
   / \     /|\
  3   4   / | \
 / \     /  |  \
1   2   2   3   4
           / \
          1   2

Beachten Sie, dass wir den Prozess anhalten, wenn die Zahl nicht in kleinere aufeinanderfolgende ganze Zahlen zerlegt werden kann. Beachten Sie auch, dass wir 9als geschrieben haben könnten 4 + 5, aber 2 + 3 + 4mehr Komponenten hat. Die Spaltungszahl von Nist nun definiert als die Anzahl der in diesem Prozess erhaltenen ganzen Zahlen, einschließlich sich Nselbst. Der obige Baum hat also 13 Knoten F(24) = 13.

Diese Sequenz ist OEIS-Eintrag A256504 .

Die ersten 40 Begriffe beginnen N = 1mit

1, 1, 3, 1, 5, 6, 5, 1, 6, 7, 12, 10, 12, 11, 12, 1, 8, 16, 14, 17, 18, 18,
23, 13, 21, 18, 22, 23, 24, 19, 14, 1, 22, 20, 23, 24, 31, 27, 25, 26

Die ersten 1000 Begriffe finden Sie in diesem Pastebin .

Die Herausforderung

NBestimmen Sie bei einer positiven Ganzzahl deren Fission-Nummer F(N). (Sie müssen also nicht die in 0OEIS aufgeführten führenden Unternehmen abdecken .)

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Bonusfrage: Können Sie interessante Eigenschaften dieser Sequenz finden?

Pyth, 23 22 21 Bytes

Lh&lJfqbsT.:tUb)syMeJ

Dies definiert eine rekursive Funktion y. Probieren Sie es online aus: Demonstration

Erläuterung:

L                      define a function y(b): return ...
            tUb          the list [1, 2, ..., b-1]
          .:   )         generate all consecutive sub-sequences
     f                   filter for sub-sequences T, which satisfy:
      qbsT                   b == sum(T)
    J                    and store them in J

                         return 
   lJ                        len(J)
  &                        and (if len(J) == 0 then 0 else ...)
                    eJ       last element of J (=longest sub-sequence) 
                  yM         recursive calls for all these numbers
                 s           sum
 h                         incremented by one (counting the current node)

Fission , 1328 989 887 797 Bytes

Diese Antwort ist etwas unangemessen lang (ich wünschte, wir hätten zusammenklappbare Regionen ) ... bitte vergiss nicht, darüber zu scrollen und den anderen Antworten etwas Liebe zu zeigen!

Die Arbeit an diesem Code hat diese Herausforderung inspiriert. Ich wollte EOEIS eine Antwort in Fission hinzufügen, was mich zu dieser Sequenz führte. Es dauerte jedoch ein paar Wochen, bis Fission tatsächlich erlernt und implementiert wurde. In der Zwischenzeit war die Sequenz wirklich auf mich gewachsen, sodass ich mich entschlossen habe, eine separate Herausforderung dafür zu stellen (außerdem wäre dies auf EOEIS sowieso nicht besonders weit unten im Baum gewesen).

Also präsentiere ich euch die Monstrosität:

 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
9\   ;    7A9
SQS  {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \  D /8/
~4X /A@[  %5                   /; &    K  } [S//~KSA /
  3    \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \ { +X
W7           X  X    /> \      +\ A\ /   \ /6~@/ \/
        /   ~A\;     +;\      /@
    ZX [K    / {/  / @  @ }  \ X @
       \AS   </      \V /    }SZS S/
         X   ;;@\   /;X  /> \ ; X X
 ;       \@+  >/ }$S SZS\+;    //\V
           / \\  /\; X X @  @  \~K{
           \0X /     /~/V\V /   0W//
    \        Z      [K \  //\
W       /MJ $$\\ /\7\A  /;7/\/ /
       4}K~@\ &]    @\  3/\
 /     \{   }$A/1 2  }Y~K <\
[{/\  ;@\@  /   \@<+@^   1;}++@S68
@\ <\    2        ;   \    /
$  ;}++ +++++++L
%@A{/
M  \@+>/
~     @
SNR'0YK
  \  A!/

Es wird erwartet, dass die Eingabe keinen nachgestellten Zeilenumbruch enthält, sodass Sie sie möglicherweise so aufrufen möchten echo -n 120 | ./Fission oeis256504.fis.

Das Layout könnte wahrscheinlich noch effizienter sein, daher denke ich, dass es hier noch viel Raum für Verbesserungen gibt (zum Beispiel 911 581 461 374 Plätze).

Bevor wir zur Erklärung kommen, ein Hinweis zum Testen: Der offizielle Dolmetscher funktioniert nicht so, wie er ist. a) Mirror.cppKompiliert nicht auf vielen Systemen. Wenn Sie auf dieses Problem stoßen, kommentieren Sie einfach die betreffende Zeile aus - die betroffene Komponente (ein zufälliger Spiegel) wird in diesem Code nicht verwendet. b) Es gibt einige Fehler, die zu undefiniertem Verhalten führen können (und wahrscheinlich für ein Programm dieses Komplexes). Sie können diesen Patch anwenden , um sie zu beheben. Sobald Sie dies getan haben, sollten Sie in der Lage sein, den Interpreter mit zu kompilieren

g++ -g --std=c++11 *.cpp -o Fission

Unterhaltsame Tatsache: Dieses Programm verwendet fast alle Komponenten, die Fission zu bieten hat, mit Ausnahme von #(zufälliger Spiegelung), :(halber Spiegelung) -oder |(einfacher Spiegelung) und "(Druckmodus).

Was in aller Welt?

Warnung: Dies wird ziemlich lange dauern ... Ich gehe davon aus, dass Sie wirklich interessiert sind, wie Fission funktioniert und wie man es programmieren könnte. Denn wenn nicht, bin ich mir nicht sicher, wie ich das möglicherweise zusammenfassen könnte. (Der nächste Absatz enthält jedoch eine allgemeine Beschreibung der Sprache.)

Fission ist eine zweidimensionale Programmiersprache, bei der sowohl Daten- als auch Steuerfluss durch Atome dargestellt werden , die sich durch ein Gitter bewegen. Wenn Sie Marbelous schon einmal gesehen oder verwendet haben , sollte das Konzept vage bekannt sein. Jedes Atom hat zwei ganzzahlige Eigenschaften: eine nicht negative Masse und eine beliebige Energie. Wenn die Masse jemals negativ wird, wird das Atom aus dem Gitter entfernt. In den meisten Fällen können Sie die Masse als "Wert" des Atoms und die Energie als eine Art Meta-Eigenschaft behandeln, die von mehreren Komponenten verwendet wird, um den Fluss der Atome zu bestimmen (dh die meisten Arten von Schaltern hängen vom Vorzeichen ab) die Energie). Ich werde Atome (m,E)bei Bedarf mit bezeichnen. Zu Beginn des Programms beginnt das Raster mit einer Reihe von(1,0)Atome von jedem beliebigen Ort aus einer der vier Komponenten UDLR(wobei der Buchstabe die Richtung angibt, in die sich das Atom anfangs bewegt). Die Platine wird dann mit einer ganzen Reihe von Komponenten bestückt, die die Masse und Energie von Atomen ändern, ihre Richtungen ändern oder andere anspruchsvollere Dinge tun. Eine vollständige Liste finden Sie auf der Esolangs-Seite. Die meisten davon stelle ich in dieser Erklärung vor. Ein weiterer wichtiger Punkt (von dem das Programm mehrmals Gebrauch macht) ist, dass das Gitter torisch ist: Ein Atom, das auf eine der Seiten auftrifft, erscheint auf der gegenüberliegenden Seite wieder und bewegt sich in die gleiche Richtung.

Ich habe das Programm in mehreren kleineren Teilen geschrieben und diese am Ende zusammengestellt, so gehe ich die Erklärung durch.

atoi

Diese Komponente mag ziemlich uninteressant erscheinen, aber sie ist nett und einfach und ermöglicht es mir, viele wichtige Konzepte des Arithmetik- und Kontrollflusses von Fission vorzustellen. Daher werde ich diesen Teil sehr detailliert durchgehen, damit ich die anderen Teile auf die Einführung neuer Fission-Mechaniken und auf übergeordnete Komponenten beschränken kann, deren detaillierter Kontrollfluss Sie selbst nachvollziehen können sollten.

Fission kann nur Byte-Werte von einzelnen Zeichen lesen, nicht von ganzen Zahlen. Während das hier akzeptabel ist, dachte ich, während ich dabei war, könnte ich es richtig machen und tatsächliche Ganzzahlen auf STDIN analysieren. Hier ist der atoiCode:

     ;
 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J 
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
           O

Zwei der wichtigsten Komponenten in Fission sind Spaltungs- und Fusionsreaktoren. Spaltreaktoren sind beliebige der V^<>(im obigen Code verwendeten <und >). Ein Spaltreaktor kann ein Atom speichern (indem er es in den Keil des Charakters schickt) (2,0). Wenn ein Atom die Spitze des Charakters trifft, werden zwei neue Atome an die Seiten geschickt. Ihre Masse wird bestimmt, indem die ankommende Masse durch die gespeicherte Masse dividiert wird (dh standardmäßig halbiert) - das linksgerichtete Atom erhält diesen Wert und das rechtsgerichtete Atom den Rest der Masse (dh die Masse bleibt in der Spaltung erhalten). . Beide ausgehenden Atome haben die ankommende Energie minusdie gespeicherte Energie. Das heißt, wir können Spaltungsreaktoren für die Arithmetik verwenden - sowohl für die Subtraktion als auch für die Division. Wenn ein Spaltreaktor von der Stelle getroffen wird, wird das Atom einfach diagonal reflektiert und bewegt sich dann in Richtung der Spitze des Charakters.

Fusionsreaktoren sind beliebige YA{}(der oben genannte Code verwendet Yund {). Ihre Funktion ist ähnlich: Sie können ein Atom speichern (Standardeinstellung (1,0)) und wenn sie von der Spitze getroffen werden, werden zwei neue Atome an die Seiten geschickt. In diesem Fall sind die beiden Atome jedoch identisch, behalten immer die ankommende Energie bei und multiplizieren die ankommende Masse mit der gespeicherten Masse. Das heißt, der Fusionsreaktor dupliziert standardmäßig einfach jedes Atom, das auf seinen Scheitelpunkt trifft. Wenn Fusionsreaktoren von der Seite getroffen werden, sind sie etwas komplizierter: Das Atom ist es auchgespeichert (unabhängig vom anderen Speicher), bis ein Atom auf die gegenüberliegende Seite trifft. In diesem Fall wird ein neues Atom in Richtung des Apex freigesetzt, dessen Masse und Energie die Summe der beiden alten Atome ist. Wenn ein neues Atom auf die gleiche Seite trifft, bevor ein passendes Atom die gegenüberliegende Seite erreicht, wird das alte Atom einfach überschrieben. Mit Fusionsreaktoren können Addition und Multiplikation durchgeführt werden.

Eine andere einfache Komponente, die ich aus dem Weg räumen möchte, ist [und ]die einfach die Richtung des Atoms nach rechts bzw. links setzt (unabhängig von der eingehenden Richtung). Die vertikalen Entsprechungen lauten M(nach unten) und W(nach oben), werden jedoch nicht für den atoiCode verwendet. UDLRwirken auch wie WM][nach der Freisetzung ihrer ursprünglichen Atome.

Wie auch immer, schauen wir uns den Code dort oben an. Das Programm beginnt mit 5 Atomen:

• Die Rund Lam Boden erhalten einfach ihr Masseninkrement (mit +) (10,0)und werden dann in einer Spaltung bzw. einem Fusionsreaktor gespeichert. Wir werden diese Reaktoren verwenden, um den Base-10-Eingang zu analysieren.
• Die LMasse in der oberen rechten Ecke wird dekrementiert (mit _) (0,0)und auf der Seite eines Fusionsreaktors gelagert Y. Dies dient dazu, die Zahl, die wir lesen, im Auge zu behalten. Diese Zahl wird schrittweise erhöht und multipliziert, wenn wir Zahlen lesen.
• Die RMasse in der linken oberen Ecke wird auf den Zeichencode 0(48) mit gesetzt '0, dann werden Masse und Energie mit getauscht @und schließlich die Masse einmal mit erhöht +, um zu geben (1,48). Es wird dann mit Diagonalspiegeln umgelenkt \und /in einem Spaltreaktor gelagert. Wir werden die 48for-Subtraktion verwenden, um die ASCII-Eingabe in die tatsächlichen Werte der Ziffern umzuwandeln. Wir mussten auch die Masse erhöhen, 1um eine Teilung durch zu vermeiden 0.
• Schließlich setzt die Ulinke untere Ecke alles in Bewegung und wird zunächst nur für den Kontrollfluss verwendet.

Nach der Umleitung nach rechts trifft das Kontrollatom ?. Dies ist die Eingabekomponente. Es liest ein Zeichen und setzt die Masse des Atoms auf den gelesenen ASCII-Wert und die Energie auf 0. Wenn wir stattdessen EOF drücken, wird die Energie auf eingestellt 1.

Das Atom fährt fort und trifft dann %. Dies ist ein Spiegelschalter. Bei nicht positiver Energie wirkt dies wie ein /Spiegel. Aber für positive Energie wirkt es wie ein \(und dekrementiert die Energie auch um 1). Während wir die Zeichen lesen, wird das Atom nach oben reflektiert und wir können das Zeichen verarbeiten. Wenn wir mit der Eingabe fertig sind, wird das Atom nach unten reflektiert und wir können eine andere Logik anwenden, um das Ergebnis abzurufen. Zu Ihrer Information, die entgegengesetzte Komponente ist &.

Wir haben also vorerst ein Atom im Aufwind. Was wir für jedes Zeichen tun möchten, ist, seinen Ziffernwert zu lesen, diesen zu unserer laufenden Summe zu addieren und dann diese laufende Summe mit 10 zu multiplizieren, um sich auf die nächste Ziffer vorzubereiten.

Das Charakteratom trifft zuerst auf einen (Standard-) Fusionsreaktor Y. Dies teilt das Atom und wir verwenden die nach links gehende Kopie als Kontrollatom, um in die Eingabekomponente zurückzukehren und das nächste Zeichen zu lesen. Die rechtsgültige Kopie wird bearbeitet. Stellen Sie sich den Fall vor, in dem wir den Charakter gelesen haben 3. Unser Atom wird sein (51,0). Wir tauschen Masse und Energie mit @, so dass wir die Subtraktion des nächsten Spaltreaktors nutzen können. Der Reaktor subtrahiert 48die Energie (ohne die Masse zu verändern) und sendet zwei Kopien davon aus (0,3)- die Energie entspricht nun der gelesenen Ziffer. Die aufsteigende Kopie wird einfach mit verworfen ;(eine Komponente, die nur alle eingehenden Atome zerstört). Wir werden weiter mit der ausgehenden Kopie arbeiten. Sie müssen seinem Weg durch die folgen/und \spiegelt ein bisschen.

Der @kurz vor dem Fusionsreaktor tauscht wieder Masse und Energie aus, so dass wir (3,0)unsere laufende Summe in der ergänzen Y. Beachten Sie, dass die laufende Summe selbst immer 0Energie hat.

Jetzt Jist ein Sprung. Was es tut, ist ein ankommendes Atom durch seine Energie nach vorne zu springen. Wenn es so ist 0, bewegt sich das Atom einfach weiter geradeaus. Wenn es 1so ist, überspringt es eine Zelle, wenn es so ist 2, überspringt es zwei Zellen und so weiter. Die Energie wird im Sprung verbraucht, so dass das Atom immer mit Energie endet 0. Da die laufende Summe keine Energie hat, wird der Sprung vorerst ignoriert und das Atom in den Fusionsreaktor umgeleitet, der {seine Masse mit multipliziert 10. Die abgehende Kopie wird verworfen, ;während die abgehende Kopie Yals neue laufende Summe in den Reaktor zurückgeführt wird.

Das oben Gesagte wird so lange wiederholt (in einer lustigen Pipeline-Art und Weise, in der neue Ziffern verarbeitet werden, bevor die vorherigen fertig sind), bis wir EOF erreichen. Nun %wird das Atom nach unten gesendet. Die Idee ist, dieses Atom (0,1)vor dem Auftreffen auf den laufenden Gesamtreaktor in ein Jetzt umzuwandeln, so dass a) die Gesamtmenge nicht beeinflusst wird (Nullmasse) und b) wir eine Energie erhalten, 1um über den Reaktor zu springen [. Wir können uns leicht um die Energie kümmern, mit der die Energie $inkrementiert wird.

Das Problem ist, dass ?die Masse nicht zurückgesetzt wird, wenn Sie EOF treffen, sodass die Masse immer noch die des zuletzt gelesenen Zeichens ist und die Energie 0(weil %das 1Zurück zu dekrementiert wird 0). Also wollen wir diese Masse loswerden. Dazu tauschen wir wieder Masse und Energie aus @.

Ich brauche eine weitere Komponente einzuführen , bevor Sie diesen Abschnitt Finishing: Z. Dies ist im Wesentlichen dasselbe wie %oder &. Der Unterschied besteht darin, dass es Atome mit positiver Energie durchlässt (während es die Energie dekrementiert) und Atome mit nicht positiver Energie um 90 Grad nach links ablenkt. Wir können dies nutzen, um die Energie eines Atoms zu eliminieren, indem wir es immer wieder durchschleifen Z- sobald die Energie weg ist, wird das Atom abgelenkt und verlässt die Schleife. Das ist dieses Muster:

/ \
[Z/

wo sich das Atom nach oben bewegt, sobald die Energie Null ist. Ich werde dieses Muster in der einen oder anderen Form mehrmals in den anderen Programmteilen verwenden.

Also , wenn das Atom diese kleine Schleife verlässt, wird es sein , (1,0)und tauschte (0,1)durch die @vor den Fusionsreaktor trifft das Endergebnis der Eingang freizugeben. Die laufende Summe wird jedoch um den Faktor 10 verringert, da wir sie bereits für eine andere Ziffer vorläufig multipliziert haben.

Jetzt mit Energie 1wird dieses Atom das überspringen [und in das springen /. Dies lenkt es in einen Spaltreaktor um, den wir vorbereitet haben, um durch 10 zu teilen und unsere fremde Multiplikation zu fixieren. Wieder verwerfen wir die eine Hälfte mit ;und behalten die andere als Ausgabe (hier dargestellt, bei Oder einfach das entsprechende Zeichen gedruckt und das Atom zerstört wird - im vollständigen Programm verwenden wir stattdessen weiterhin das Atom).

itoa

           /     \
input ->  [{/\  ;@
          @\ <\   
          $  ;}++ +++++++L
          %@A{/
          M  \@+>/
          ~     @
          SNR'0YK
            \  A!/

Natürlich müssen wir das Ergebnis auch wieder in einen String konvertieren und ausdrucken. Dafür ist dieser Teil da. Dies setzt voraus, dass die Eingabe nicht vor Tick 10 oder so eintrifft, sondern im vollständigen Programm, das leicht gegeben ist. Dieses Bit befindet sich am Ende des vollständigen Programms.

Dieser Code führt eine neue, sehr mächtige Fission-Komponente ein: den Stack K. Der Stapel ist anfangs leer. Wenn ein Atom mit nicht negativer Energie auf den Stapel trifft, wird das Atom einfach auf den Stapel geschoben. Wenn ein Atom mit negativer Energie auf den Stapel trifft, werden seine Masse und Energie durch das Atom auf der Oberseite des Stapels ersetzt (das dadurch abgesprungen ist). Ist der Stapel jedoch leer, kehrt sich die Richtung des Atoms um und seine Energie wird positiv (dh multipliziert mit -1).

Okay, zurück zum eigentlichen Code. Die Idee des itoaSnippets besteht darin, das Eingabemodul 10 wiederholt zu verwenden, um die nächste Ziffer zu finden, während die Eingabe für die nächste Iteration durch 10 geteilt wird. Dies ergibt alle Ziffern in umgekehrter Reihenfolge (von der niedrigsten zur höchsten). Um die Reihenfolge festzulegen, schieben wir alle Ziffern auf einen Stapel und ziehen sie am Ende einzeln ab, um sie zu drucken.

Die obere Hälfte des Codes führt die LZiffernberechnung durch : das mit den Pluszeichen gibt eine 10, die wir klonen und in eine Spaltung und einen Fusionsreaktor einspeisen, so dass wir teilen und mit 10 multiplizieren können. Die Schleife beginnt [im Wesentlichen nach der in der oberen linken Ecke . Der aktuelle Wert wird geteilt: Eine Kopie wird durch 10 geteilt, dann mit 10 multipliziert und in einem Spaltreaktor gespeichert, der dann von der anderen Kopie am Scheitelpunkt getroffen wird. Dies berechnet i % 10als i - ((i/10) * 10). Beachten Sie auch, dass das AZwischenergebnis nach der Division und vor der Multiplikation aufgeteilt wird, sodass wir i / 10in die nächste Iteration einspeisen können.

Das %bricht die Schleife ab, sobald die Iterationsvariable 0 erreicht. Da dies mehr oder weniger eine do-while-Schleife ist, würde dieser Code sogar zum Drucken funktionieren 0(ohne ansonsten führende Nullen zu erzeugen). Sobald wir die Schleife verlassen, wollen wir den Stapel leeren und die Ziffern ausdrucken. Sist das Gegenteil von Z, es ist also ein Schalter, der ein ankommendes Atom mit nicht positiver Energie um 90 Grad nach rechts ablenkt. Das Atom bewegt sich also tatsächlich über die Kante von der SGeraden zur K, um eine Ziffer auszublenden (beachten Sie ~, dass dies sicherstellt, dass das ankommende Atom Energie hat -1). Diese Ziffer wird um erhöht 48, um den ASCII-Code des entsprechenden Ziffernzeichens zu erhalten. Das Ateilt die Ziffer, mit der eine Kopie gedruckt werden soll!und geben Sie die andere Kopie Yfür die nächste Ziffer in den Reaktor zurück. Die gedruckte Kopie wird als nächster Auslöser für den Stapel verwendet (beachten Sie, dass die Spiegel sie auch um die Kante herum senden, um die Mvon links zu treffen ).

Wenn der Stapel leer ist, Kreflektiert der Wille das Atom und wandelt seine Energie in um +1, so dass es direkt durch den Stapel läuft S. Ndruckt eine neue Zeile (nur weil es ordentlich ist :)). Und dann geht das Atom R'0wieder durch und landet auf der Seite von Y. Da es keine weiteren Atome gibt, wird dies niemals veröffentlicht und das Programm wird beendet.

Berechnung der Spaltungsnummer: Das Framework

Kommen wir zum eigentlichen Fleisch des Programms. Der Code ist im Grunde ein Port meiner Mathematica-Referenzimplementierung:

fission[n_] := If[
  (div = 
    SelectFirst[
      Reverse@Divisors[2 n], 
      (OddQ@# == IntegerQ[n/#] 
       && n/# > (# - 1)/2) &
    ]
  ) == 1,
  1,
  1 + Total[fission /@ (Range@div + n/div - (div + 1)/2)]
]

wo divist die Anzahl der ganzen Zahlen in der maximalen Partition.

Die Hauptunterschiede bestehen darin, dass wir in Fission nicht mit halben Ganzzahlen umgehen können, also mache ich eine Menge Dinge, die mit zwei multipliziert werden, und dass es in Fission keine Rekursion gibt. Um dies zu umgehen, schiebe ich alle Ganzzahlen in einer Partition in eine Warteschlange, um sie später zu verarbeiten. Für jede Zahl, die wir verarbeiten, erhöhen wir einen Zähler um eins und sobald die Warteschlange leer ist, geben wir den Zähler frei und senden ihn zum Drucken ab. (Eine Warteschlange Qfunktioniert genau so K, nur in FIFO-Reihenfolge.)

Hier ist ein Rahmen für dieses Konzept:

                      +--- input goes in here
                      v 

                     SQS ---> compute div from n          D /8/
                     ~4X               |                /~KSA /
                       3               +----------->    { +X
initial trigger ---> W                               6~@/ \/
                              4                   
                     W        ^                     /
                              |              3
                     ^     generate range    |
                     |     from n and div  <-+----- S6
                     |         -then-      
                     +---- release new trigger

Die wichtigsten neuen Komponenten sind die Ziffern. Das sind Teleporter. Alle Teleporter mit der gleichen Ziffer gehören zusammen. Wenn ein Atom einen Teleporter trifft, bewegt es sofort den nächsten Teleporter in derselben Gruppe, wobei der nächste in der üblichen Reihenfolge von links nach rechts von oben nach unten bestimmt wird. Diese sind nicht notwendig, helfen aber beim Layouten (und damit ein bisschen Golfen). Es gibt auch das, Xwas ein Atom einfach dupliziert und eine Kopie geradeaus und die andere rückwärts sendet.

Inzwischen können Sie möglicherweise den größten Teil des Frameworks selbst aussortieren. In der oberen linken Ecke befindet sich die Warteschlange mit den noch zu verarbeitenden Werten und wird einzeln freigegeben n. Eine Kopie von nwird nach unten teleportiert, weil wir sie für die Berechnung des Bereichs benötigen. Die andere Kopie wird in den oberen Block geschrieben, der berechnet wird div(dies ist bei weitem der größte Abschnitt des Codes). Einmal divberechnet, wird es dupliziert - eine Kopie erhöht einen Zähler in der oberen rechten Ecke, der in gespeichert ist K. Die andere Kopie wird nach unten teleportiert. Wenn divwar 1, ablenken wir es nach oben sofort und verwenden Sie es als ein Auslöser für die nächste Iteration, ohne neue Werte Einreihen. Ansonsten verwenden wir divundn Klicken Sie im unteren Bereich auf, um den neuen Bereich (dh einen Strom von Atomen mit den entsprechenden Massen, die anschließend in die Warteschlange gestellt werden) zu generieren, und geben Sie dann einen neuen Auslöser frei, nachdem der Bereich abgeschlossen wurde.

Sobald die Warteschlange leer ist, wird der Auslöser reflektiert, geht geradewegs durch die Sund erscheint wieder in der oberen rechten Ecke, wo er den Zähler (das Endergebnis) freigibt A, von dem er dann zu itoavia teleportiert wird 8.

Berechnung der Spaltungsnummer: The Loop Body

Sie müssen also nur noch die beiden Abschnitte berechnen divund den Bereich generieren. Computing divist dieser Teil:

 ;    
 {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \
/A@[  %5                   /; &    K  } [S/
   \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \ 
         X  X    /> \      +\ A\ /   \ /
    /   ~A\;     +;\      /@
ZX [K    / {/  / @  @ }  \ X @
   \AS   </      \V /    }SZS S/
     X   ;;@\   /;X  /> \ ; X X
     \@+  >/ }$S SZS\+;    //\V
       / \\  /\; X X @  @  \~K{
       \0X /     /~/V\V /   0W//
\        Z      [K \  //\
           \ /\7\A  /;7/\/

Sie haben jetzt wahrscheinlich genug gesehen, um dies mit etwas Geduld selbst herauszufinden. Die Aufschlüsselung auf hoher Ebene lautet wie folgt: Die ersten 12 Spalten oder so erzeugen einen Strom von Teilern von 2n. Die nächsten 10 Spalten filtern diejenigen heraus, die nicht zufriedenstellen OddQ@# == IntegerQ[n/#]. Die nächsten 8 Spalten filtern diejenigen heraus, die nicht zufriedenstellen n/# > (# - 1)/2). Schließlich schieben wir alle gültigen Divisoren auf einen Stapel, und sobald wir fertig sind, leeren wir den gesamten Stapel in einen Fusionsreaktor (überschreiben alle bis auf den letzten / größten Divisor) und geben dann das Ergebnis frei, gefolgt von der Eliminierung seiner Energie (die nicht vorhanden war) -zero von der Überprüfung der Ungleichung).

Es gibt eine Menge verrückter Pfade, die eigentlich gar nichts bewirken. Überwiegend der \/\/\/\/Wahnsinn oben (die 5s sind auch Teil davon) und ein Pfad um den Boden (der durch das 7s führt). Ich musste diese hinzufügen, um mit einigen schlechten Rennbedingungen fertig zu werden. Fission könnte eine Verzögerungskomponente verwenden ...

Der Code, aus dem der neue Bereich generiert wird, lautet nwie divfolgt:

 /MJ $$\
4}K~@\ &]    @\  3/\
\{   }$A/1 2  }Y~K <\
 \@  /   \@<+@^   1;}++@
  2        ;   \    /

Wir berechnen zuerst n/div - (div + 1)/2(beide Begriffe sind mit einem Floor versehen, was dasselbe Ergebnis ergibt) und speichern es für später. Dann generieren wir einen Bereich von divunten bis 1und addieren den gespeicherten Wert zu jedem von ihnen.

Es gibt zwei neue gemeinsame Muster in beiden, die ich erwähnen sollte: Eines ist SXoder ZXvon unten getroffen (oder gedrehte Versionen). Dies ist eine gute Möglichkeit, ein Atom zu duplizieren, wenn Sie möchten, dass eine Kopie direkt weitergeleitet wird (da das Umleiten der Ausgänge eines Fusionsreaktors manchmal umständlich sein kann). Das Soder Zdreht das Atom in das Xund dreht dann die gespiegelte Kopie zurück in die ursprüngliche Ausbreitungsrichtung.

Das andere Muster ist

[K
\A --> output

Wenn wir irgendeinen Wert in speichern, können Kwir ihn wiederholt abrufen, indem wir Kmit negativer Energie von oben aufschlagen. Das Adupliziert den Wert, an dem wir interessiert sind und sendet die Kopie direkt zurück auf den Stapel, damit wir sie das nächste Mal benötigen.

Nun, das war ein ziemlicher Zeitvertreib ... aber wenn Sie es tatsächlich geschafft haben, dann haben Sie hoffentlich die Idee, dass Fission ein Problem für Sie darstellt

CJam, 42 41 Bytes

ri]{_{:X,:)_few:+W%{1bX=}=}%{,(},e_}h]e_,

Eine einfache erste Durchquerung der Breite und ein Haltezustand des leeren nächsten Levels.

Wie es funktioniert :

ri]                                       e# This represents the root of the fissile tree
   {                               }h     e# Now we run a do-while loop
    _{                    }%              e# Copy the nodes at the current level and map them
                                          e# via this code block to get next level nodes
      :X,:)                               e# Store the node value in X and get array [1..X]
           _few                           e# Copy the array and get continuous slices of
                                          e# length 1 through X from the array [1..X]
               :+W%                       e# Right now, we have an array of array with each
                                          e# array containing slice of same length. We join
                                          e# those arrays and reverse them to get slices of
                                          e# higher length in front of lower lengths
                   {1bX=}=                e# Choose the first slice whose sum is same as X
                                          e# The reversal above makes sure that we give
                                          e# preference to slice of higher length in case of
                                          e# multiple slices add up to X
                            {,(},         e# Filter out slices of length 1 which basically
                                          e# mean that the current node cannot be split up
                                 e_       e# Join all slices in a single array. This is our
                                          e# next level in the Fissile tree. If this is empty
                                          e# it means that all no further node can be
                                          e# decomposed. In an {}h do-while loop, this fact
                                          e# itself becomes the stopping condition for the
                                          e# loop
                                     ]e_, e# Wrap all levels in an array. Flatten the array
                                          e# and take its length

Probieren Sie es hier online aus

Python 3, 112 Bytes

def f(n,c=0):
 d=n-c;s=(n-d*~-d/2)/d
 return(s%1or s<1)and f(n,c+1)or+(d<2)or-~sum(f(int(s)+i)for i in range(d))

4 Bytes gespart dank @FryAmTheEggman.

Erklärung kommt später ...

Bonus-Fakt: Jede Potenz von 2 hat eine Fission-Nummer von 1. Dies liegt daran, dass die Summe einer Folge gerader Länge immer die Summe der beiden mittleren Zahlen ist, die ungerade ist, multipliziert mit der halben Länge der Folge, die ganzzahlig ist . Die Summe einer Sequenz ungerader Länge ist die mittlere Zahl multipliziert mit der Sequenzlänge, die ungerade ist. Da eine Potenz von 2 keinen ungeraden Teiler hat, kann sie nur als die Summe von sich selbst ausgedrückt werden.

Python 2, 111 102 97 Bytes

Etwas lesbar:

def f(n,c=0):a=n-c;b=n-a*~-a/2;return 1/a or-~sum(map(f,range(b/a,b/a+a)))if b>b%a<1else f(n,c+1)

Nicht so lesbar:

def f(n,a=0):b=n-a*~-a/2;return b>0and(f(n,a+1)or b%a<1and(1/a or-~sum(map(f,range(b/a,b/a+a)))))

Beide 97 Bytes.

bist das nMinus der (a-1)thDreieckszahl. Wenn ja b % a == 0, dann nist das die Summe der afortlaufenden Nummern ab b.

Python 2, 86

f=lambda n,R={1}:n-sum(R)and f(n,R^{[min(R),max(R)+1][n>sum(R)]})or-~sum(map(f,R-{n}))

Weniger golfen:

def f(n,R={1}):
    d=sum(R)-n
    if d==0:return (sum(map(f,R-{n}))
    if d<0:return f(n,R|{max(R)+1})
    if d>0:return f(n,R-{min(R)})

Die Idee ist, potenzielle Läufe von aufeinanderfolgenden ganzen Zahlen zu testen, die sich summieren n. Der Lauf wird direkt als Set Rund nicht über seine Endpunkte gespeichert .

Wir prüfen anhand der nDifferenz , wie die Summe des aktuellen Laufs mit der gewünschten Summe verglichen wird .

• Wenn die Summe zu groß ist, schneiden wir das kleinste Element im Lauf.
• Wenn die Summe zu klein ist, verlängern wir den Lauf, indem wir das Maximum um 1 erhöhen.
• Wenn die Summe korrekt ist, führen wir eine Rekursion durch, ordnen sie fdem Lauf zu, summieren und addieren 1 für den aktuellen Knoten. Wenn der Lauf ist {n}, haben wir alle nicht trivialen möglichen Summen versucht, stoppen Sie die Rekursion, indem Sie nzuerst entfernen .

Dank an Sp3000 für das Speichern von 3 Zeichen.

Python 2, 85

Ich bin sehr stolz auf diese Antwort, da es für n = 9 bereits zehn Sekunden und für n = 10 fünf bis zehn Minuten dauert. Im Codegolf wird dies als wünschenswertes Attribut eines Programms angesehen.

f=lambda n,a=1,d=1:a/n or[f(a)+f(n-a,1+1%d*a)+1/d,f(n,a+d/n,d%n+1)][2*n!=-~d*(2*a+d)]

Es gibt auch eine Kurzschlussversion, die nicht so lange dauert und die gleiche Anzahl von Bytes verwendet:

f=lambda n,a=1,d=1:a/n or~d*(2*a+d)+n*2and f(n,a+d/n,d%n+1)or f(a)+f(n-a,1+1%d*a)+1/d 

Es kann schneller sein, überschreitet aber zumindest die Standard-Rekursionsgrenze, sobald n etwas über 40 liegt.

Die Idee ist es, eine Brute - Force - Suche nach Zahlen zu tun aund dso , dass a + a+1 + ... + a+d == n, auf Werte zwischen 1 und n. Der f(n,a+d/n,d%n+1)Zweig der Rekursion durchläuft die (a, d)Paare. Für den Fall, dass die Gleichheit erfüllt ist, schaffe ich es, einen teuren map(range(...))Anruf zu vermeiden , indem ich mich in nur zwei Zweige aufteile, unabhängig davon, wie lang die Sequenz ist. Die a+1durchgehenden Nummern dwerden zu einem Aufruf zusammengefasst, findem der aParameter so eingestellt wird, dass keine andere Methode zum Aufteilen der Sequenz verwendet werden kann.

Haskell, 76 69 Bytes

f x=head$[1+sum(map f[y..z])|y<-[1..x-1],z<-[y..x],sum[y..z]==x]++[1]

Verwendungszweck:

*Main> map f [1..40]
[1,1,3,1,5,6,5,1,6,7,12,10,12,11,12,1,8,16,14,17,18,18,23,13,21,18,22,23,24,19,14,1,22,20,23,24,31,27,25,26]

Wie es funktioniert:

[  [y..z] |y<-[1..x-1],z<-[y..x],sum[y..z]==x]

           make a list of lists with all consecutive integers (at least 2 elements)
           that sum up to x, sorted by lowest number, e.g. 9 -> [[2,3,4],[4,5]].

1+sum(map f[...]) 

           recursively calculate the Fission Number for each list

[...]++[1]

           always append the 1 to the list of Fission Numbers.

head

           take the first element, which is either the Fission Number of the
           longest list or if there's no list, the 1 appended in the step before.  

Netzhaut , 66 Bytes

^|$
,
(`,(1+?)(?=(?<1>1\1)+\D)
$0;
+)`,(1*);1\1
,$1,1$1;
^,|1

.
1

Übernimmt die Eingabe und druckt die Ausgabe in unary.

Sie können jede Zeile in eine einzelne Datei einfügen oder den Code so wie er ist mit dem -sFlag ausführen . Z.B:

> echo -n 1111111|retina -s fission
11111

Erläuterung:

• Wir führen eine durch Kommas getrennte Liste der zu teilenden Nummern.
• Für jede Zahl nehmen wir den kleinsten Startwert, der eine gültige Aufteilung bilden kann, und grenzen ihn mit einem Semikolon vom Rest ab.
• Befindet sich in einer Zahl ein Semikolon, ändern wir es in ein Komma und begrenzen den nächstgrößeren (Länge des vorherigen Elements + 1) Teil der Zahl.
• Wir wiederholen die Schritte 2 und 3, bis Änderungen eintreten.
• Wir erhalten ein Komma für jedes Blatt und ein Semikolon für jeden inneren Knoten sowie ein zusätzliches Komma, da wir mit zwei Kommas begonnen haben. Also entfernen wir ein Komma und die Teile der Zahlen ( 1's) und konvertieren den Rest in 1' s.

Die Zustände des Strings während des gesamten Prozesses mit Eingabe 11111111111111 (unary 14):

,11111111111111,
,11;111111111111,
,11,1;11,1111,11;111;,
,11,1,11;,1111,11,1;11;;,
,11,1,11;,1111,11,1,11;;;,
,,;,,,,;;;,
11111111111

Vielen Dank für @MartinButtner für die Hilfe im Chat!

CJam (43 Bytes)

qi,{):X),_m*{{_)*2/}/-X=}=~\,>0\{~$+}/)}%W=

Online-Demo

Ich bin sicher , dass ich mit den erweiterten Schleifen ein paar Tricks bin fehlt, aber das macht ausnutzen ordentlich die CJam Eigenschaft (die mir vorher geärgert hat) , dass im Inneren eine %Karte , um die Ergebnisse auf dem Stapel bleiben und daher zugegriffen werden kann unter Verwendung von $mit einem negativer Offset.

Los, 133 Bytes

func 算(n int)int{Σ:=1;for i:=0;i<n;i++{for j:=0;j<n;j++{if i*i+i-j*j-j==2*n{for k:=j+1;k<=i;k++{Σ+=算(k)};j,i=n,n}}};return Σ}

Dies ist mein erster Code Golf, sorry wenn ich Fehler gemacht habe.

Dies basiert auf der Idee, dass die spaltbare "Zusammensetzung" auch als Unterschied zwischen zwei Folgen geordneter ganzer Zahlen angesehen werden kann. Nehmen Sie zum Beispiel die spaltbare "Komposition" für die Zahl 13. Sie ist 6,7. Aber es kann als die Summe der ganzen Zahlen 1 ... 7 minus der Summe der ganzen Zahlen 1 ... 5 gesehen werden

  A: 1 2 3 4 5 6 7  sum = 28
  B: 1 2 3 4 5      sum = 15 
A-B:           6 7  sum = 13, which is also 28-15 = 13

Erinnern Sie sich an die Formel aus Gauß 'Schultagen, Summe 1 ... n = (n ^ 2 + n) / 2. Um also eine Komposition sequentieller Ganzzahlen für ein gegebenes n zu finden, können wir auch sagen, wir suchen nach 'Endpunkten' p und q im Bereich 1 ... n, so dass (p ^ 2 + p) / 2 - ( q ^ 2 + q) / 2 = n. Im obigen Beispiel hätten wir nach 'Endpunkten' 5 und 7 gesucht, weil 7 ^ 2 + 7 = 56/2, 5 ^ 2 + 5 = 30/2, 56 / 2-30 / 2 = 28-15 = 13.

Nun gibt es mehrere Möglichkeiten, eine Zahl auf spaltbare Weise zusammenzusetzen, wie Martin feststellte: 9 = 2 + 3 + 4, aber auch 4 + 5. Es scheint jedoch offensichtlich, dass die "niedrigste" Startsequenz auch die längste sein wird, da sie länger dauert kleine Zahlen ergeben eine große Zahl als mittlere Zahlen. (Ich habe leider keinen Beweis)

Um die Zusammensetzung von 9 zu finden, testen Sie jedes 'Endpunktpaar', p und q, wobei Sie sowohl p als auch q getrennt von 0 bis 9 durchlaufen, und testen Sie, ob p ^ p + p / 2 - q ^ 2 + q / 2 = 9. Oder, einfacher gesagt, multiplizieren Sie die Gleichung mit 2, um die Divisionsthemen der Rundung zu vermeiden und die gesamte Mathematik in ganzen Zahlen zu halten. Dann suchen wir nach p und q, so dass (p ^ p + p) - (q ^ q + q) = 9 * 2 ist. Die erste Übereinstimmung, die wir finden, sind die Endpunkte der spaltbaren Zusammensetzung, da, wie bereits erwähnt, die niedrigste Gruppe von Zahlen auch die längste ist und wir von niedrig nach hoch suchen (0 bis 9). Wir brechen aus der Schleife aus, sobald wir eine Übereinstimmung finden.

Jetzt findet die rekursive Funktion die spaltbaren Endpunkte p und q für das gegebene n und ruft sich dann für jedes der Kinder im Baum von p bis q auf. Für 9 würde es 1 und 4 finden (20-2 = 18), dann würde es sich auf 2, 3 und 4 zurückrufen und die Ergebnisse aufsummieren. Bei Zahlen wie 4 findet es einfach keine Übereinstimmung und gibt daher '1' zurück. Dies kann verkürzt werden, entspricht jedoch meinem dritten Go-Programm und ich bin kein Rekursionsexperte.

Danke fürs Lesen.

CJam, 40 35 33 Bytes

ri{__,f-_few:+{1b1$=}=|{F}*}:F~],

Danke an @Optimizer für den Vorschlag few, der 2 Bytes gespart hat.

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

ri      e# Read an integer from STDIN.
{       e# Define function F(X):
  _     e# Push X.
  _,    e# Push [0 ... X-1].
  f-    e# Subract each from X. Pushes Y := [X ... 1].
  _few  e# Push all overlapping slices of Y of length in Y.
  :+    e# Consolidate the slices of different lenghts in a single array.
  {     e# Find the first slice S such that...
    1b  e#   the sum of its elements...
    1$= e#   equals X.
  }=    e#   Since Y is in descending order, the first matching slice is also the longest.
  |     e# Set union with [X]. This adds X to the beginning of the S if S != [X].
  {F}*  e# Execute F for each element of S except the first (X).
}:F     e#
~       e# Execute F for the input.
],      e# Count the integers on the stack.