Znalazłem tę sekwencję podczas pracy nad Ewolucją OEIS , ale nigdy nie udało mi się opublikować jej jako odpowiedzi. Po napisaniu referencyjnej implementacji w Mathematica pomyślałem, że jest to zabawne ćwiczenie jako osobne wyzwanie, więc proszę bardzo.

Zbudujmy numeryczny reaktor rozszczepiający! Rozważ dodatnią liczbę całkowitą N. Jako przykład przyjrzymy się 24. Aby rozdzielić tę liczbę, musimy znaleźć największą liczbę kolejnych liczb całkowitych dodatnich, które sumują się N. W tym przypadku tak jest 7 + 8 + 9 = 24. Podzieliliśmy się 24na trzy nowe liczby. Ale to nie byłby duży reaktor rozszczepiający bez reakcji łańcuchowych. Powtórzmy więc rekurencyjnie proces dla tych komponentów:

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

Zauważ, że zatrzymujemy proces, ilekroć liczby nie można rozłożyć na mniejsze kolejne liczby całkowite. Zauważ też, że moglibyśmy napisać 9jako 4 + 5, ale 2 + 3 + 4ma więcej składników. Liczba Rozszczepienie z Nobecnie definiowany jako liczba całkowitych otrzymywanych w tym procesie, w tym Nsam. Powyższe drzewo ma 13 węzłów, więc F(24) = 13.

Ta sekwencja to pozycja OEIS A256504 .

Pierwsze 40 warunków, począwszy od N = 1, są

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

Pierwsze 1000 haseł można znaleźć w tym pastebin .

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą N, określ jej numer rozszczepienia F(N). (Więc nie musisz obejmować wiodących 0wymienionych w OEIS.)

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Dodatkowe pytanie: czy możesz znaleźć jakieś interesujące właściwości tej sekwencji?

Pyth, 23 22 21 bajtów

Lh&lJfqbsT.:tUb)syMeJ

Definiuje to funkcję rekurencyjną y. Wypróbuj online: Demonstracja

Wyjaśnienie:

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)

Rozszczepienie , 1328 989 887 797 bajtów

Ta odpowiedź jest nieco nieuzasadniona długa (szkoda, że ​​nie mieliśmy zwijanych regionów ) ... proszę nie zapomnij przewinąć obok tego i pokazać innym odpowiedziom trochę miłości!

Praca nad tym kodem była tym, co zainspirowało to wyzwanie. Chciałem dodać odpowiedź w Fission do EOEIS, co doprowadziło mnie do tej sekwencji. Jednak faktyczne nauczenie się rozszczepienia i jego wdrożenie zajęło kilka tygodni nad jego włączeniem i wyłączeniem. W międzyczasie sekwencja naprawdę mnie rozrosła, więc postanowiłem postawić dla niej osobne wyzwanie (plus, i tak nie byłoby to szczególnie daleko na drzewie w EOEIS).

Przedstawiam wam więc Monstrum:

 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!/

Oczekuje, że na wejściu nie ma końcowego znaku nowej linii, więc możesz chcieć go tak nazwać echo -n 120 | ./Fission oeis256504.fis.

Układ prawdopodobnie prawdopodobnie byłby bardziej wydajny, więc myślę, że wciąż jest tu dużo miejsca na ulepszenia (na przykład zawiera on 911 581 461 374 spacji).

Zanim przejdziemy do wyjaśnienia, uwaga na temat przetestowania tego: oficjalny tłumacz nie działa tak jak jest. a) Mirror.cppnie kompiluje się na wielu systemach. Jeśli napotkasz ten problem, po prostu skomentuj obraźliwą linię - dotknięty komponent (losowe lustro) nie jest używany w tym kodzie. b) Istnieje kilka błędów, które mogą prowadzić do nieokreślonego zachowania (i prawdopodobnie tak będzie w przypadku tak złożonego programu). Możesz zastosować tę poprawkę, aby je naprawić. Gdy to zrobisz, powinieneś być w stanie skompilować interpretera

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

Ciekawostka: ten program wykorzystuje prawie każdy element, jaki ma do zaoferowania Fission, z wyjątkiem #(losowego lustra), :(pół lustra) -lub |(zwykłego lustra) i "(trybu drukowania).

Co u licha

