Encontrei essa sequência enquanto trabalhava no Evolution of OEIS , mas nunca consegui publicá-la como resposta. Depois de escrever uma implementação de referência no Mathematica, pensei que este é um exercício divertido de ser feito como um desafio separado. Então, aqui vamos nós.

Vamos construir um reator de fissão numérica! Considere um número inteiro positivo N. Como exemplo, veremos 24. Para fissão esse número, temos que encontrar o maior número de números inteiros positivos consecutivos que somam N. Nesse caso, é isso 7 + 8 + 9 = 24. Então, dividimos 24em três novos números. Mas isso não seria um reator de fissão sem reações em cadeia. Então, vamos repetir recursivamente o processo para esses componentes:

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

Observe que paramos o processo sempre que o número não pode ser decomposto em números inteiros consecutivos menores. Observe também que poderíamos ter escrito 9como 4 + 5, mas 2 + 3 + 4possui mais componentes. O número de fissão de Nagora é definido como o número de números inteiros obtidos neste processo, incluindo Nele próprio. A árvore acima tem 13 nós, então F(24) = 13.

Esta sequência é a entrada OEIS A256504 .

Os primeiros 40 termos, a partir de N = 1, são

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

Os primeiros 1000 termos podem ser encontrados nesta pasta .

O desafio

Dado um número inteiro positivo N, determine seu número de fissão F(N). (Portanto, você não precisa cobrir os principais 0listados no OEIS.)

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e exibindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Pergunta bônus: Você pode encontrar propriedades interessantes dessa sequência?

Pitão, 23 22 21 bytes

Lh&lJfqbsT.:tUb)syMeJ

Isso define uma função recursiva y. Experimente online: Demonstração

Explicação:

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)

Fissão , 1328 989 887 797 bytes

Esta resposta é um pouco irracionalmente longa (eu gostaria que tivéssemos regiões dobráveis ) ... por favor, não se esqueça de passar por isso e mostrar às outras respostas um pouco de amor!

Trabalhar nesse código foi o que inspirou esse desafio. Eu queria adicionar uma resposta em Fission ao EOEIS, o que me levou a essa sequência. No entanto, realmente aprender a Fissão e implementá-la levou algumas semanas trabalhando dentro e fora. Enquanto isso, a sequência realmente cresceu em mim, então eu decidi postar um desafio separado para ela (além disso, isso não teria sido particularmente distante na EOEIS).

Então, apresento a vocês a Monstrosity:

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

Ele espera que não haja uma nova linha à direita na entrada; portanto, convém chamá-lo assim echo -n 120 | ./Fission oeis256504.fis.

O layout provavelmente ainda pode ser mais eficiente, então acho que ainda há muito espaço para melhorias aqui (por exemplo, isso contém 911 581 461 374 espaços).

Antes de chegarmos à explicação, uma observação sobre o teste: o intérprete oficial não funciona totalmente como está. a) Mirror.cppnão compila em muitos sistemas. Se você encontrar esse problema, basta comentar a linha incorreta - o componente afetado (um espelho aleatório) não é usado neste código. b) Existem alguns erros que podem levar a um comportamento indefinido (e provavelmente resultarão em um programa desse complexo). Você pode aplicar esse patch para corrigi-los. Depois de fazer isso, você poderá compilar o intérprete com

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

Curiosidade: Este programa usa quase todos os componentes que a Fissão tem a oferecer, exceto #(espelho aleatório), :(meio espelho) -ou |(espelho simples) e "(modo de impressão).

O que na Terra?

Aviso: Isso será bastante longo ... Suponho que você esteja realmente interessado em saber como a Fissão funciona e como se pode programar nela. Porque se você não estiver, não tenho certeza de como poderia resumir isso. (O próximo parágrafo fornece uma descrição geral do idioma.)

