Collatz Attack!

Esse desafio é baseado em algumas novas descobertas relacionadas à conjectura de Collatz e projetado de alguma forma no espírito de um projeto colaborativo de polímatas . A solução da conjectura completa é considerada extremamente difícil ou impossível pelos especialistas em matemática / teoria dos números, mas essa tarefa mais simples é bastante viável e há muitos exemplos de código de amostra. Na melhor das hipóteses, novas idéias teóricas podem ser obtidas para o problema com base nas entradas / engenhosidade / criatividade dos concorrentes.

A nova descoberta é a seguinte: Imagine uma série contígua de números inteiros [ n1 ... n2 ] digamos m total. Atribua esses números inteiros a uma estrutura de lista. Agora, uma versão generalizada da conjectura de Collatz pode prosseguir da seguinte maneira. Itere um dos m (ou menos) números inteiros na lista a seguir com base em alguns critérios / algoritmo de seleção. Remova esse número inteiro da lista se atingir 1. Claramente, a conjectura de Collatz é equivalente a determinar se esse processo sempre é bem-sucedido em todas as opções de n1, n2 .

Aqui está a torção, uma restrição adicional. Em cada etapa, adicione m atual itera na lista juntos. Em seguida, considere a função f (i) onde i é o número da iteração ef (i) é a soma das iterações atuais na lista. Procure f (i) com uma propriedade "agradável" específica.

O conceito geral / geral é melhor / mais bem documentado aqui (com muitos exemplos em ruby). A conclusão é que existem estratégias / heurísticas / algoritmos bastante simples que levam a uma "diminuição praticamente monotônica" de f (i) e muitos exemplos são dados nessa página. Aqui está um exemplo da saída gráfica (plotada via gnuplot):

Então, aqui está o desafio: use variações nos exemplos existentes ou idéias inteiramente novas para criar um algoritmo de seleção que resulte em f (i) "o mais próximo possível da redução monotônica possível". Os participantes devem incluir um gráfico de f (i) em sua inscrição. Os eleitores podem votar com base nesse gráfico e nas idéias algorítmicas do código.

O concurso será baseado apenas nos parâmetros n1 = 200 / n2 = 400 ! (o mesmo na página de exemplo.) Mas, esperançosamente, os participantes explorarão outras regiões e também tentarão generalizar seus algoritmos.

Observe que uma tática que pode ser muito útil aqui são algoritmos do tipo descida de gradiente ou algoritmos genéticos.

Pode discutir isso ainda mais no chat para os participantes interessados.

Para alguns árbitros, outro desafio de Collatz no codegolf: Collatz Conjecture (por Doorknob )

Eu escrevi algum código no Python 2 para executar algoritmos para este desafio:

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) pega a lista de valores e retorna uma lista de bools para saber se cada um deve ser alterado.

Isso inclui a primeira coisa que tentei, como a linha logo após o comentário, que estava iterando todos os valores da lista. Eu tenho esse:

Não parece nem um pouco monotônico, então tentei iterar apenas os valores que diminuiriam a soma, se houver, iterando os que aumentariam menos:

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

Infelizmente, isso não terminar (pelo menos para n1=200, n2=400). Tentei acompanhar os valores que já havia visto 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)]

Isso também não termina.

Ainda não tentei mais nada, mas se tiver novas idéias, as postarei aqui.

Python 3

Minha idéia principal era adicionar cada sequência de Collatz dos números à f(i)função individualmente, de forma a minimizar o aumento total de f(i). A função resultante não está diminuindo estritamente, mas possui uma estrutura agradável (na minha opinião :)). O segundo gráfico foi criado com um intervalo maior para f(i)uma função de punição ligeiramente diferente. Código no Gist.

Ao usar a regra (3 * n + 1) / 2 em vez da regra 3 * n + 1, o algoritmo produz um método completamente monotônico f(i)! Tenho certeza de que essa modificação pode tornar os gráficos do vzn muito mais suaves também. O segundo gráfico foi criado com um intervalo maior para f(i). Código no Gist.

Ambos os resultados são semelhantes para [n,2*n]intervalos maiores .