Encontré esta secuencia mientras trabajaba en Evolution of OEIS , pero nunca pude publicarla como respuesta. Después de escribir una implementación de referencia en Mathematica, pensé que este es un ejercicio divertido para hacer como un desafío separado, así que aquí vamos.

¡Construyamos un reactor de fisión numérico! Considere un entero positivo N. Como ejemplo, lo veremos 24. Para obtener este número, tenemos que encontrar el mayor número de enteros positivos consecutivos que sumen N. En este caso, eso es 7 + 8 + 9 = 24. Entonces nos hemos dividido 24en tres nuevos números. Pero esto no sería un gran reactor de fisión sin reacciones en cadena. Entonces, repitamos recursivamente el proceso para estos componentes:

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

Tenga en cuenta que detenemos el proceso siempre que el número no pueda descomponerse en enteros consecutivos más pequeños. También tenga en cuenta que podríamos haber escrito 9como 4 + 5, pero 2 + 3 + 4tiene más componentes. El número de fisión de Nahora se define como el número de enteros obtenidos en este proceso, incluido él Nmismo. El árbol anterior tiene 13 nodos, entonces F(24) = 13.

Esta secuencia es la entrada OEIS A256504 .

Los primeros 40 términos, a partir de N = 1, son

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

Los primeros 1000 términos se pueden encontrar en este pastebin .

El reto

Dado un número entero positivo N, determine su número de Fisión F(N). (Por lo tanto, no necesita cubrir los principales 0listados en OEIS).

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Pregunta extra: ¿Puedes encontrar alguna propiedad interesante de esta secuencia?

Pyth, 23 22 21 bytes

Lh&lJfqbsT.:tUb)syMeJ

Esto define una función recursiva y. Pruébelo en línea: demostración

Explicación:

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)

Fisión , 1328 989 887 797 bytes

Esta respuesta es un poco irrazonablemente larga (desearía que tuviéramos regiones colapsables ) ... ¡por favor, no se olvide de pasar esto y mostrarles amor a las otras respuestas!

Trabajar en este código fue lo que inspiró este desafío. Quería agregar una respuesta en Fission a EOEIS, lo que me llevó a esta secuencia. Sin embargo, aprender realmente la fisión e implementar esto tomó algunas semanas trabajando en ello de vez en cuando. Mientras tanto, la secuencia realmente había crecido en mí, así que decidí publicar un desafío por separado (además, de todos modos, esto no habría sido particularmente lejano en EOEIS).

Así que les presento, la monstruosidad:

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

Espera que no haya una nueva línea final en la entrada, por lo que es posible que desee llamarlo así echo -n 120 | ./Fission oeis256504.fis.

El diseño probablemente aún podría ser más eficiente, por lo que creo que todavía hay mucho margen de mejora aquí (por ejemplo, esto contiene 911 581 461 374 espacios).

Antes de llegar a la explicación, una nota sobre cómo probar esto: el intérprete oficial no funciona del todo como está. a) Mirror.cppno se compila en muchos sistemas. Si se encuentra con ese problema, simplemente comente la línea ofensiva: el componente afectado (un espejo aleatorio) no se usa en este código. b) Hay un par de errores que pueden conducir a un comportamiento indefinido (y probablemente lo harán para un programa tan complejo). Puede aplicar este parche para solucionarlos. Una vez que haya hecho eso, debería poder compilar el intérprete con

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

Dato curioso: este programa utiliza casi todos los componentes que Fission tiene para ofrecer, excepto #(espejo aleatorio), :(medio espejo) -o |(espejo simple) y "(modo de impresión).

¿Qué en la tierra?

Advertencia: Esto será bastante largo ... Supongo que está realmente interesado en cómo funciona Fission y cómo se podría programar en él. Porque si no lo estás, no estoy seguro de cómo podría resumir esto. (Sin embargo, el siguiente párrafo ofrece una descripción general del lenguaje).

