Como a função para saber se um número é ou não feliz é uma função pura, podemos usar nela memoização.
Uma maneira muito fácil de fazer memoização é com recursão. Note que a própria definição de feliz pode ser interpretada de maneira recursiva:
Se o número em questão for 1, ele é feliz.
Se o número não for 1, então ele é feliz se a soma do quadrado dos seus dígitos for feliz.
No caso, se a recursão não convergir, então isso implica que o número é infeliz (coitadinho =/ ).
Agora, será que, diferentemente da conjectura de Collatz, eu consigo demonstrar que a sequência do somatório dos dígitos de um número converge para laços finitos? Sim, conseguimos. (A ideia de identificar os laços eu pesquei da resposta do @Bacco)
Pegue um número grande. Nós sabemos que ele tem n
dígitos. Qualquer número com n
dígitos tem como soma máxima do quadrado dos seus dígitos como n*9^2
. Basta então verificar que essa soma vai ser menor do que qualquer número de n
dígitos. O menor número de n
dígitos é 10^(n-1)
. Então, se para a maior soma de quadrados de dígitos com n
dígitos ela for menor do que o menor número de n
dígitos, então temos que 10^(n-1)
será um limite superior a essa soma, portanto não haverá laços com elemetos maiores que 10^(n-1)
. Isso também limitado o tamanho máximo do laço para 10^(n-1)
.
Peguemos com n = 4
. O menor número é 1000
. A maior soma é 4*81 = 324
. Isso significa que qualquer soma feita com 4 dígitos ou menos será sempre limitada a 324. Isso implica que não haverá laços com mais do que 1000 elementos, com todos os elementos limitados a no máximo o número 1000.
Ok, o limite na verdade é bem menor, mas o limite relaxado já é o suficiente para a demonstração
Pegando essa ideia, podemos fazer a função feliz
que faz uma verificação recursiva pela felicidade dos números. Para isso, uso um "caminho de migalhas" que, sempre que toco nele, detecto o laço e portanto a infelicidade do número. Também aproveito conhecimento prévio da felicidade alheia e se a soma dos quadrados dos dígitos já for conhecidamente feliz
ou infeliz
e marco meu caminho de volta com essa medida de felicidade.
No caso, minha memória é posicional e cada posição consiste de um estado. Existem 4 possíveis estados:
undefined
: memória nova, não tenho nada memoizado para essa posição
'H'
: feliz =)
'M'
: triste =/
'S'
: minha migalha, não sei ainda
Note que para a memoização funcionar corretamente, esse caminho de migalhas impede a execução paralela de descobrimento de novas memórias. Se com essa memoização alguém colocar esse algoritmo para servir duas perguntas sobre a felicidade dos números em paralelo, o resultado não será garantido. E a partir desse ponto a memória deve ser limpa para começar de novo.
Um detalhe importante é que a memoização aqui começa com o caso base já na memória: eu já começo lembrando que 1 ==> 'H'
.
Segue a versão mais legível, com trace para verificar a memória e apenas alguns poucos números testados:
function soma_quad_digits(numero) {
let soma_quad = 0;
while (numero > 0) {
let dig = numero % 10;
numero = Math.floor(numero/10);
soma_quad += dig*dig;
}
return soma_quad;
}
function felicidade_memoizada(numero, memoria) {
if (memoria[numero] === undefined) {
console.log("indo atrás da felicidade de " + numero + " (soma do quadrado dos dígitos: " + soma_quad_digits(numero) + ")");
// memória aqui é indefinida! oba \o/
memoria[numero] = 'S'; // S de SEARCHING, usado pra marcar loops
let nova_memoria = felicidade_memoizada(soma_quad_digits(numero), memoria); // busca a nova memória recursivamente
memoria[numero] = nova_memoria; // fazendo a memoização
console.log("memorizando que " + numero + " é " + nova_memoria);
return nova_memoria;
} else if (memoria[numero] == 'H') { // H de HAPPY
return 'H'; // sim, achou memória feliz
} else if (memoria[numero] == 'M') { // M de MAD
return 'M'; // caí num caso conhecido de infelicidade
} else if (memoria[numero] == 'S') { // oh, oh... loop
// nesse caso, na recursão que preencheu como SEARCHING originalmente vai marcar esse cara como MAD...
return 'M';
}
}
let memoria = [];
memoria[1] = 'H'; // definição
let feliz = (n) => felicidade_memoizada(n, memoria) == 'H';
console.log(feliz(2));
console.log(feliz(7));
console.log(feliz(19));
console.log(feliz(23));
console.log(feliz(50));
Agora, poderíamos ter de modo mais elegante a criação da função feliz
. Não gostei muito de deixar a variável memoria
no escopo global. Podemos usar uma função autoinvocada que retorna a função feliz
. Essa versão eu já sacrifico logo todos os comentários e legibilidade:
let feliz = (function() {
function soma_quad_digits(numero) {
let soma_quad = 0;
for (let dig = numero % 10; numero > 0; numero = (numero/10)|0, dig = numero%10) {
soma_quad += dig*dig;
}
return soma_quad;
}
function felicidade_memoizada(numero, memoria) {
if (numero > 10000) {
return felicidade_memoizada(soma_quad_digits(numero), memoria);
}
if (memoria[numero] === undefined) {
memoria[numero] = 'S';
return memoria[numero] = felicidade_memoizada(soma_quad_digits(numero), memoria);
} else if (memoria[numero] == 'H') {
return 'H';
} else {
return 'M';
}
}
let memoria = [];
memoria[1] = 'H';
return (n) => felicidade_memoizada(n, memoria) == 'H';
})();
for (let i = 0; i <= 50; i++) {
if (feliz(i)) {
console.log(i);
}
}
Mas, sinceramente, por que nos limitar a apenas 50? Vamos até o limite superior relaxado do laço, que seria 1000?
let feliz = (function() {
function soma_quad_digits(numero) {
let soma_quad = 0;
for (let dig = numero % 10; numero > 0; numero = (numero/10)|0, dig = numero%10) {
soma_quad += dig*dig;
}
return soma_quad;
}
function felicidade_memoizada(numero, memoria) {
if (numero > 10000) {
return felicidade_memoizada(soma_quad_digits(numero), memoria);
}
if (memoria[numero] === undefined) {
memoria[numero] = 'S';
return memoria[numero] = felicidade_memoizada(soma_quad_digits(numero), memoria);
} else if (memoria[numero] == 'H') {
return 'H';
} else {
return 'M';
}
}
let memoria = [];
memoria[1] = 'H';
return (n) => felicidade_memoizada(n, memoria) == 'H';
})();
for (let i = 0; i <= 1000; i++) {
if (feliz(i)) {
document.write(i + " "); // tentei ficar só no log, mas ficou grande demais...
}
}