Ostrzeżenie: potrwa to dość długo ... Zakładam, że naprawdę interesujesz się działaniem Fission i tym, jak można w nim zaprogramować. Ponieważ jeśli nie, nie jestem pewien, jak mógłbym to podsumować. (Następny akapit zawiera jednak ogólny opis języka.)

Rozszczepienie jest dwuwymiarowym językiem programowania, w którym zarówno przepływ danych, jak i sterowania są reprezentowane przez atomy poruszające się po siatce. Jeśli widziałeś lub używałeś Marbelous wcześniej, koncepcja powinna być niejasno znana. Każdy atom ma dwie właściwości całkowite: nieujemną masę i dowolną energię. Jeśli masa kiedykolwiek stanie się ujemna, atom zostanie usunięty z siatki. W większości przypadków można traktować masę jako „wartość” atomu, a energię jako rodzaj meta-właściwości, która jest wykorzystywana przez kilka składników do określania przepływu atomów (tzn. Większość rodzajów przełączników zależy od znaku energia). W (m,E)razie potrzeby oznaczę atomy . Na początku programu siatka zaczyna się od kilku(1,0)atomy z dowolnego miejsca na czterech składnikach UDLR(gdzie litera wskazuje kierunek, w którym początkowo porusza się atom). Płytka jest następnie wypełniona całą masą składników, które zmieniają masę i energię atomów, zmieniają ich kierunki lub robią inne, bardziej wyrafinowane rzeczy. Pełna lista znajduje się na stronie esolangów , ale większość z nich przedstawię w tym objaśnieniu. Innym ważnym punktem (z którego program korzysta kilka razy) jest to, że siatka jest toroidalna: atom, który uderza w którąkolwiek ze stron, pojawia się po przeciwnej stronie, poruszając się w tym samym kierunku.

Napisałem program w kilku mniejszych częściach i na końcu je zmontowałem, więc w ten sposób przejdę przez wyjaśnienie.

atoi

Ten element może wydawać się raczej nieciekawy, ale jest ładny i prosty i pozwala mi wprowadzić wiele ważnych pojęć dotyczących arytmetyki i przepływu sterowania Fission. Dlatego przejrzę tę część z bardzo drobiazgowymi szczegółami, więc mogę zredukować inne części do wprowadzenia nowej mechaniki rozszczepienia i wskazania komponentów wyższego poziomu, których szczegółowy przepływ kontroli powinieneś być w stanie śledzić.

Rozszczepienie może odczytać tylko wartości bajtów z pojedynczych znaków, a nie z całych liczb. Chociaż jest to akceptowalna praktyka tutaj, pomyślałem, że będąc przy tym, mogę to zrobić poprawnie i przeanalizować rzeczywiste liczby całkowite na STDIN. Oto atoikod:

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

Dwa najważniejsze elementy rozszczepienia to reaktory rozszczepienia i syntezy jądrowej. Reaktory rozszczepienia są dowolnymi V^<>(powyższy kod używa <i >). Reaktor rozszczepienia może przechowywać atom (wysyłając go do klina postaci), domyślnie (2,0). Jeśli atom uderzy w wierzchołek postaci, dwa nowe atomy zostaną wysłane na boki. Ich masę określa się dzieląc przychodzącą masę przez masę przechowywaną (tj. Domyślnie o połowę) - atom lewostronny otrzymuje tę wartość, a atom prawostronny otrzymuje resztę masy (tj. Masa jest zachowana w rozszczepieniu) . Oba wychodzące atomy będą miały przychodzącą energię minuszmagazynowana energia. Oznacza to, że możemy wykorzystać reaktory rozszczepienia do arytmetyki - zarówno do odejmowania, jak i dzielenia. Jeśli reaktor rozszczepiony zostanie trafiony z miejsca, atom jest po prostu odbijany po przekątnej, a następnie porusza się w kierunku wierzchołka postaci.