La fisión es un lenguaje de programación bidimensional, donde los datos y el flujo de control están representados por átomos que se mueven a través de una cuadrícula. Si has visto o usado Marbelous antes, el concepto debería ser vagamente familiar. Cada átomo tiene dos propiedades enteras: una masa no negativa y una energía arbitraria. Si la masa se vuelve negativa, el átomo se elimina de la red. En la mayoría de los casos, puede tratar la masa como el "valor" del átomo y la energía como algún tipo de metapropiedad que utilizan varios componentes para determinar el flujo de los átomos (es decir, la mayoría de los tipos de interruptores dependen del signo de la energía). Denotaré átomos por (m,E), cuando sea necesario. Al comienzo del programa, la cuadrícula comienza con un montón de(1,0)átomos de donde sea que coloque uno de los cuatro componentes UDLR(donde la letra indica la dirección en la que se mueve inicialmente el átomo). Luego, el tablero se llena con un montón de componentes que cambian la masa y la energía de los átomos, cambian sus direcciones o hacen otras cosas más sofisticadas. Para obtener una lista completa, vea la página de esolangs , pero presentaré la mayoría de ellos en esta explicación. Otro punto importante (que el programa utiliza varias veces) es que la cuadrícula es toroidal: un átomo que golpea cualquiera de los lados vuelve a aparecer en el lado opuesto, moviéndose en la misma dirección.

Escribí el programa en varias partes más pequeñas y las ensamblé al final, así es como explicaré la explicación.

atoi

Este componente puede parecer poco interesante, pero es agradable y simple y me permite presentar muchos de los conceptos importantes del flujo aritmético y de control de Fission. Por lo tanto, pasaré por esta parte con un detalle bastante meticuloso, para poder reducir las otras partes a la introducción de nuevas mecánicas de fisión y señalar componentes de nivel superior cuyo flujo de control detallado debería poder seguir usted mismo.

La fisión solo puede leer valores de bytes de caracteres individuales, no números enteros. Si bien es una práctica aceptable por aquí, pensé que mientras lo hacía, podría hacerlo bien y analizar enteros reales en STDIN. Aquí está el atoicódigo:

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

Dos de los componentes más importantes en la fisión son los reactores de fisión y fusión. Los reactores de fisión son cualquiera de V^<>(el código anterior usa <y >). Un reactor de fisión puede almacenar un átomo (enviándolo a la cuña del personaje), por defecto (2,0). Si un átomo golpea el ápice del personaje, se enviarán dos átomos nuevos a los lados. Su masa se determina dividiendo la masa entrante por la masa almacenada (es decir, dividiendo a la mitad por defecto): el átomo izquierdo obtiene este valor y el átomo derecho obtiene el resto de la masa (es decir, la masa se conserva en la fisión) . Ambos átomos salientes tendrán la energía entrante menosLa energía almacenada. Esto significa que podemos usar reactores de fisión para aritmética, tanto para sustracción como para división. Si se golpea un reactor de fisión desde el sitio, el átomo simplemente se refleja diagonalmente y luego se moverá en la dirección del ápice del personaje.

