How to find "Happy Numbers" within an interval?

Question

I’m making an application where I need to find Happy Numbers within a certain range, in the case of 0 to 50, and I found this in Wikipedia:

The happy numbers are defined by the following procedure. Starting with any positive integer, the number is replaced by the sum of the squares of their digits, and repeat the process until the number is 1 or until it enters an infinite cycle which does not include one or the sum of the square squares of the square of an initial positive number. The numbers at the end of the end with 1, are known as happy numbers, but those who do not end with a 1 are numbers called unfortunate.

And there’s an example of how to know if the number is Happy:

7 is a happy number:

If n is not happy, the sum of the squares will never give 1, will be generated infinite terms.

How would an algorithm be to find these numbers in the above range? I have a lot of difficulty working with Javascript powers.

The happy numbers between 0 and 50 would be:

1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49

I needed a code to get to that result.

Answer 1

Another way to do it is by breaking the string and using Math.pow in each of the "pieces", for example:

function beHappy(value) {

  let repeat = [];

  /**
   * Verifica se o valor é maior que 1 e se
   * o valor não é repetido, isso irá evitar
   * um loop infinito
   */
  while (value > 1 && !~repeat.indexOf(value)) {
    let result = 0;

    /**
     * Adiciona o valor para na variável
     * repeat para evitar o loop infinito
     */
    repeat.push(value);

    /* Quebra a string em pedaços */
    for (let n of value.toString().split("")) {

      /**
       * Utiliza o Math.pow para calcular a base
       * elevado ao expoente. É o mesmo que n * n
       */
      result += Math.pow(n, 2)
    }

    value = result;
  }

  return value == 1;
}

for (let i = 0; i <= 50; i++) {
  if (beHappy(i)) {
    console.log(i);
  }
}

Answer 2

Adapted from Rosetta Code for Sopt:

https://rosettacode.org/wiki/Happy_numbers#Javascript

Licence to reproduce the document:

https://www.gnu.org/licenses/fdl-1.2.html

I changed the track to 0-50 and put the proper comments in the code.

Basically is done what was requested in the statement, the only detail all that matters is the criteria for knowing when to stop:

As the sequence can be very large, the only alternatives that we have to find the 1, concluding by the "happiness" of the number, or find a repeated result, which would characterize an "unfortunate".

function happy(number) {
    var m, digit ;

    // cycle é onde vamos acumular os resultados de cada passo
    var cycle = [] ;
 
    // enquanto não encontramos o 1, nem uma repetição, vamos insistindo
    while(number != 1 && cycle[number] !== true) {
        // armazenamos o número analisado no array, para detectar repetição
        cycle[number] = true ;
        m = 0 ;
        while (number > 0) { 

            // o % extrai os dígitos 1 a 1
            digit = number % 10 ;

            // e o valor do quadrado é acumulado em m
            m += digit * digit ;
            number = (number  - digit) / 10 ;
        }
        number = m ;
    }
    return (number == 1) ;
}
 
var number = 0 ;
while(number < 50) { 
    if (happy(number)) document.write(number + " ");
    number++;
}

Possible optimization: store the previous results by marking them with "happy" or "unhappy", because if in the search loop some "happy" appears, the origin number is "happy" too (the opposite is also true, if any "unfortunate" is found in the search, the origin number is also "unfortunate")

Recommended reading, from Online Encyclopedia of Integer Sequences:

http://oeis.org/A007770

Answer 3

As the function to know whether a number is happy or not is a pure function, we can use on her memoisation.

A very easy way to do memoization is with recursion. Note that the very definition of happy can be interpreted recursively:

If the number in question is 1, he’s happy.

If the number is not 1, then he is happy if the sum of the square of his digits is happy.

In this case, if the recursion does not converge, then it implies that the number is unhappy (poor thing =/ ).

Now, is that, unlike collatz conjecture, I can demonstrate that the sequence of the sum of digits of a number converges to finite loops? Yes, we did. (The idea of identifying the ties I fished from reply by @Bacco)

Take a big number. We know he has n digits. Any number with n digits have as the maximum sum of the square of their digits as n*9^2. Just then verify that this sum will be less than any number of n digits. The smallest number of n digits is 10^(n-1). So if for the largest sum of square digits with n digits it is smaller than the smallest number of n digits, so we have to 10^(n-1) will be an upper bound to that sum, so there will be no ties with larger elemets than 10^(n-1). That also limited the maximum loop size for 10^(n-1).

Let’s take with n = 4. The smallest number is 1000. The largest sum is 4*81 = 324. This means that any sum made with 4 digits or less will always be limited to 324. This implies that there will be no ties with more than 1000 elements, with all elements limited to at most the number 1000.

Okay, the limit is actually much lower, but the relaxed limit is enough for the demonstration

Taking this idea, we can do the function feliz that makes a recursive check for the happiness of the numbers. For this, I use a "crumb path" that whenever I touch it, I detect the tie and therefore the unhappiness of the number. I also take advantage of previous knowledge of the happiness of others and if the sum of the squares of the digits is already known feliz or infeliz and mark my way back with that measure of happiness.

In this case, my memory is positional and each position consists of a state. There are 4 possible states:

• undefined: new memory, I have nothing memoized for that position
• 'H': happy =)
• 'M': sad =/
• 'S': my crumb, I don’t know yet

Note that for memoization to work properly, this crumb path prevents parallel execution of discovery of new memories. If someone puts this algorithm to serve two questions about the happiness of numbers in parallel, the result will not be guaranteed. And from that point the memory must be wiped to start again.

An important detail is that the memoization here begins with the case based already on memory: I already start by remembering that 1 ==> 'H'.

Follows the most readable version, with trace to check the memory and only few numbers tested:

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

Now, we could have in a more elegant way the creation of the function feliz. I didn’t really like leaving the variable memoria in the global scope. We can use a function self-appointed that returns the function feliz. This version I already sacrifice all comments and readability:

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);
  }
}

But honestly, why limit ourselves to just 50? Let’s go to the upper limit relaxed of the loop, which would be 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...
  }
}