quinta-feira, 16 de agosto de 2018
Indecidivel problema generalizado de Collatz
Lendo sobre matemática na coluna do Sr. Marcelo Viana encontrei um quebra cabeça que ainda está em aberto:
https://www1.folha.uol.com.br/colunas/marceloviana/2018/08/problemas-matematicos-o-facil-pode-ser-muito-dificil.shtml
Outra fonte:
http://people.cs.uchicago.edu/~simon/RES/collatz.pdf
1)
Brincando e observando o problema, pude perceber que para descobrir se NÃO é válido para todos os números, precisamos saber se existe algum número que retorna a ele mesmo após várias interações repetidas de:
multiplicar por 3 e somar 1
dividir por 2
2)
Supondo que um número pudesse crescer indefinidamente e por ultimo ter uma redução dividindo por 2, que consideraremos como estado final, encontrei uma pirâmide de soluções baseadas na seguinte formula:
sendo k a posição da construção, variando de zero a infinito de um em um:
2k+1 → (gera) 3k+2
2k+1 → 3k+2
Assim, se temos um k=3 significa que para o número 2*3+1, que é 7, pode-se obter, pela formulação de Collatz o numero 11:
Assim, a partir de 7, que é impar, temos (3*7+1)/2 que é 11
Partindo dessa formula, percebi que é possível construir uma pirâmide com a seguinte estrutura:
0
1, 2
3, 5, 8
7, 11, 17, 26
15, 23, 35, 53, 80
31, 47, 71, 107, 161, 242
.
.
.
O primeiro numero de cada linha é obtido a partir das potencias de 2 subtraídas de um: 1, 2, 4, 8, 16...
Os números seguintes a estes primeiros é obtido a partir da soma dos primeiros pelo seu imediatamente acima somado de um. Por exemplo, para 35 gerar 53, pega-se 35 + (17+1) = 53
Aparentemente, a partir dos números já criados na pirâmide, é possível construir os números mais a frente pela formula
2k+1 → 3k+2
Assim, se o k = 8, que aparece no final da linha 3, temos que:
(2*8+1 = 17) → (3*8+2 = 26)
Desconsiderei todos os outros números que não aparecem, pois eles são redutíveis a qualquer outro número que possa aparecer na pirâmide. Seja pela divisão de 2 ou seja pela multiplicação de 3 soma um.
<html>
<script>
function getVal()
{
var p=0;
velho = new Array();
velho.push(0);
while(p<16)
{
novo = new Array();
document.write(" k = " + p + " ... " );
novo.push(Math.pow(2,p)-1 );
document.write(" " + novo[0] );
for(var i=0; i<p; i++)
{
novo.push(novo[i] + velho[i] +1 );
document.write(" - " + novo[i+1] );
}
velho = novo;
document.write("</br>");
p++;
}
}
getVal();
</script>
</html>
Nenhum comentário:
Postar um comentário