Los reactores de fusión son cualquiera de YA{}(el código anterior usa Yy {). Su función es similar: pueden almacenar un átomo (predeterminado (1,0)) y cuando se golpea desde el vértice se enviarán dos átomos nuevos a los lados. Sin embargo, en este caso los dos átomos serán idénticos, siempre retendrán la energía entrante y multiplicarán la masa entrante por la masa almacenada. Es decir, por defecto, el reactor de fusión simplemente duplica cualquier átomo que golpea su ápice. Cuando se golpean desde los lados, los reactores de fusión son un poco más complicados: el átomo también esalmacenado (independientemente de la otra memoria) hasta que un átomo golpee el lado opuesto. Cuando eso sucede, se libera un nuevo átomo en la dirección del ápice cuya masa y energía son la suma de los dos átomos antiguos. Si un nuevo átomo golpea el mismo lado antes de que un átomo coincidente llegue al lado opuesto, el átomo antiguo simplemente se sobrescribirá. Los reactores de fusión se pueden usar para implementar la suma y la multiplicación.

Otro componente simple que quiero sacar del camino es [y ]que simplemente establece la dirección del átomo a derecha e izquierda, respectivamente (independientemente de la dirección entrante). Los equivalentes verticales son M(abajo) y W(arriba) pero no se usan para el atoicódigo. UDLRTambién actúan como WM][después de liberar sus átomos iniciales.

De todos modos, veamos el código allí arriba. El programa comienza con 5 átomos:

• El Ry Len la parte inferior simplemente consigue que su incremento de masa (con +) se convierta (10,0)y luego se almacene en un reactor de fusión y de fisión, respectivamente. Utilizaremos estos reactores para analizar la entrada de base 10.
• En Lla esquina superior derecha se reduce su masa (con _) (0,0)y se almacena en el lado de un reactor de fusión Y. Esto es para hacer un seguimiento del número que estamos leyendo: aumentaremos gradualmente y lo multiplicaremos a medida que leamos números.
• En Rla esquina superior izquierda, su masa se establece en el código de caracteres de 0(48) con '0, luego la masa y la energía se intercambian @y finalmente la masa se incrementa una vez con +para dar (1,48). Luego se redirige con espejos diagonales \y /se almacena en un reactor de fisión. Usaremos la 48sustracción for para convertir la entrada ASCII en los valores reales de los dígitos. También tuvimos que aumentar la masa 1para evitar la división por 0.
• Finalmente, la Uesquina inferior izquierda es lo que realmente pone todo en movimiento y se usa inicialmente solo para controlar el flujo.

Después de ser redirigido a la derecha, el átomo de control golpea ?. Este es el componente de entrada. Lee un carácter y establece la masa del átomo al valor ASCII leído y la energía a 0. Si golpeamos EOF, la energía se establecerá en 1.

El átomo continúa y luego golpea %. Este es un interruptor de espejo. Para que la energía no positivo, esto actúa como un /espejo. Pero para la energía positiva actúa como a \(y también disminuye la energía en 1). Entonces, mientras leemos los personajes, el átomo se reflejará hacia arriba y podremos procesar el personaje. Pero cuando terminamos con la entrada, el átomo se reflejará hacia abajo y podemos aplicar una lógica diferente para recuperar el resultado. FYI, el componente opuesto es &.

Así que tenemos un átomo en movimiento por ahora. Lo que queremos hacer para cada personaje es leer el valor de su dígito, agregarlo a nuestro total acumulado y luego multiplicar ese total acumulado por 10 para prepararse para el siguiente dígito.

El átomo de caracteres golpea primero un reactor de fusión (predeterminado) Y. Esto divide el átomo y usamos la copia de la izquierda como un átomo de control para volver al componente de entrada y leer el siguiente carácter. Se procesará la copia a la derecha. Considere el caso en el que hemos leído el personaje 3. Nuestro átomo lo será (51,0). Intercambiamos masa y energía con @, de modo que podamos hacer uso de la resta del próximo reactor de fisión. El reactor resta 48la energía (sin cambiar la masa), por lo que envía dos copias de (0,3): la energía ahora corresponde al dígito que hemos leído. La copia saliente simplemente se descarta con ;(un componente que simplemente destruye todos los átomos entrantes). Seguiremos trabajando con la copia anterior. Tendrás que seguir su camino a través del/y se \refleja un poco.

El @justo antes de que la masa del reactor de fusión permutas y la energía de nuevo, de manera que vamos a añadir (3,0)a nuestra total acumulado en la Y. Tenga en cuenta que el total acumulado en sí mismo siempre tendrá 0energía.

Ahora Jes un salto. Lo que hace es saltar cualquier átomo entrante hacia adelante por su energía. Si es así 0, el átomo sigue moviéndose directamente. Si es 1así, saltará una celda, si es 2así, saltará dos celdas y así sucesivamente. La energía se gasta en el salto, por lo que el átomo siempre termina con energía 0. Como el total acumulado no tiene energía cero, el salto se ignora por ahora y el átomo se redirige al reactor de fusión {que multiplica su masa por 10. La copia descendente se descarta ;mientras que la copia ascendente se retroalimenta al Yreactor como el nuevo total acumulado .

Lo anterior sigue repitiéndose (de una manera divertida y canalizada donde se procesan los nuevos dígitos antes de que se hagan los anteriores) hasta que lleguemos a EOF. Ahora el %enviará el átomo hacia abajo. La idea es convertir este átomo (0,1)ahora antes de golpear el reactor total en funcionamiento para que a) el total no se vea afectado (masa cero) yb) obtengamos una energía de 1saltar sobre el [. Podemos cuidar fácilmente la energía con $, lo que incrementa la energía.

El problema es que ?no restablece la masa cuando golpeas EOF, por lo que la masa seguirá siendo la del último personaje leído y la energía lo será 0(porque %disminuyó el 1regreso a 0). Entonces queremos deshacernos de esa masa. Para hacer eso intercambiamos masa y energía @nuevamente.

Necesito introducir un componente más antes de terminar esta sección: Z. Esto es esencialmente lo mismo que %o &. La diferencia es que permite que los átomos de energía positiva pasen directamente (mientras disminuye la energía) y desvía los átomos de energía no positiva 90 grados a la izquierda. Podemos usar esto para eliminar la energía de un átomo haciendo un bucle a través de ella Zuna y otra vez; tan pronto como la energía se haya ido, el átomo se desviará y abandonará el bucle. Ese es este patrón:

/ \
[Z/

donde el átomo se moverá hacia arriba una vez que la energía sea cero. Usaré este patrón de una forma u otra varias veces en las otras partes del programa.

Entonces, cuando el átomo abandona este pequeño bucle, será (1,0)reemplazado (0,1)por @antes de golpear el reactor de fusión para liberar el resultado final de la entrada. Sin embargo, el total acumulado estará apagado por un factor de 10, porque ya lo hemos multiplicado tentativamente por otro dígito.

Entonces, ahora con energía 1, este átomo se saltará [y saltará al /. Esto lo desvía en un reactor de fisión que hemos preparado para dividir por 10 y arreglar nuestra multiplicación extraña. Nuevamente, descartamos una mitad con ;y conservamos la otra como salida (aquí representada con la Ocual simplemente imprimiría el carácter correspondiente y destruiría el átomo; en el programa completo seguimos usando el átomo).

itoa

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

Por supuesto, también necesitamos convertir el resultado a una cadena e imprimirlo. Para eso es esta parte. Esto supone que la entrada no llega antes del tick 10 más o menos, sino en el programa completo que se da fácilmente. Este bit se puede encontrar en la parte inferior del programa completo.

Este código introduce un nuevo componente de fisión muy poderoso: la pila K. La pila está inicialmente vacía. Cuando un átomo con energía no negativa golpea la pila, el átomo simplemente es empujado hacia la pila. Cuando un átomo con energía negativa golpea la pila, su masa y energía serán reemplazadas por el átomo en la parte superior de la pila (que de este modo se abre). Sin embargo, si la pila está vacía, la dirección del átomo se invierte y su energía se vuelve positiva (es decir, se multiplica por -1).

Bien, volviendo al código real. La idea del itoafragmento es tomar repetidamente el módulo de entrada 10 para encontrar el siguiente dígito mientras se divide la entrada por 10 para la próxima iteración. Esto arrojará todos los dígitos en orden inverso (de menos significativo a más significativo). Para arreglar el orden, empujamos todos los dígitos en una pila y al final los sacamos uno por uno para imprimirlos.

La mitad superior del código hace el cálculo de dígitos: el Lcon las más da un 10 que clonamos y alimentamos en un reactor de fisión y un reactor de fusión para que podamos dividir y multiplicar por 10. El ciclo esencialmente comienza después de la [esquina superior izquierda . El valor actual se divide: una copia se divide por 10, luego se multiplica por 10 y se almacena en un reactor de fisión, que luego es golpeado por la otra copia en el ápice. Esto se calcula i % 10como i - ((i/10) * 10). Tenga en cuenta también que Adivide el resultado intermedio después de la división y antes de la multiplicación, de modo que podamos alimentar i / 10la próxima iteración.

El %aborta el bucle una vez que la variable de iteración golpea 0. Como esto es más o menos un bucle do-while, este código incluso el trabajo para la impresión 0(sin crear ceros a la izquierda de otro tipo). Una vez que salimos del bucle, queremos vaciar la pila e imprimir los dígitos. Ses lo opuesto a Z, por lo que es un interruptor que desviará un átomo entrante con energía no positiva 90 grados a la derecha. Por lo tanto, el átomo en realidad se mueve sobre el borde de la Slínea recta a la Kde un dígito (tenga en cuenta ~que garantiza que el átomo entrante tenga energía -1). Ese dígito se incrementa 48para obtener el código ASCII del carácter de dígito correspondiente. El Adivide el dígito para imprimir una copia con!y vuelva a alimentar la otra copia al Yreactor para el siguiente dígito. La copia que se imprime se usa como el siguiente disparador para la pila (tenga en cuenta que los espejos también la envían alrededor del borde para golpearla Mdesde la izquierda).

Cuando la pila está vacía, Kreflejará el átomo y convertirá su energía en +1tal, que pasará directamente a través del S. Nimprime una nueva línea (solo porque está ordenada :)). Y luego el átomo se vuelve a atravesar R'0para terminar en el lado del Y. Como no hay más átomos alrededor, esto nunca se lanzará y el programa finalizará.

Calcular el número de fisión: el marco

Vayamos a la carne real del programa. El código es básicamente un puerto de mi implementación de referencia de 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)]
]