Reaktory termojądrowe są dowolnymi YA{}(powyższy kod używa Yi {). Ich funkcja jest podobna: mogą przechowywać atom (domyślnie (1,0)), a po trafieniu ze szczytu dwa nowe atomy zostaną wysłane na boki. Jednak w tym przypadku dwa atomy będą identyczne, zawsze zachowując przychodzącą energię i mnożąc przychodzącą masę przez zmagazynowaną masę. To znaczy, że reaktor termojądrowy po prostu powiela każdy atom uderzający w jego wierzchołek. Po uderzeniu z boku reaktory termojądrowe są nieco bardziej skomplikowane: atom teżprzechowywane (niezależnie od innej pamięci), aż atom uderzy w przeciwną stronę. Kiedy tak się dzieje, nowy atom zostaje uwolniony w kierunku wierzchołka, którego masa i energia są sumą dwóch starych atomów. Jeśli nowy atom uderzy w tę samą stronę, zanim dopasowany atom dotrze do przeciwnej strony, stary atom zostanie po prostu nadpisany. Reaktory termojądrowe można wykorzystać do realizacji dodawania i mnożenia.

Kolejnym prostym składnikiem, który chcę usunąć z drogi, [i ]który po prostu ustawia kierunek atomu odpowiednio w prawo i w lewo (niezależnie od kierunku nadchodzącego). Pionowe odpowiedniki to M(w dół) i W(w górę), ale nie są używane w atoikodzie. UDLRdziałają również jak WM][po uwolnieniu swoich początkowych atomów.

W każdym razie spójrzmy na kod tam. Program zaczyna się od 5 atomów:

• RI Lu dołu po prostu uzyskać ich przyrost masy (w +), aby się (10,0), a następnie przechowywano w rozszczepienia i reaktor syntezy, odpowiednio. Użyjemy tych reaktorów do parsowania danych wejściowych base-10.
• W Lprawym górnym rogu jego masa jest zmniejszana (za pomocą _), aby stać się (0,0)i jest przechowywana z boku reaktora termojądrowego Y. Ma to na celu śledzenie liczby, którą czytamy - stopniowo zwiększamy i mnożymy ją, gdy czytamy liczby.
• W Rlewym górnym rogu ustawiono masę na kod znaku 0(48) za pomocą '0, następnie masę i energię zamieniono na, @a na koniec raz zwiększono masę, +aby dać (1,48). Następnie jest przekierowywany za pomocą zwierciadeł ukośnych \i /przechowywany w reaktorze rozszczepiającym. Użyjemy 48do odejmowania, aby przekształcić dane wejściowe ASCII w rzeczywiste wartości cyfr. Musieliśmy także zwiększyć masę, 1aby uniknąć podziału według 0.
• Wreszcie, Uw lewym dolnym rogu jest to, co faktycznie wprawia wszystko w ruch i początkowo jest używane tylko do sterowania przepływem.

Po przekierowaniu w prawo atom kontrolny uderza ?. To jest komponent wejściowy. Odczytuje znak i ustawia masę atomu na odczytaną wartość ASCII i energię na 0. Jeśli zamiast tego uderzymy w EOF, energia zostanie ustawiona na 1.

Atom kontynuuje, a następnie uderza %. To jest przełącznik lustrzany. W przypadku energii dodatniej działa to jak /lustro. Ale dla energii dodatniej działa jak \(i zmniejsza energię o 1). Tak więc, gdy czytamy postacie, atom zostanie odbity w górę i możemy przetworzyć postać. Ale kiedy skończymy z wprowadzaniem danych, atom zostanie odbity w dół i możemy zastosować inną logikę, aby uzyskać wynik. FYI, przeciwny składnik to &.

Więc na razie ruszamy atomem. Dla każdego znaku chcemy odczytać jego wartość cyfrową, dodać to do naszej sumy bieżącej, a następnie pomnożyć tę sumę bieżącą przez 10, aby przygotować się do następnej cyfry.

Atom postaci najpierw uderza w (domyślny) reaktor termojądrowy Y. Dzieli to atom i używamy lewej kopii jako atomu kontrolnego, aby zapętlić się z powrotem do komponentu wejściowego i odczytać następny znak. Odpowiednia kopia zostanie przetworzona. Rozważ przypadek, w którym przeczytaliśmy postać 3. Nasz atom będzie (51,0). Zamieniamy masę i energię @, dzięki czemu możemy skorzystać z odejmowania następnego reaktora rozszczepiającego. Reaktor odejmuje 48energię (bez zmiany masy), więc wysyła dwie kopie (0,3)- energia odpowiada teraz odczytanej cyfrze. Nadchodząca kopia jest po prostu odrzucana za pomocą ;(komponentu, który po prostu niszczy wszystkie przychodzące atomy). Będziemy kontynuować pracę z poniższą kopią. Musisz podążać jego ścieżką przez/i \trochę odzwierciedla.

@Tuż przed reaktora termojądrowego swapy masy i energii znowu tak, że dodamy (3,0)do naszej uruchomiony w sumie Y. Zauważ, że sama bieżąca suma zawsze będzie miała 0energię.

Teraz Jjest skok. To, co robi, to przeskakuje każdy nadchodzący atom do przodu dzięki swojej energii. Jeśli tak 0, atom po prostu idzie prosto. Jeśli tak, 1pominie jedną komórkę, jeśli tak, 2pominie dwie komórki i tak dalej. Energia jest wydawana w skoku, więc atom zawsze kończy się energią 0. Ponieważ suma bieżąca ma zerową energię, skok jest na razie ignorowany, a atom zostaje przekierowany do reaktora termojądrowego, {który zwielokrotnia jego masę 10. Pobrana kopia jest odrzucana, ;podczas gdy kopia wysyłana jest z powrotem do Yreaktora jako nowa suma robocza .

Powyższe powtarza się (w zabawny sposób, w którym nowe cyfry są przetwarzane przed wykonaniem poprzednich), dopóki nie trafimy do EOF. Teraz %wyśle ​​atom w dół. Chodzi o to, aby przekształcić ten atom (0,1)teraz przed uderzeniem w działający reaktor całkowity, aby a) nie wpłynęło to na sumę (masa zerowa) ib) otrzymamy energię 1przeskakiwania [. Możemy łatwo zadbać o energię $, która zwiększa energię.

Problem polega na tym ?, że masa nie resetuje się, gdy uderzasz w EOF, więc masa nadal będzie równa masie ostatniego odczytanego znaku, a energia będzie 0(ponieważ %zmniejszyła się z 1powrotem do 0). Chcemy więc pozbyć się tej masy. Aby to zrobić, ponownie zamieniamy masę i energię @.

Muszę wprowadzić jeszcze jeden komponent przed kończąc ten rozdział: Z. Jest to zasadniczo to samo co %lub &. Różnica polega na tym, że przepuszcza on atomy energii dodatniej (jednocześnie zmniejszając energię) i odchyla atomy energii nie dodatniej o 90 stopni w lewo. Możemy to wykorzystać do wyeliminowania energii atomu, zapętlając ją w Zkółko - gdy tylko energia zniknie, atom zostanie odchylony i opuści pętlę. To jest ten wzór:

/ \
[Z/

gdzie atom przesunie się w górę, gdy energia wyniesie zero. Będę używał tego wzorca w takiej czy innej formie kilka razy w innych częściach programu.

Kiedy więc atom opuści tę małą pętlę, zostanie (1,0)i zamieniany na (0,1)nią @przed uderzeniem w reaktor termojądrowy, aby uwolnić końcowy wynik wejścia. Jednak suma bieżąca zostanie zmniejszona 10-krotnie, ponieważ wstępnie pomnożono ją dla innej cyfry.

Więc teraz z energią 1ten atom przeskoczy [i wskoczy do /. To odchyla go do reaktora rozszczepienia, który przygotowaliśmy do podzielenia przez 10 i naprawienia naszego zewnętrznego mnożenia. Ponownie odrzucamy jedną połowę z, ;a drugą zachowujemy jako wyjście (tutaj reprezentowane Otym, po prostu wydrukujemy odpowiedni znak i zniszczymy atom - w pełnym programie zamiast tego używamy atomu).

itoa

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

Oczywiście musimy również przekonwertować wynik z powrotem na ciąg i wydrukować go. Po to jest ta część. Zakłada się, że dane wejściowe nie pojawiają się przed kleszczem 10 lub więcej, ale w pełnym programie, który można łatwo podać. Ten bit można znaleźć na dole pełnego programu.

Ten kod wprowadza nowy, bardzo wydajny komponent rozszczepienia: stos K. Stos jest początkowo pusty. Kiedy atom z energią nieujemną uderza w stos, atom jest po prostu wpychany na stos. Kiedy atom o ujemnej energii trafi na stos, jego masa i energia zostaną zastąpione atomem na szczycie stosu (który w ten sposób pęknie). Jeśli stos jest pusty, kierunek atomu jest odwrócony, a jego energia staje się dodatnia (tzn. Jest mnożona -1).

OK, wracając do faktycznego kodu. Ideą tego itoafragmentu jest wielokrotne przyjmowanie wejściowego modulo 10 w celu znalezienia następnej cyfry, przy jednoczesnym dzieleniu liczby całkowitej przez 10 na następną iterację. To da wszystkie cyfry w odwrotnej kolejności (od najmniej znaczącej do najbardziej znaczącej). Aby ustalić kolejność, wypychamy wszystkie cyfry na stos, a na końcu usuwamy je jeden po drugim, aby je wydrukować.

Górna połowa kodu wykonuje obliczenia cyfrowe: za Lpomocą plusów daje 10, które klonujemy i wprowadzamy do rozszczepienia i reaktora termojądrowego, abyśmy mogli podzielić i pomnożyć przez 10. Pętla zasadniczo zaczyna się po [lewym górnym rogu . Bieżąca wartość jest dzielona: jedna kopia jest dzielona przez 10, a następnie mnożona przez 10 i przechowywana w reaktorze rozszczepiającym, który następnie trafia drugą kopią na szczycie. To jest obliczane i % 10jako i - ((i/10) * 10). Zauważ też, że Adzieli wynik pośredni po dzieleniu i przed pomnożeniem, tak że możemy przejść i / 10do następnej iteracji.

%Przerywa pętlę raz zmienna iteracji uderza 0. Ponieważ jest to mniej lub bardziej do-while, kod ten będzie jeszcze praca do drukowania 0(bez tworzenia zer inaczej). Po opuszczeniu pętli chcemy opróżnić stos i wydrukować cyfry. Sjest przeciwieństwem Z, więc jest to przełącznik, który odchyli nadchodzący atom o nie dodatniej energii o 90 stopni w prawo. Tak więc atom faktycznie przesuwa się nad krawędzią od Sprostej do linii, Kaby wyskoczył z cyfry (zwróć uwagę na to, ~co zapewnia, że ​​nadchodzący atom ma energię -1). Ta cyfra jest zwiększana o, 48aby uzyskać kod ASCII odpowiedniego znaku cyfry. ADzieli cyfrę, aby wydrukować jedną kopię z!i podaj drugą kopię z powrotem do Yreaktora na następną cyfrę. Wydrukowana kopia jest używana jako następny wyzwalacz dla stosu (zwróć uwagę, że lustra wysyłają ją również wokół krawędzi, aby trafić Mw lewą stronę).

Kiedy stos jest pusty, Kodbija atom i zamienia jego energię w +1taki sposób, że przechodzi on prosto przez S. Nwypisuje nowy wiersz (tylko dlatego, że jest czysty :)). A potem atom R'0znów idzie przez tor, by znaleźć się po stronie Y. Ponieważ w pobliżu nie ma już żadnych atomów, nie zostanie to nigdy uwolnione, a program się zakończy.

Obliczanie numeru rozszczepienia: ramy

Przejdźmy do faktycznego mięsa programu. Kod jest w zasadzie portem mojej referencyjnej implementacji Mathematica:

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

gdzie divjest liczbą całkowitą w maksymalnej partycji.

Główne różnice polegają na tym, że w Fission nie możemy sobie poradzić z wartościami całkowitymi, więc robię wiele rzeczy pomnożonych przez dwa i że w Fission nie ma rekurencji. Aby obejść ten problem, wypycham wszystkie liczby całkowite na partycji w kolejce do przetworzenia później. Dla każdej liczby, którą przetwarzamy, zwiększamy licznik o jeden, a gdy kolejka jest pusta, zwalniamy licznik i wysyłamy go do wydrukowania. (Kolejka Qdziała dokładnie tak Ksamo, tylko w kolejności FIFO.)

Oto ramy tej koncepcji:

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

Najważniejsze nowe elementy to cyfry. To są teleportery. Wszystkie teleportery o tej samej cyfrze należą do siebie. Gdy atom uderzy w dowolny teleporter, natychmiast przeniesie następny teleporter w tej samej grupie, gdzie następny jest ustalany w zwykłej kolejności od lewej do prawej, od góry do dołu. Nie są one konieczne, ale pomagają w układaniu (a więc i golfie). Są też takie, Xktóre po prostu kopiują atom, wysyłając jedną kopię do przodu, a drugą do tyłu.

Do tej pory możesz samodzielnie rozwiązać większość frameworka. W lewym górnym rogu jest kolejka wartości do przetworzenia i zwalniane są pojedynczo n. Jedna kopia njest teleportowana na dół, ponieważ potrzebujemy jej podczas obliczania zakresu, druga kopia trafia do bloku u góry, który oblicza div(jest to zdecydowanie największa pojedyncza sekcja kodu). Po divobliczeniu jest duplikowany - jedna kopia inkrementuje licznik w prawym górnym rogu, w którym jest przechowywany K. Druga kopia jest teleportowana na dół. Jeśli divtak 1, natychmiast odchylamy go w górę i używamy jako wyzwalacza do następnej iteracji, bez kolejkowania żadnych nowych wartości. W przeciwnym razie używamy divin w dolnej części, aby wygenerować nowy zakres (tj. strumień atomów o odpowiednich masach, które są następnie umieszczane w kolejce), a następnie zwolnić nowy wyzwalacz po zakończeniu zakresu.

Gdy kolejka jest pusta, wyzwalacz zostanie odzwierciedlony, przechodząc prosto przez Si pojawiając się ponownie w prawym górnym rogu, skąd uwalnia licznik (wynik końcowy), z Aktórego następnie zostaje teleportowany itoaprzez 8.

Obliczanie numeru rozszczepienia: ciało pętli

Pozostały więc tylko dwie sekcje do obliczenia divi wygenerowania zakresu. Komputery divto ta część:

 ;    
 {+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/\/

Prawdopodobnie widziałeś już teraz wystarczająco dużo, aby rozwiązać to z cierpliwością. Podział wysokiego poziomu jest następujący: pierwsze 12 kolumn generuje strumień dzielników 2n. Następne 10 kolumn odfiltrowuje te, które nie spełniają OddQ@# == IntegerQ[n/#]. Następne 8 kolumn odfiltrowuje te, które nie spełniają n/# > (# - 1)/2). W końcu wpychamy wszystkie prawidłowe dzielniki na stos, a gdy skończyliśmy, opróżniamy cały stos do reaktora termojądrowego (nadpisując wszystkie oprócz ostatniego / największego dzielnika), a następnie zwalniamy wynik, a następnie eliminujemy jego energię (która nie była -zero od sprawdzania nierówności).

Jest tam wiele szalonych ścieżek, które tak naprawdę nic nie robią. Przeważnie \/\/\/\/szaleństwo na górze ( 5s są również jego częścią) i jedna ścieżka na dole (która przechodzi przez 7s). Musiałem je dodać, aby poradzić sobie z trudnymi warunkami wyścigowymi. Rozszczepienie może wykorzystywać składnik opóźniający ...

Kod, który generuje nowy zakres ni divjest następujący:

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

Najpierw obliczamy n/div - (div + 1)/2(oba wyrażenia zmiennoprzecinkowe, co daje ten sam wynik) i przechowujemy na później. Następnie generujemy zakres od w divdół do 1i dodajemy zapamiętaną wartość do każdego z nich.

W obu z nich są dwa nowe wspólne wzorce, o których powinienem wspomnieć: Jeden jest SXlub ZXtrafiony od dołu (lub wersje obrócone). Jest to dobry sposób na duplikowanie atomu, jeśli chcesz, aby jedna kopia szła prosto przed siebie (ponieważ przekierowanie wyjść reaktora termojądrowego może czasami być kłopotliwe). Te Si Zobraca atom w Xa następnie obraca lustrzaną kopiowania z powrotem do pierwotnego kierunku propagacji.

Drugi wzór to

[K
\A --> output

Jeśli przechowujemy jakąkolwiek wartość K, możemy wielokrotnie ją odzyskać, uderzając Kujemną energią z góry. APowiela wartość jesteśmy zainteresowani i wysyła co skopiować z powrotem na stos na następny raz my go potrzebujemy.

Cóż, to był całkiem tome ... ale jeśli rzeczywiście to przeżyłeś, mam nadzieję, że wpadłeś na pomysł, że Fission i͝s̢̘̗̗ ͢i̟nç̮̩r̸̭̬̱͔e̟̹̟̜͟d̙i̠͙͎̖͓̯b̘̠͎̭̰̼l̶̪̙̮̥̮y̠̠͎̺͜ ͚̬̮f̟͞u̱̦̰͍n͍ ̜̠̙t̸̳̩̝o ̫͉̙͠p̯̱̭͙̜͙͞ŕ̮͓̜o̢̙̣̭g̩̼̣̝r̤͍͔̘̟ͅa̪̜͇m̳̭͔̤̞ͅ ͕̺͉̫̀ͅi͜n̳̯̗̳͇̹.̫̞̲̞̜̳

CJam, 42 41 bajtów

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

Prosta szerokość pierwszego przejścia i stan zatrzymania pustego następnego poziomu.

Jak to działa :

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

Wypróbuj online tutaj

Python 3, 112 bajtów

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 bajty zapisane dzięki @FryAmTheEggman.

Wyjaśnienie nastąpi później ...

Dodatkowy fakt: Każda potęga 2 ma liczbę rozszczepienia równą 1. Jest tak, ponieważ suma sekwencji o parzystej długości jest zawsze sumą dwóch środkowych liczb, która jest nieparzysta, pomnożona przez połowę długości sekwencji, która jest liczbą całkowitą . Suma sekwencji nieparzystej długości to środkowa liczba pomnożona przez długość sekwencji, która jest nieparzysta. Ponieważ potęga 2 nie ma dziwnego dzielnika, można ją wyrazić jedynie jako sumę samego siebie.

Python 2, 111 102 97 bajtów

Nieco czytelne:

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)

Niezbyt czytelne:

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

Oba 97 bajtów.

bto nminus (a-1)thtrójkątna liczba. Jeśli b % a == 0, nto suma akolejnych liczb zaczynająca się od 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}))

Mniej golfa:

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)})

