Definimos uma sequência do tipo Collatzs com 4 números inteiros positivos:

• n valor inicial
• d > 1 divisor
• m > 1 multiplicador
• i incremento

(Na sequência original de Collatz d = 2 m = 3e i = 1.)

Dado que esses números inteiros sserão criados da seguinte maneira:

• s(0) = n
• se k > 0e s(k-1) mod d = 0entãos(k) = s(k-1) / d
• se k > 0e s(k-1) mod d != 0entãos(k) = s(k-1) * m + i

Um exemplo de sequência com d = 2, m = 3, i = 5e n = 80será s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....

Cada sequência alcançará valores mais altos do que qualquer limite dado (ou seja, a sequência é divergente) ou entrará em um loop infinito se, para alguns te u( t!=u), a s(t) = s(u)igualdade for verdadeira.

Em nosso problema, se o valor de um elemento de sequência for maior que 10^9ou se não houver repetição de elemento antes do 1000enésimo elemento, a sequência será considerada divergente.

A tarefa

Você deve escrever um programa ou função que use os números inteiros positivos d me icomo entradas e saídas de todos os diferentes tipos finais das seqüências (loops infinitos e divergências) que os valores iniciais n = 1, 2, 3, ... 999, 1000possam produzir.

Detalhes da entrada

• A entrada é uma string ou lista (ou equivalente mais próximo na sua língua) que representa (na forma comum) três inteiros positivos d, me inessa ordem. de msão pelo menos 2. Nenhum número é maior que 100.

Detalhes da saída

A especificação de saída é um pouco prolixo. Pode valer a pena conferir os exemplos primeiro.

• Você deve enviar para a saída padrão (ou alternativa mais próxima) ou retornar uma sequência.
• Se uma sequência divergente é possível, a primeira linha deve ser DIVERGENT.
• Uma representação exclusiva do loop de uma sequência é sua rotação, onde o menor número é o último separado por espaços. Por exemplo, se s = 2 1 4 2 1 4 2 1o loop for 4 2 1.
• Em cada linha a seguir, você deve gerar cada loop exclusivo exatamente uma vez precedido pela palavra LOOP. Por exemploLOOP 4 2 1
• Os loops devem estar em ordem crescente em relação ao último elemento.
• A nova linha à direita é opcional.

Exemplos:

As primeiras linhas são as entradas e as seguintes até uma linha em branco são as saídas.

2 3 1
LOOP 4 2 1

2 2 6
LOOP 8 4 2 1
LOOP 12 6 3

3 7 8
DIVERGENT
LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

3 9 1
DIVERGENT

6 9 9
DIVERGENT
LOOP 18 3 36 6 1
LOOP 27 252 42 7 72 12 2
LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4
LOOP 81 738 123 1116 186 31 288 48 8
LOOP 99 900 150 25 234 39 360 60 10
LOOP 126 21 198 33 306 51 468 78 13

10 10 10
LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1

93 91 92
DIVERGENT
LOOP 2185 198927 2139 23
LOOP 4278 46

Implementação de referência em Python 3 na Ideone.

Este é o código-golfe, e a menor entrada ganha.

Python 3, 269 254 252 246 bytes

d,m,i=eval(input())
S=set()
for n in range(1,1001):
 T=X=()
 while len(T)**3<1e9>=n:
  T=(n,)+T;n=[n//d,n*m+i][n%d>0]
  if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M]
 S|={X}
for x in sorted(S):print(x and"LOOP"or"DIVERGENT",*x[::-1])

(Agora 10 vezes mais lento para economizar alguns bytes. Código de golfe típico.)

Insira uma lista via STDIN (por exemplo [2, 3, 1]). Estou pensando que deve haver uma maneira melhor de padronizar os ciclos ...

A abordagem é bastante direta - teste todos os 1000 números e obtenha apenas as saídas exclusivas. No entanto, existem dois pequenos truques lá:

• Os loops são representados por tuplas não vazias, mas o mais importante é que a divergência é representada por uma tupla vazia . Isso é bom porque:

  • Ele não quebra sortede até aparece antes de todas as tuplas de loop
  • Permite selecionar uma string via x and"LOOP"or"DIVERGENT"
  • *()[::-1] não afeta print
• Os loops são construídos para trás para transformar "classificação ascendente pelo último elemento" em "classificação ascendente pelo primeiro elemento", o que elimina a necessidade de passar uma lambda para sorted.

Submissão anterior, 252 bytes

d,m,i=eval(input())
def f(n,T=()):
 x=[n//d,n*m+i][n%d>0];I=T.index
 if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M]
 return()if(T[1000:]or x>1e9)else f(x,(x,)+T)
for x in sorted(set(map(f,range(1,1001)))):print(x and"LOOP"or"DIVERGENT",*x[::-1])

Este é muito mais rápido.