donde dives el número de enteros en la partición máxima.

Las principales diferencias son que no podemos tratar con valores de medio entero en Fission, por lo que estoy haciendo muchas cosas multiplicadas por dos, y que no hay recurrencia en Fission. Para evitar esto, estoy empujando todos los enteros en una partición en una cola para que se procesen más tarde. Para cada número que procesamos, incrementaremos un contador en uno y una vez que la cola esté vacía, liberaremos el contador y lo enviaremos para que se imprima. (Una cola, Qfunciona exactamente igual K, solo en orden FIFO).

Aquí hay un marco para este concepto:

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

Los nuevos componentes más importantes son los dígitos. Estos son teletransportadores. Todos los teletransportadores con el mismo dígito pertenecen juntos. Cuando un átomo golpea cualquier teletransportador, se moverá inmediatamente al siguiente teletransportador en el mismo grupo, donde el siguiente se determina en el orden habitual de izquierda a derecha, de arriba a abajo. Estos no son necesarios, pero ayudan con el diseño (y por lo tanto un poco de golf). También existe el Xque simplemente duplica un átomo, enviando una copia hacia adelante y la otra hacia atrás.

A estas alturas, es posible que pueda resolver la mayor parte del marco usted mismo. La esquina superior izquierda tiene la cola de valores aún por procesar y se libera uno na la vez. Una copia de nse teletransporta a la parte inferior porque la necesitamos al calcular el rango, la otra copia va al bloque en la parte superior que calcula div(esta es, con mucho, la sección más grande del código). Una vez que divse ha calculado, se duplica: una copia incrementa un contador en la esquina superior derecha, que se almacena K. La otra copia se teletransporta a la parte inferior. Si divfue así 1, lo desviamos hacia arriba inmediatamente y lo usamos como un disparador para la próxima iteración, sin enquistar ningún valor nuevo. De lo contrario, usamos divyn en la sección en la parte inferior para generar el nuevo rango (es decir, una corriente de átomos con las masas correspondientes que posteriormente se ponen en la cola), y luego suelte un nuevo disparador después de que se haya completado el rango.