A fissão é uma linguagem de programação bidimensional, onde dados e fluxo de controle são representados por átomos se movendo através de uma grade. Se você já viu ou usou o Marbelous antes, o conceito deve ser vagamente familiar. Cada átomo tem duas propriedades inteiras: uma massa não negativa e uma energia arbitrária. Se a massa se tornar negativa, o átomo é removido da grade. Na maioria dos casos, você pode tratar a massa como o "valor" do átomo e a energia como algum tipo de metapropriedade usada por vários componentes para determinar o fluxo dos átomos (ou seja, a maioria dos tipos de comutadores depende do sinal de a energia). Denotarei átomos por (m,E), quando necessário. No início do programa, a grade começa com um monte de(1,0)átomos de onde você coloca um dos quatro componentes UDLR(onde a letra indica a direção em que o átomo está se movendo inicialmente). O quadro é então preenchido com um monte de componentes que alteram a massa e a energia dos átomos, mudam de direção ou fazem outras coisas mais sofisticadas. Para uma lista completa, consulte a página esolangs , mas apresentarei a maioria deles nesta explicação. Outro ponto importante (que o programa utiliza várias vezes) é que a grade é toroidal: um átomo que atinge qualquer um dos lados reaparece no lado oposto, movendo-se na mesma direção.

Escrevi o programa em várias partes menores e montei-as no final, e é assim que vou explicar a explicação.

atoi

Esse componente pode parecer bastante desinteressante, mas é agradável e simples e permite que eu introduza muitos dos conceitos importantes do fluxo aritmético e de controle da Fission. Portanto, irei abordar esta parte com detalhes bastante meticulosos, para que eu possa reduzir as outras partes à introdução de novas mecânicas de Fissão e apontar componentes de nível superior cujo fluxo de controle detalhado você deve seguir.

A fissão só pode ler valores de bytes de caracteres individuais, não números inteiros. Embora seja uma prática aceitável por aqui, imaginei que, enquanto fazia isso, poderia fazer o certo e analisar números inteiros reais no STDIN. Aqui está o atoicódigo:

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

Dois dos componentes mais importantes na fissão são os reatores de fissão e fusão. Reatores de fissão são qualquer um V^<>(o código acima usa <e >). Um reator de fissão pode armazenar um átomo (enviando-o para a cunha do personagem), sendo o padrão (2,0). Se um átomo atingir o ápice do personagem, dois novos átomos serão enviados para os lados. Sua massa é determinada dividindo-se a massa recebida pela massa armazenada (ou seja, diminuindo pela metade) - o átomo à esquerda obtém esse valor e o átomo à direita obtém o restante da massa (ou seja, a massa é conservada na fissão) . Ambos os átomos de saída terão a energia recebida menosa energia armazenada. Isso significa que podemos usar reatores de fissão para aritmética - tanto para subtração quanto para divisão. Se um reator de fissão é atingido a partir do local, o átomo é simplesmente refletido na diagonal e depois se move na direção do ápice do personagem.

