Collatz Attack!

Este desafío se basa en algunos hallazgos nuevos relacionados con la conjetura de Collatz y está diseñado de alguna manera en el espíritu de un proyecto colaborativo de polymath . Los expertos en teoría matemática / numérica consideran extremadamente difícil o quizás imposible resolver la conjetura completa, pero esta tarea más simple es bastante factible y hay muchos ejemplos de código de muestra. En el mejor de los casos, se pueden obtener nuevas ideas teóricas sobre el problema basadas en las entradas de los concursantes / ingenio / creatividad.

El nuevo hallazgo es el siguiente: Imagine una serie contigua de enteros [ n1 ... n2 ] digamos m total. Asigne estos enteros a una estructura de lista. Ahora una versión generalizada de la conjetura de Collatz puede proceder de la siguiente manera. Itere uno de los enteros m (o menos) en la siguiente lista según algunos criterios / algoritmos de selección. Elimine ese número entero de la lista si llega a 1. Claramente, la conjetura de Collatz es equivalente a determinar si este proceso siempre tiene éxito para todas las opciones de n1, n2 .

Aquí está el giro, una restricción adicional. En cada paso, agregue las iteraciones m actuales en la lista juntas. Luego considere la función f (i) donde i es el número de iteración yf (i) es la suma de iteraciones actuales en la lista. Busque f (i) con una propiedad "bonita" particular.

Todo el concepto general está mejor documentado aquí (con muchos ejemplos en ruby). El hallazgo es que existen estrategias / heurísticas / algoritmos bastante simples que conducen a una " f (i) " decreciente de forma aproximadamente monotónica y existen muchos ejemplos en esa página. Aquí hay un ejemplo de la salida gráfica (trazada a través de gnuplot):

Así que aquí está el desafío: usar variaciones en los ejemplos existentes o ideas completamente nuevas para construir un algoritmo de selección que resulte en una f (i) "lo más cerca posible de una disminución monotónica". Los participantes deben incluir un gráfico de f (i) en su presentación. Los votantes pueden votar según ese gráfico y las ideas algorítmicas en el código.

¡El concurso se basará en n1 = 200 / n2 = 400 parámetros solamente! (lo mismo en la página de muestra). Pero con suerte los concursantes explorarán otras regiones y también intentarán generalizar sus algoritmos.

Tenga en cuenta que una táctica que podría ser muy útil aquí son los algoritmos de tipo de descenso de gradiente o algoritmos genéticos.

Puede discutir todo esto en el chat para los participantes interesados.

Para algunos árbitros, otro desafío codegolf Collatz: Conjetura Collatz (por Doorknob )

Escribí un código en Python 2 para ejecutar algoritmos para este desafío:

import matplotlib.pyplot as plt

def iterate(n):
    return n*3+1 if n%2 else n/2
def g(a):
    ##CODE GOES HERE
    return [True]*len(a)
n1=input()
n2=input()
a=range(n1,n2+1)
x=[]
y=[]
i=0
while any(j>1 for j in a):
    y.append(sum(a))
    x.append(i)
    i+=1
    b=g(a)
    for j in range(len(a)):
        if b[j]:
            a[j]=iterate(a[j])
plt.plot(x,y)
plt.show()

g(x) toma la lista de valores y devuelve una lista de bools para determinar si cada uno debe cambiarse.

Eso incluye lo primero que probé, como la línea justo después del comentario, que iteraba todos los valores de la lista. Tengo esto:

No parece cercano a monótono, así que intenté iterar solo valores que disminuirían la suma, si hay alguna, iterando los que lo aumentarían menos de lo contrario:

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m=[n[i]-a[i] for i in range(l)]
return [m[i]==min(m) for i in range(l)]

Desafortunadamente, eso no termina (al menos para n1=200, n2=400). Intenté hacer un seguimiento de los valores que había visto antes inicializando c=set():

l=len(a)
n=[iterate(i) for i in a]
less=[n[i]<a[i] for i in range(l)]
if any(less):
    return less
m={i:n[i]-a[i] for i in range(l)}
r=[i for i in m if m[i]==min(m.values())]
while all([a[i] in c for i in r]) and m != {}:
    m={i:m[i] for i in m if a[i] not in c}
    r+=[i for i in m.keys() if m[i]==min(m.values())]
for i in r:
    c.add(a[i])
return [i in r for i in range(l)]

Sin embargo, eso tampoco termina.

Todavía no he probado nada más, pero si tengo nuevas ideas, las publicaré aquí.

Python 3

Mi idea principal era agregar cada secuencia de Collatz de números a la f(i)función individualmente de manera que minimice el aumento total de f(i). La función resultante no está disminuyendo estrictamente, pero tiene una estructura agradable (en mi opinión :)). El segundo gráfico se creó con un intervalo más largo f(i)y una función de castigo ligeramente diferente. Código sobre Gist.

Cuando se usa la regla (3 * n + 1) / 2 en lugar de la 3 * n + 1, ¡el algoritmo produce un monotónico completamente f(i)! Estoy seguro de que esta modificación también podría hacer que los gráficos de vzn sean mucho más suaves. El segundo gráfico se creó con un intervalo más largo para f(i). Código sobre Gist.

Ambos resultados son similares para [n,2*n]rangos más grandes .