Una vez que la cola está vacía, el disparador se reflejará, pasará directamente a través de él Sy volverá a aparecer en la esquina superior derecha, donde libera el contador (el resultado final) A, que luego se teletransporta a itoatravés de 8.

Calcular el número de fisión: el cuerpo del bucle

Entonces, todo lo que queda son las dos secciones para calcular divy generar el rango. La computación dives esta parte:

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

Probablemente has visto suficiente ahora para resolver esto con paciencia. El desglose de alto nivel es el siguiente: las primeras 12 columnas generan un flujo de divisores de 2n. Las siguientes 10 columnas filtran las que no satisfacen OddQ@# == IntegerQ[n/#]. Las siguientes 8 columnas filtran las que no satisfacen n/# > (# - 1)/2). Finalmente, empujamos todos los divisores válidos en una pila, y una vez que terminamos, vaciamos toda la pila en un reactor de fusión (sobrescribiendo todos menos el último / mayor divisor) y luego liberamos el resultado, seguido de eliminar su energía (que no era -cero de verificar la desigualdad).

Hay muchos caminos locos que realmente no hacen nada. Predominantemente, la \/\/\/\/locura en la parte superior (las 5s también son parte de ella) y un camino alrededor de la parte inferior (que pasa por las 7s). Tuve que agregar estos para lidiar con algunas condiciones de carrera desagradables. La fisión podría usar un componente de retraso ...