Reatores de fusão são qualquer um YA{}(o código acima usa Ye {). Sua função é semelhante: eles podem armazenar um átomo (padrão (1,0)) e, quando atingidos do ápice, dois novos átomos serão enviados para os lados. No entanto, neste caso, os dois átomos serão idênticos, sempre retendo a energia recebida e multiplicando a massa recebida pela massa armazenada. Ou seja, por padrão, o reator de fusão simplesmente duplica qualquer átomo atingindo seu ápice. Quando atingidos pelos lados, os reatores de fusão são um pouco mais complicados: o átomo também éarmazenado (independentemente da outra memória) até que um átomo atinja o lado oposto. Quando isso acontece, um novo átomo é liberado na direção do ápice, cuja massa e energia são a soma dos dois átomos antigos. Se um novo átomo atinge o mesmo lado antes de um átomo correspondente atingir o lado oposto, o átomo antigo será simplesmente substituído. Os reatores de fusão podem ser usados ​​para implementar adição e multiplicação.

Outro componente simples Eu quero ficar fora do caminho é [e ]que simplesmente definir a direção do átomo para a direita e esquerda, respectivamente (independentemente da direção de entrada). Os equivalentes verticais são M(para baixo) e W(para cima), mas não são usados ​​para o atoicódigo. UDLRtambém atuam como WM][após liberar seus átomos iniciais.

De qualquer forma, vamos olhar o código lá em cima. O programa começa com 5 átomos:

• O Re Lna parte inferior simplesmente obtêm seu incremento de massa (com +) (10,0)e depois são armazenados em um reator de fissão e de fusão, respectivamente. Usaremos esses reatores para analisar a entrada da base 10.
• O Lcanto superior direito faz com que sua massa diminua (com _) para se tornar (0,0)e é armazenada no lado de um reator de fusão Y. Isso é para acompanhar o número que estamos lendo - aumentaremos gradualmente e multiplicaremos isso à medida que lermos números.
• No Rcanto superior esquerdo, sua massa é definida como o código de caractere de 0(48) com '0, então massa e energia são trocadas @e, finalmente, a massa é incrementada uma vez com +a doação (1,48). Em seguida, é redirecionado com espelhos diagonais \e /armazenado em um reator de fissão. Usaremos a 48subtração for para transformar a entrada ASCII nos valores reais dos dígitos. Também tivemos que aumentar a massa 1para evitar a divisão 0.
• Finalmente, Uno canto inferior esquerdo é o que realmente coloca tudo em movimento e é inicialmente usado apenas para controlar o fluxo.

Depois de ser redirecionado para a direita, o átomo de controle é atingido ?. Este é o componente de entrada. Ele lê um caractere e define a massa do átomo para o valor ASCII lido e a energia para 0. Se atingirmos EOF, a energia será ajustada para 1.

O átomo continua e depois bate %. Este é um interruptor de espelho. Para energia não positiva, isso age como um /espelho. Mas, para energia positiva, age como um \(e também diminui a energia em 1). Então, enquanto estivermos lendo os personagens, o átomo será refletido para cima e podemos processar o personagem. Mas quando terminarmos a entrada, o átomo será refletido para baixo e podemos aplicar uma lógica diferente para recuperar o resultado. Para sua informação, o componente oposto é &.

Então, temos um átomo subindo por enquanto. O que queremos fazer para cada caractere é ler o valor do dígito, adicionar isso ao total da corrida e multiplicar esse total por 10 para preparar o próximo dígito.

O átomo de caractere primeiro atinge um reator de fusão (padrão) Y. Isso divide o átomo e usamos a cópia à esquerda como um átomo de controle para retornar ao componente de entrada e ler o próximo caractere. A cópia correta será processada. Considere o caso em que lemos o personagem 3. Nosso átomo será (51,0). Trocamos massa e energia com @, de modo que possamos fazer uso da subtração do próximo reator de fissão. O reator subtrai 48a energia (sem alterar a massa), então envia duas cópias de (0,3)- a energia agora corresponde ao dígito que lemos. A cópia inicial é simplesmente descartada ;(um componente que destrói todos os átomos recebidos). Continuaremos trabalhando com a cópia descendente. Você precisará seguir seu caminho através do/e \espelha um pouco.

O @pouco antes do reator de fusão troca massa e energia novamente, de modo que adicionaremos (3,0)ao total em execução no Y. Observe que o total em execução, portanto, sempre terá 0energia.

Agora Jé um salto. O que ele faz é pular qualquer átomo recebido para a frente por sua energia. Se for 0, o átomo continua seguindo em frente. Se for 1, pulará uma célula, se for 2, pulará duas células e assim por diante. A energia é gasta no salto, então o átomo sempre acaba com energia 0. Como o total em execução tem energia zero, o salto é ignorado por enquanto e o átomo é redirecionado para o reator de fusão {que multiplica sua massa por 10. A cópia descendente é descartada ;enquanto a cópia descendente é realimentada no Yreator como o novo total em execução.

O exemplo acima continua repetindo (de uma maneira engraçada em pipeline, onde novos dígitos estão sendo processados ​​antes que os anteriores sejam feitos) até atingirmos o EOF. Agora o %enviará o átomo para baixo. A idéia é transformar esse átomo (0,1)agora antes de atingir o reator total em funcionamento, de modo que a) o total não seja afetado (massa zero) eb) tenhamos energia 1para pular o [. Podemos cuidar facilmente da energia $que aumenta a energia.

A questão é que ?não redefinir a massa quando você estiver atingindo o EOF, portanto a massa ainda será a do último caractere lido, e a energia será 0(porque %diminuiu a 1volta para 0). Então, queremos nos livrar dessa massa. Para fazer isso, trocamos massa e energia @novamente.

Eu preciso introduzir mais um componente antes de terminar esta seção: Z. É essencialmente o mesmo que %ou &. A diferença é que ela permite que átomos de energia positiva passem direto (enquanto diminui a energia) e desvia os átomos de energia não positiva 90 graus para a esquerda. Podemos usar isso para eliminar a energia de um átomo, repetindo-a Zrepetidamente - assim que a energia acabar, o átomo será desviado e sairá do loop. Esse é esse padrão:

/ \
[Z/

onde o átomo se moverá para cima quando a energia for zero. Usarei esse padrão de uma forma ou de outra várias vezes nas outras partes do programa.

Então, quando o átomo sair desse pequeno loop, ele será (1,0)trocado (0,1)pelo @antes de atingir o reator de fusão para liberar o resultado final da entrada. No entanto, o total atual será reduzido em um fator de 10, porque já o multiplicamos por outro dígito.

Então agora, com energia 1, esse átomo irá pular [e pular para dentro /. Isso o desvia para um reator de fissão que preparamos para dividir por 10 e corrigir nossa multiplicação estranha. Novamente, descartamos uma metade com ;e mantemos a outra como saída (aqui representada com a Oqual simplesmente imprimiríamos o caractere correspondente e destruiríamos o átomo - no programa completo, continuamos usando o átomo).

itoa

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

Obviamente, também precisamos converter o resultado novamente em uma string e imprimi-lo. É para isso que serve essa parte. Isso pressupõe que a entrada não chegue antes do ponto 10, mas no programa completo que é facilmente fornecido. Este bit pode ser encontrado na parte inferior do programa completo.

Este código apresenta um novo e poderoso componente de fissão: a pilha K. A pilha está inicialmente vazia. Quando um átomo com energia não negativa atinge a pilha, o átomo é simplesmente empurrado para a pilha. Quando um átomo com energia negativa atinge a pilha, sua massa e energia serão substituídas pelo átomo no topo da pilha (que é assim liberado). Se a pilha estiver vazia, a direção do átomo é revertida e sua energia se torna positiva (isto é, é multiplicada por -1).

Ok, voltando ao código real. A idéia do itoatrecho é pegar repetidamente o módulo de entrada 10 para encontrar o próximo dígito enquanto divide a entrada por 10 para a próxima iteração. Isso produzirá todos os dígitos na ordem inversa (do menos significativo para o mais significativo). Para fixar a ordem, colocamos todos os dígitos em uma pilha e, no final, os separamos um a um para imprimi-los.

A metade superior do código calcula os dígitos: o Lcom as vantagens dá um 10, que clonamos e alimentamos em um reator de fissão e fusão, para que possamos dividir e multiplicar por 10. O loop começa essencialmente após o [canto superior esquerdo . O valor atual é dividido: uma cópia é dividida por 10, depois multiplicada por 10 e armazenada em um reator de fissão, que é atingido pela outra cópia no ápice. Isso calcula i % 10como i - ((i/10) * 10). Observe também que Adivide o resultado intermediário após a divisão e antes da multiplicação, para que possamos alimentar i / 10a próxima iteração.

A %aborta o loop uma vez que a variável iteração atinge 0. Uma vez que este é mais ou menos um do-while loop, este código seria mesmo trabalho para a impressão 0(sem criar zeros à esquerda em contrário). Uma vez que deixamos o loop, queremos esvaziar a pilha e imprimir os dígitos. Sé o oposto de Z, portanto, é um interruptor que desviará um átomo de entrada com energia não positiva 90 graus para a direita. Portanto, o átomo realmente se move sobre a borda, da Sreta para a, Kpara sair de um dígito (observe o ~que garante que o átomo recebido tenha energia -1). Esse dígito é incrementado por 48para obter o código ASCII do caractere de dígito correspondente. O Adivide o dígito para imprimir uma cópia com!e alimente a outra cópia novamente no Yreator para o próximo dígito. A cópia impressa é usada como o próximo gatilho para a pilha (observe que os espelhos também a enviam pela borda para atingir Ma esquerda).

Quando a pilha está vazia, Kela refletirá o átomo e transformará sua energia em +1, de modo que passe diretamente através do S. Nimprime uma nova linha (apenas porque é elegante :)). E então o átomo passa R'0novamente para o lado do Y. Como não há mais átomos por perto, isso nunca será lançado e o programa será encerrado.

Cálculo do número de fissão: a estrutura

Vamos para a carne real do programa. O código é basicamente uma porta da minha implementação de referência do 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)]
]