Pomysł polega na przetestowaniu potencjalnych przebiegów kolejnych liczb całkowitych, które sumują się n. Przebieg jest przechowywany bezpośrednio bezpośrednio jako zestaw, Ra nie za pośrednictwem jego punktów końcowych.

Sprawdzamy, jak suma bieżącego przebiegu porównuje się z żądaną sumą npoprzez ich różnicę.

• Jeśli suma jest zbyt duża, wycinamy najmniejszy element w przebiegu.
• Jeśli suma jest zbyt mała, przedłużamy bieg, zwiększając jego maksimum o 1.
• Jeśli suma jest prawidłowa, ponawiamy rekurencję, mapując fprzebieg, sumując i dodając 1 dla bieżącego węzła. Jeśli przebieg jest {n}, wypróbowaliśmy wszystkie nietrywialne możliwe kwoty, zatrzymaj rekurencję, usuwając nnajpierw.

Dzięki Sp3000 za zapisanie 3 znaków.

Python 2, 85

Jestem bardzo dumny z tej odpowiedzi, ponieważ trwa ona już kilkadziesiąt sekund dla n = 9 i 5-10 minut dla n = 10. W code golf jest to uważane za pożądany atrybut programu.

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

Istnieje również wersja zwierająca, która nie trwa tak długo i wykorzystuje tę samą ilość bajtów:

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 