El código que genera el nuevo rango ny dives el siguiente:

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

Primero calculamos n/div - (div + 1)/2(ambos términos con piso, que produce el mismo resultado) y almacenamos para más adelante. Luego generamos un rango de divabajo hacia abajo 1y agregamos el valor almacenado a cada uno de ellos.

Hay dos nuevos patrones comunes en ambos, que debo mencionar: uno es SXo ZXgolpear desde abajo (o versiones rotadas). Esta es una buena manera de duplicar un átomo si desea que una copia siga adelante (ya que la redirección de las salidas de un reactor de fusión a veces puede ser engorrosa). El So Zgira el átomo hacia adentro Xy luego gira la copia reflejada nuevamente en la dirección original de propagación.

El otro patrón es

[K
\A --> output

Si almacenamos algún valor K, podemos recuperarlo repetidamente golpeando Kcon energía negativa desde la parte superior. El Aduplica el valor que nos interesa y envía lo que copiar de nuevo a la derecha en la pila para la próxima vez que lo necesitamos.

Bueno, eso fue bastante tomo ... pero si realmente superaste esto, espero que tengas la idea de que 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 bytes

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

Un primer recorrido de Breadth simple y una condición de detención del siguiente nivel vacío.

Cómo funciona :

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

Pruébalo en línea aquí

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 guardados gracias a @FryAmTheEggman.

Explicación que viene más tarde ...

Dato extra: cada potencia de 2 tiene un número de Fisión de 1. Esto se debe a que la suma de una secuencia de longitud par es siempre la suma de los dos números medios, que es impar, multiplicado por la mitad de la longitud de la secuencia, que es entera . La suma de una secuencia de longitud impar es el número del medio multiplicado por la longitud de la secuencia, que es impar. Entonces, debido a que una potencia de 2 no tiene un divisor impar, solo se puede expresar como la suma de sí misma.

Python 2, 111 102 97 bytes

Algo legible:

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)

No tan legible:

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

Ambos 97 bytes.

bes el nmenos el (a-1)thnúmero triangular. Si b % a == 0, entonces nes la suma de anúmeros consecutivos a partir de b.

Pitón 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}))

Menos golfizado:

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

La idea es probar posibles corridas de enteros consecutivos que sumen n. La ejecución se almacena directamente directamente como un conjunto en Rlugar de a través de sus puntos finales.

Verificamos cómo la suma de la ejecución actual se compara con la suma deseada a ntravés de su diferencia.

• Si la suma es demasiado grande, cortamos el elemento más pequeño de la ejecución.
• Si la suma es demasiado pequeña, ampliamos la carrera haciendo que su máximo sea mayor en 1.
• Si la suma es correcta, recurrimos, asignamos fa la ejecución, sumamos y sumamos 1 para el nodo actual. Si la ejecución es {n}, hemos intentado todas las sumas posibles no triviales, detenga la recursión eliminando nprimero.

Gracias a Sp3000 por guardar 3 caracteres.

Pitón 2, 85

Estoy muy orgulloso de esta respuesta porque ya lleva decenas de segundos para n = 9 y 5-10 minutos para n = 10. En el código de golf esto se considera un atributo deseable de un programa.

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

También hay una versión de cortocircuito que no toma tanto tiempo y usa la misma cantidad de bytes:

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 

Puede ser más rápido, pero al menos excede el límite de recursión predeterminado una vez que n supera un poco más de 40.

La idea es hacer una búsqueda de fuerza bruta para números ay dtal que a + a+1 + ... + a+d == n, en valores entre 1 y n. La f(n,a+d/n,d%n+1)rama de la recursión recorre los (a, d)pares. En el caso de que se satisfaga la igualdad, me las arreglo para evitar una map(range(...))llamada costosa dividiéndome en solo dos ramas, independientemente de la duración de la secuencia. Los números a+1a través dse agrupan en una sola llamada del ffijando el aparámetro para que de una manera diferente para dividir la secuencia no se puede utilizar.

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]