onde divé o número de números inteiros na partição máxima.

As principais diferenças são que não podemos lidar com valores de meio inteiro na Fissão, então estou fazendo muitas coisas multiplicadas por dois e que não há recursão na Fissão. Para contornar isso, estou pressionando todos os números inteiros em uma partição em uma fila para serem processados ​​posteriormente. Para cada número que processamos, incrementaremos um contador em um e, quando a fila estiver vazia, liberaremos o contador e enviaremos para impressão. (Uma fila,, Qfunciona exatamente da mesma forma K, apenas na ordem FIFO.)

Aqui está uma estrutura para este conceito:

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

Os novos componentes mais importantes são os dígitos. Estes são teleportadores. Todos os teleportadores com o mesmo dígito pertencem um ao outro. Quando um átomo atinge um teletransportador, ele imediatamente move o próximo teletransportador no mesmo grupo, onde o próximo é determinado na ordem usual da esquerda para a direita e de cima para baixo. Isso não é necessário, mas ajuda no layout (e, portanto, no golfe). Há também o Xque simplesmente duplica um átomo, enviando uma cópia para a frente e a outra para trás.

A essa altura, você poderá resolver a maior parte da estrutura. O canto superior esquerdo tem a fila de valores ainda a serem processados ​​e libera um de ncada vez. Uma cópia né teletransportada para o fundo porque precisamos dela ao calcular o intervalo, a outra cópia entra no bloco na parte superior que calcula div(essa é de longe a maior seção do código). Uma vez divcalculado, ele é duplicado - uma cópia incrementa um contador no canto superior direito, armazenado em K. A outra cópia é teleportada para o fundo. Se divfoi 1, desviámo-lo para cima imediatamente e usá-lo como gatilho para a próxima iteração, sem enfileirar novos valores. Caso contrário, usamos diven na seção na parte inferior para gerar o novo intervalo (ou seja, um fluxo de átomos com as massas correspondentes que são subsequentemente colocadas na fila) e, em seguida, solte um novo gatilho após o término do intervalo.