Może być szybszy, ale przynajmniej przekracza domyślny limit rekurencji, gdy n przekroczy nieco 40.

Chodzi o to, aby wykonać wyszukiwanie brute force na liczbach ai dtakie, że a + a+1 + ... + a+d == nna wartości między 1 a n. f(n,a+d/n,d%n+1)Gałąź rekursji przechodzi poprzez (a, d)pary. W przypadku, gdy równość jest spełniona, udaje mi się uniknąć drogiego map(range(...))połączenia, dzieląc tylko na dwie gałęzie, niezależnie od długości sekwencji. Numery a+1poprzez dsą skupione w jednym wywołaniu fpoprzez ustawienie aparametru tak, że inny sposób podzielić się kolejność nie może być używany.

Haskell, 76 69 bajtów

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

Stosowanie:

*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]

Jak to działa:

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

Siatkówka , 66 bajtów

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

.
1

Pobiera dane wejściowe i drukuje dane wyjściowe jako jednoargumentowy.

Możesz umieścić każdą linię w jednym pliku lub uruchomić kod tak jak w przypadku -sflagi. Na przykład:

> echo -n 1111111|retina -s fission
11111

Wyjaśnienie:

• Prowadzimy listę rozdzielanych przecinkami liczb do podziału.
• Dla każdej liczby bierzemy najmniejszą wartość początkową, która może utworzyć prawidłowy podział i oddzielić go od reszty średnikiem.
• Jeśli w numerze znajduje się średnik, zamieniamy go na przecinek i ograniczamy kolejną część o odpowiedniej wielkości (długość poprzedniego elementu + 1).
• Powtarzamy krok 2 i 3, aż nastąpią zmiany.
• Dostajemy przecinek dla każdego liścia i średnik dla każdego węzła wewnętrznego oraz dodatkowy przecinek, ponieważ zaczynaliśmy od dwóch przecinków. Usuwamy przecinek i części liczb, 1a resztę konwertujemy na 1.