Uso:

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

Cómo funciona:

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

Retina , 66 bytes

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

.
1

Toma la entrada e imprime la salida en unario.

Puede poner cada línea en un solo archivo o ejecutar el código tal como está con la -sbandera. P.ej:

> echo -n 1111111|retina -s fission
11111

Explicación:

• Mantenemos una lista delimitada por comas de los números que se dividirán.
• Para cada número tomamos el valor inicial más pequeño que puede crear una división válida y delimitarlo del resto con un punto y coma.
• Si hay un punto y coma dentro de un número, lo cambiamos a una coma y delimitamos la siguiente parte del número del tamaño adecuado (longitud del elemento anterior + 1).
• Repetimos los pasos 2 y 3 hasta que ocurran los cambios.
• Obtenemos una coma para cada hoja y un punto y coma para cada nodo interno más una coma adicional porque comenzamos con dos comas. Entonces eliminamos una coma y las partes ( 1's) de los números y convertimos el resto a 1' s.

Los estados de la cadena a lo largo del proceso con entrada 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

¡Muchas gracias a @MartinButtner por la ayuda en el chat!

CJam (43 bytes)

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

Demostración en línea

Estoy seguro de que me faltan algunos trucos con los bucles avanzados, pero esto explota perfectamente la propiedad CJam (que anteriormente me ha molestado) de que dentro de un %mapa los resultados permanecen en la pila y, por lo tanto, se puede acceder $con un compensación negativa

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

Este es mi primer código de golf, perdón si cometí algún error.

Esto utiliza la idea de que la "composición" fisionable también puede verse como una diferencia entre dos secuencias de enteros ordenados. Por ejemplo, tome la "composición" fisionable para el número 13. Es 6,7. Pero puede verse como la suma de los enteros 1 ... 7 menos la suma de los enteros 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

Recuerde la fórmula de los días escolares de Gauss, suma 1 ... n = (n ^ 2 + n) / 2. Entonces, para encontrar una composición de enteros secuenciales para un n dado, también podríamos decir que estamos buscando 'puntos finales' p y q a lo largo del rango 1 ... n para que (p ^ 2 + p) / 2 - ( q ^ 2 + q) / 2 = n. En el ejemplo anterior, habríamos estado buscando 'puntos finales' 5 y 7 porque 7 ^ 2 + 7 = 56/2, 5 ^ 2 + 5 = 30/2, 56 / 2-30 / 2 = 28-15 = 13.

Ahora hay varias formas posibles de componer un número fisionable, como Martin señaló 9 = 2 + 3 + 4 pero también 4 + 5. Pero parece obvio que la secuencia de inicio "más baja" también será la más larga, porque toma más números pequeños para resumir en un número grande de lo que lo hacen los números medianos. (No tengo pruebas por desgracia)

Entonces, para encontrar la composición de 9, pruebe cada 'par de puntos finales', p y q, iterando p y q por separado de 0 a 9, y pruebe si p ^ p + p / 2 - q ^ 2 + q / 2 = 9. O, más simplemente, multiplique la ecuación por 2, para evitar los problemas de división del redondeo y mantener todas las matemáticas en números enteros. Entonces estamos buscando p y q tal que (p ^ p + p) - (q ^ q + q) = 9 * 2. La primera coincidencia que encontraremos serán los puntos finales de la composición fisionable porque, como se señaló, el grupo de números más bajo también será el más largo, y estamos buscando de bajo a alto (0 a 9). Salimos del círculo tan pronto como encontremos una coincidencia.

Ahora la función recursiva encuentra esos 'puntos finales fisionables' p y q para el n dado, luego se recupera para cada uno de los 'hijos' en el árbol de p a q. Para 9, encontraría 1 y 4, (20-2 = 18) y luego se volvería a llamar a sí mismo en 2, 3 y 4, sumando los resultados. Para números como 4, simplemente nunca encuentra una coincidencia, por lo que devuelve '1'. Esto podría acortarse, pero este es como mi tercer programa y no soy un experto en recursión.

Gracias por leer.

CJam, 40 35 33 bytes

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

Gracias a @Optimizer por sugerir few, que ahorró 2 bytes.

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

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.