Quando a fila estiver vazia, o gatilho será refletido, passando direto pelo Se reaparecendo no canto superior direito, de onde ele libera o contador (o resultado final) A, do qual é então teleportado para a itoavia 8.

Cálculo do número de fissão: o corpo do loop

Então, tudo o que resta são as duas seções para calcular dive gerar o intervalo. Computação divé 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/\/

Você provavelmente já viu o suficiente agora para resolver isso sozinho com alguma paciência. O detalhamento de alto nível é o seguinte: as primeiras 12 colunas geram um fluxo de divisores de 2n. As próximas 10 colunas filtram as que não satisfazem OddQ@# == IntegerQ[n/#]. As próximas 8 colunas filtram as que não satisfazem n/# > (# - 1)/2). Finalmente, empurramos todos os divisores válidos em uma pilha e, quando terminamos, esvaziamos toda a pilha em um reator de fusão (sobrescrevendo todos, exceto o último / maior divisor) e liberamos o resultado, seguido pela eliminação de sua energia (que não era zero de verificar a desigualdade).

Existem muitos caminhos loucos por lá que realmente não fazem nada. Predominantemente, a \/\/\/\/loucura no topo (os 5s também fazem parte) e um caminho ao redor do fundo (que passa pelos 7). Eu tive que adicioná-los para lidar com algumas condições desagradáveis ​​de corrida. A fissão poderia usar um componente de atraso ...