Stany ciągu w całym procesie z danymi wejściowymi 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

Wielkie dzięki za @MartinButtner za pomoc na czacie!

CJam (43 bajty)

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

Demo online

Jestem pewien, że brakuje mi trików z zaawansowanymi pętlami, ale to ładnie wykorzystuje właściwość CJam (która wcześniej mnie zirytowała), że w %mapie wyniki pozostają na stosie i dlatego można uzyskać do nich dostęp za $pomocą przesunięcie ujemne.

Idź, 133 bajty

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 Σ}

To jest mój pierwszy golfowy kod, przepraszam, jeśli popełniłem jakieś błędy.

Wykorzystuje to ideę, że „skład” rozszczepialny może być również postrzegany jako różnica między dwiema sekwencjami uporządkowanych liczb całkowitych. Weźmy na przykład „skład” rozszczepialny dla liczby 13. Jest to 6,7. Ale może to być postrzegane jako suma liczb całkowitych 1 ... 7 minus suma liczb całkowitych 1 ... 5

  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

Przypomnijmy wzór z czasów szkolnych Gaussa, suma 1 ... n = (n ^ 2 + n) / 2. Aby więc znaleźć skład liczb całkowitych sekwencyjnych dla danego n, moglibyśmy również powiedzieć, że szukamy „punktów końcowych” p i q w zakresie 1 ... n, aby (p ^ 2 + p) / 2 - ( q ^ 2 + q) / 2 = n. W powyższym przykładzie szukalibyśmy „punktów końcowych” 5 i 7, ponieważ 7 ^ 2 + 7 = 56/2, 5 ^ 2 + 5 = 30/2, 56 / 2-30 / 2 = 28-15 = 13

