Happy numbers

In the Doctor Who episode "42" (the seventh of the third modern series), the tenth Doctor explains that a (natural positive) number that reduces to one when you sum up the square of its digits and continue iterating it until it yields one is said to be happy. If this description doesn't look so descriptive to you, there is a page about happy numbers on wikipedia that looks interesting.

We can check if a number is happy with a C++ function like this one:
bool isHappy(unsigned value)
{
  std::set<unsigned> numbers; // 1
  numbers.insert(1); // 2
  while(numbers.find(value) == numbers.end()) // 3
  {
    numbers.insert(value); // 4
    int next = 0;
    while(value > 0)
    {
      int digit = value % 10;
      next += std::pow(digit, 2); // 5
      value /= 10;
    }
    value = next;
  }

  return value == 1; // 6
}
1. A sad number would enter in a hopeless infinite loop. To detect it, we should keep memory of the states it has already passed, so that we can check them.
2. We could stop transforming the input number when we get a value that we have already seen (sad), of when we get 1 (happy).
3. If the current value is not in the buffering set, we iterate once again.
4. Add the current value to the "already seen" set, and calculate the next state.
5. Each digit is squared and added.
6. If value has reached 1, we have a happy number.

No comments:

Post a Comment