O código que gera o novo intervalo de ne divé este:

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

Primeiro calculamos n/div - (div + 1)/2(ambos os termos, o que resulta no mesmo resultado) e armazenamos para mais tarde. Em seguida, geramos um intervalo de divbaixo para 1e adicionamos o valor armazenado a cada um deles.

Existem dois novos padrões comuns em ambos, que devo mencionar: um é SXou é ZXatingido por baixo (ou versões rotacionadas). Essa é uma boa maneira de duplicar um átomo, se você quiser que uma cópia avance (já que o redirecionamento das saídas de um reator de fusão às vezes pode ser complicado). O Sou Zgira o átomo para dentro Xe, em seguida, gira a cópia espelhada de volta para a direção original de propagação.

O outro padrão é

[K
\A --> output

Se armazenarmos algum valor K, podemos recuperá-lo repetidamente, atingindo Kcom energia negativa do topo. O Aduplica o valor que estamos interessados e envia o que copiar de volta à direita para a pilha para a próxima vez que precisar.

Bem, isso foi um tomo ... mas se você realmente passou por isso, espero que você tenha a ideia de que a Fission

CJam, 42 41 bytes

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

Uma simples passagem pela primeira largura e uma condição de parada do próximo nível vazio.

Como 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

Experimente online aqui

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 salvos graças a @FryAmTheEggman.

Explicação em breve ...

Fato bônus: Toda potência de 2 tem um número de fissão igual a 1. Isso ocorre porque a soma de uma sequência de comprimento par é sempre a soma dos dois números do meio, que é ímpar, multiplicado pela metade do comprimento da sequência, que é inteiro . A soma de uma sequência de comprimento ímpar é o número do meio multiplicado pelo comprimento da sequência, que é ímpar. Portanto, como uma potência de 2 não possui um divisor ímpar, ela pode ser expressa apenas como a soma de si mesma.

Python 2, 111 102 97 bytes

Um pouco legível:

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)

Não é tão legível:

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 os 97 bytes.

bé o nmenos o (a-1)thnúmero triangular. Se b % a == 0, então né a soma dos anúmeros consecutivos a partir de 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}))

Menos golfe:

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

A idéia é testar execuções potenciais de números inteiros consecutivos que somam n. A execução é armazenada diretamente diretamente como um conjunto, Re não através de seus pontos de extremidade.

Verificamos como a soma da execução atual se compara à soma desejada natravés da diferença.

• Se a soma for muito grande, cortamos o menor elemento na execução.
• Se a soma for muito pequena, estenderemos a corrida, aumentando seu máximo em 1.
• Se a soma estiver correta, recuaremos, mapeando fa execução, somando e adicionando 1 para o nó atual. Se a execução for {n}, tentamos todas as somas possíveis não triviais, pare a recursão removendo nprimeiro.

Agradecimentos ao Sp3000 por economizar 3 caracteres.

Python 2, 85

Estou muito orgulhoso dessa resposta, porque já leva dezenas de segundos para n = 9 e 5 a 10 minutos para n = 10. No código de golfe, isso é considerado um atributo desejável de um 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)]

Há também uma versão em curto-circuito que não leva muito tempo e usa a mesma quantidade 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 

Pode ser mais rápido, mas pelo menos excede o limite de recursão padrão quando n ficar um pouco acima de 40.

A idéia é fazer uma busca por força bruta por números ae dtal que a + a+1 + ... + a+d == n, em valores entre 1 e n. O f(n,a+d/n,d%n+1)ramo da recursão percorre os (a, d)pares. No caso de a igualdade ser satisfeita, eu consigo evitar uma map(range(...))ligação cara dividindo-a em apenas dois ramos, independentemente de quanto tempo a sequência seja. Os números a+1através dsão aglomeradas em uma chamada de fajustando o aparâmetro de modo a que uma forma diferente para dividir a sequência não pode ser utilizada.

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]

Como 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

Recebe e imprime a saída em unário.