Teraz istnieje wiele możliwych sposobów na skomponowanie liczby rozszczepialnej, jak zauważył Martin 9 = 2 + 3 + 4, ale także 4 + 5. Ale wydaje się oczywiste, że „najniższa” sekwencja początkowa również będzie najdłuższa, ponieważ zajmuje więcej małe liczby do zsumowania do dużej liczby niż liczby średnie. (Niestety nie mam dowodu)

Aby znaleźć skład 9, przetestuj każdą „parę punktów końcowych”, p i q, iterując zarówno p i q oddzielnie od 0 do 9, i sprawdź, czy p ^ p + p / 2 - q ^ 2 + q / 2 = 9. Lub prościej, pomnóż równanie przez 2, aby uniknąć problemów z dzieleniem zaokrąglania i zachować całą matematykę w liczbach całkowitych. Następnie szukamy p i q takich, że (p ^ p + p) - (q ^ q + q) = 9 * 2. Pierwszym znalezionym przez nas dopasowaniem będą punkty końcowe składu rozszczepialnego, ponieważ, jak zauważono, najniższa grupa liczb będzie również najdłuższa, a my szukamy od niskiej do wysokiej (od 0 do 9). Zrywamy się z pętli, gdy tylko znajdziemy dopasowanie.

Teraz funkcja rekurencyjna znajduje te „rozszczepialne punkty końcowe” p i q dla danego n, a następnie przywołuje sama dla każdego z „dzieci” w drzewie od p do q. Dla 9 znalazłby 1 i 4 (20-2 = 18), a następnie ponownie wywołałby się na 2, 3 i 4, sumując wyniki. W przypadku liczb takich jak 4 po prostu nigdy nie znajduje dopasowania, dlatego zwraca „1”. To może być skracalne, ale jest to jak mój trzeci program go i nie jestem ekspertem od rekurencji.

Dziękuje za przeczytanie.

CJam, 40 35 33 bajtów

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

Dzięki @Optimizer za sugestie few, które pozwoliły zaoszczędzić 2 bajty.

Wypróbuj online w interpretatorze CJam .

Jak to działa

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.