Analizando secuencias similares a Collatz

12

Definimos una secuencia tipo Collatzs con 4 enteros positivos:

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

(En la secuencia original de Collatz d = 2 m = 3y i = 1.)

Dados estos enteros sse crearán de la siguiente manera:

  • s(0) = n
  • si k > 0y s(k-1) mod d = 0luegos(k) = s(k-1) / d
  • si k > 0y s(k-1) mod d != 0luegos(k) = s(k-1) * m + i

Una secuencia de ejemplo con d = 2, m = 3, i = 5y n = 80será s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....

Cada secuencia alcanzará valores más altos que cualquier límite dado (es decir, la secuencia es divergente) o entrará en un bucle infinito si para algunos ty u( t!=u) la s(t) = s(u)igualdad será verdadera.

En nuestro problema, si el valor de un elemento de secuencia es mayor 10^9o no hay repetición de elementos antes del 1000elemento th, la secuencia se considera divergente.

La tarea

Debería escribir un programa o función que tome los enteros positivos d my icomo entradas y salidas todos los diferentes tipos finales de las secuencias (bucles infinitos y divergencia) que n = 1, 2, 3, ... 999, 1000pueden producir los valores iniciales .

Detalles de entrada

  • La entrada es una cadena o una lista (o equivalente más cercano en su idioma) que representa (en la forma común) tres números enteros positivos d, my ien ese orden. dy mson al menos 2. Ninguno de los dos números es mayor que 100.

Detalles de salida

La especificación de salida es un poco prolija. Podría valer la pena ver los ejemplos primero.

  • Debe enviar a la salida estándar (o la alternativa más cercana) o devolver una cadena.
  • Si es posible una secuencia divergente, la primera línea debería serlo DIVERGENT.
  • Una representación única del ciclo de una secuencia es su rotación, donde el número más pequeño es el último separado por espacios. Por ejemplo, si s = 2 1 4 2 1 4 2 1el bucle es 4 2 1.
  • En cada línea siguiente, debe generar cada ciclo único exactamente una vez precedido por la palabra LOOP. P.ejLOOP 4 2 1
  • Los bucles deben estar en orden ascendente con respecto a su último elemento.
  • La nueva línea final es opcional.

Ejemplos:

Las primeras líneas son las entradas y las siguientes hasta una línea en blanco son las salidas.

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

Implementación de referencia en Python 3 en Ideone.

Este es el código de golf, por lo que gana la entrada más corta.

randomra
fuente

Respuestas:

5

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

(Ahora 10 veces más lento para guardar algunos bytes. Código de golf típico).

Ingrese una lista a través de STDIN (por ejemplo [2, 3, 1]). Estoy pensando que debe haber una mejor manera de estandarizar los ciclos ...

El enfoque es bastante sencillo: pruebe los 1000 números y tome solo las salidas únicas. Sin embargo, hay dos pequeños trucos allí:

  • Los bucles están representados por tuplas no vacías, pero lo más importante es que la divergencia está representada por una tupla vacía . Esto es bueno porque:

    • No se rompe sortede incluso aparecerá antes de todas las tuplas de bucle
    • Nos permite seleccionar una cadena a través de x and"LOOP"or"DIVERGENT"
    • *()[::-1] no afecta print
  • Los bucles se construyen hacia atrás para convertir "ordenar ascendente por último elemento" en "ordenar ascendente por primer elemento", lo que elimina la necesidad de pasar una lambda sorted.

Presentación previa, 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 es mucho más rápido.

Sp3000
fuente