Você pode colocar cada linha em um único arquivo ou executar o código como está com o -ssinalizador. Por exemplo:

> echo -n 1111111|retina -s fission
11111

Explicação:

• Mantemos uma lista delimitada por vírgula dos números a serem divididos.
• Para cada número, pegamos o menor valor inicial que pode criar uma divisão válida e delimitá-la do resto com um ponto e vírgula.
• Se houver um ponto e vírgula dentro de um número, alteramos para uma vírgula e delimitamos a próxima parte do número com tamanho adequado (comprimento do elemento anterior + 1).
• Repetimos as etapas 2 e 3 até que as mudanças aconteçam.
• Obtemos uma vírgula para cada folha e um ponto-e-vírgula para cada nó interno mais uma vírgula extra, porque começamos com duas vírgulas. Portanto, removemos uma vírgula e as partes dos números 1e convertemos o restante em 1.

Os estados da cadeia de caracteres ao longo do processo com 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

Muito obrigado a @MartinButtner pela ajuda no chat!

CJam (43 bytes)

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

Demonstração online

Tenho certeza de que estou perdendo alguns truques com os loops avançados, mas isso explora perfeitamente a propriedade CJam (que anteriormente me incomodou) que, dentro de um %mapa, os resultados permanecem na pilha e, portanto, podem ser acessados ​​usando $um deslocamento negativo.

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 é o meu primeiro código de golfe, desculpe se cometi algum erro.

Isso usa a ideia de que a "composição" físsil também pode ser vista como uma diferença entre duas sequências de números inteiros ordenados. Por exemplo, pegue a "composição" físsil para o número 13. É 6,7. Mas pode ser visto como a soma dos números inteiros 1 ... 7 menos a soma dos números inteiros 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

Lembre-se da fórmula dos dias letivos de Gauss, some 1 ... n = (n ^ 2 + n) / 2. Então, para encontrar uma composição de números inteiros seqüenciais para um dado n, também poderíamos dizer que estamos procurando por 'pontos finais' peq ao longo do intervalo 1 ... n para que (p ^ 2 + p) / 2 - ( q ^ 2 + q) / 2 = n. No exemplo acima, estaríamos procurando por 'pontos finais' 5 e 7 porque 7 ^ 2 + 7 = 56/2, 5 ^ 2 + 5 = 30/2, 56 / 2-30 / 2 = 28-15 = 13.

Agora, existem várias maneiras possíveis de compor um número físsil, como Martin notou 9 = 2 + 3 + 4, mas também 4 + 5. Mas parece óbvio que a sequência inicial "mais baixa" também será a mais longa, porque leva mais tempo. números pequenos para somar um número grande do que números médios. (Infelizmente não tenho provas)

Portanto, para encontrar a composição de 9, teste todos os 'pares de terminais', p e q, iterando peq separadamente de 0 a 9 e teste se p ^ p + p / 2 - q ^ 2 + q / 2 = 9. Ou, mais simplesmente, multiplique a equação por 2, para evitar os problemas de divisão do arredondamento e manter toda a matemática em números inteiros. Então, estamos procurando peq tais que (p ^ p + p) - (q ^ q + q) = 9 * 2. A primeira correspondência encontrada será os pontos finais da composição do físsil porque, como observado, o grupo mais baixo de números também será o mais longo, e estamos pesquisando de baixo para alto (0 a 9). Saímos do circuito assim que encontramos uma correspondência.

Agora, a função recursiva encontra esses 'pontos finais físseis' peq para o dado n, depois se lembra de cada um dos 'filhos' na árvore de p a q. Para 9, ele encontraria 1 e 4 (20-2 = 18) e, em seguida, chamaria novamente 2, 3 e 4, somando os resultados. Para números como 4, ele simplesmente nunca encontra uma correspondência e, portanto, retorna '1'. Isso pode ser abreviado, mas é como meu terceiro programa go, e eu não sou especialista em recursão.

Obrigado pela leitura.

CJam, 40 35 33 bytes

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

Agradecemos ao @Optimizer por sugerir few, que salvou 2 bytes.

Experimente online no intérprete CJam .

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