Happy number

From Wikipedia, the free encyclopedia

Categories: Base-dependent integer sequences | Recreational mathematics

A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers. A computer search up to 10²⁰ suggests that about 12% of numbers are happy, though no proof is known (Guy 2004:§E34).

1 Overview
2 Sequence behavior
3 Happy primes
4 Happy numbers in other bases
5 Origin
6 References

Overview

More formally, given a number Failed to parse (Missing texvc executable; please see math/README to configure.): n=n_0 , define a sequence Failed to parse (Missing texvc executable; please see math/README to configure.): n_1 , Failed to parse (Missing texvc executable; please see math/README to configure.): n_2 , ... where Failed to parse (Missing texvc executable; please see math/README to configure.): n_{i+1}

is the sum of the squares of the digits of Failed to parse (Missing texvc executable; please see math/README to configure.): n_i

. Then Failed to parse (Missing texvc executable; please see math/README to configure.): n

is happy if and only if this sequence goes to 1.

If a number is happy, then all members of its sequence are happy; if a number is unhappy, all members of its sequence are unhappy.

For example, 7 is happy, as the associated sequence is:

7² = 49

4² + 9² = 97

9² + 7² = 130

1² + 3² + 0² = 10

1² + 0² = 1.

The first few happy numbers are

1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, 103, 109, 129, 130, 133, 139, 167, 176, 188, 190, 192, 193, 203, 208, 219, 226, 230, 236, 239, 262, 263, 280, 291, 293, 301, 302, 310, 313, 319, 320, 326, 329, 331, 338, 356, 362, 365, 367, 368, 376, 379, 383, 386, 391, 392, 397, 404, 409, 440, 446, 464, 469, 478, 487, 490, 496. (sequence A007770 in OEIS).

Sequence behavior

If Failed to parse (Missing texvc executable; please see math/README to configure.): n

is not happy, then its sequence does not go to 1.  What happens instead is that it ends up in the cycle

4, 16, 37, 58, 89, 145, 42, 20, 4, ...

To see this fact, first note that if Failed to parse (Missing texvc executable; please see math/README to configure.): n

has Failed to parse (Missing texvc executable; please see math/README to configure.): m
digits, then the sum of the squares of its digits is at most Failed to parse (Missing texvc executable; please see math/README to configure.): 81m

. For Failed to parse (Missing texvc executable; please see math/README to configure.): m=4

and above,

Failed to parse (Missing texvc executable; please see math/README to configure.): n\geq10^{m-1}>81m

so any number over 1000 gets smaller under this process. Once we are under 1000, the number for which the sum of squares of digits is largest is 999, and the result is 3 times 81, that is, 243.

In the range 100 to 243, the number 199 produces the largest next value, of 163.
In the range 100 to 163, the number 159 produces the largest next value, of 107.
In the range 100 to 107, the number 107 produces the largest next value, of 50.

Considering more precisely the intervals [244,999], [164,243], [108,163] and [100,107], we see that every number above 99 gets strictly smaller under this process. Thus, no matter what number we start with, we eventually drop below 100. Exhaustive search then shows that every number in the interval [1,99] is either happy or goes to the above cycle.

Happy primes

A happy prime is a happy number that is prime. The first few happy primes are

7, 13, 19, 23, 31, 79, 97, 103, 109, 139, 167, 193, 239, 263, 293, 313, 331, 367, 379, 383, 397, 409, 487 (sequence A035497 in OEIS)

Note that all primes of the form Failed to parse (Missing texvc executable; please see math/README to configure.): 10^n + 3

and Failed to parse (Missing texvc executable; please see math/README to configure.): 10^n + 9
are happy.  The palindromic prime 10¹⁵⁰⁰⁰⁶ + 7426247×10⁷⁵⁰⁰⁰ + 1 is also a happy prime with 150007 digits because the many 0's do not contribute to the sum of squared digits, and Failed to parse (Missing texvc executable; please see math/README to configure.): 1^2 + 7^2+4^2+2^2+6^2+2^2+4^2+7^2 + 1^2 = 176

, which is a happy number. Paul Jobling discovered the prime in 2005.[1].

As of June 2007, the largest known happy prime and the twelfth largest known prime is 4847 × 2^3321063 + 1. The decimal expansion has 999744 digits: 1844857508...(999724 digits omitted)...2886501377. Richard Hassler and Seventeen or Bust discovered the prime in 2005.[2] [3] Jens K. Andersen identified it as the largest known happy prime in June 2007.

In the Doctor Who episode "42", a sequence of happy primes (313, 331, 367, 379) is used as a code for unlocking a sealed door on a spaceship falling into a star.

Happy numbers in other bases

The definition of happy numbers depends on the decimal (i.e., base 10) representation of the numbers. The definition can be extended to other bases.

To represent numbers in other bases, we may use a subscript to the right to indicate the base. For instance, Failed to parse (Missing texvc executable; please see math/README to configure.): 100_2

represents the number 4, and

Failed to parse (Missing texvc executable; please see math/README to configure.): 123_5 = 1 \cdot 5^2 + 2 \cdot 5 + 3 =38.

Then, it is easy to see that there are happy numbers in every base. For instance, the numbers

Failed to parse (Missing texvc executable; please see math/README to configure.): 1_b,10_b,100_b,1000_b,...

are all happy, for any base Failed to parse (Missing texvc executable; please see math/README to configure.): b .

By a similar argument to the one above for decimal happy numbers, we can see that unhappy numbers in base Failed to parse (Missing texvc executable; please see math/README to configure.): b

lead to cycles of numbers less than Failed to parse (Missing texvc executable; please see math/README to configure.): 1000_b

. We can use the fact that if Failed to parse (Missing texvc executable; please see math/README to configure.): n < 1000_b , then the sum of the squares of the base-Failed to parse (Missing texvc executable; please see math/README to configure.): b

digits of Failed to parse (Missing texvc executable; please see math/README to configure.): n
is less than or equal to

Failed to parse (Missing texvc executable; please see math/README to configure.): 3(b-1)^2

which can be shown to be less than Failed to parse (Missing texvc executable; please see math/README to configure.): b^3 . This shows that once the sequence reaches a number less than Failed to parse (Missing texvc executable; please see math/README to configure.): 1000_b , it stays below Failed to parse (Missing texvc executable; please see math/README to configure.): 1000_b , and hence must cycle or reach 1.

In base 2, all numbers are happy. All binary numbers larger than 1000₂ decay into a value equal to or less than 1000₂, and all such values are happy: The following four sequences contain all numbers less than Failed to parse (Missing texvc executable; please see math/README to configure.): 1000_2

Failed to parse (Missing texvc executable; please see math/README to configure.): 111_2 \rightarrow 11_2 \rightarrow 10_2 \rightarrow 1

Failed to parse (Missing texvc executable; please see math/README to configure.): 110_2 \rightarrow 10_2 \rightarrow 1

Failed to parse (Missing texvc executable; please see math/README to configure.): 101_2 \rightarrow 10_2 \rightarrow 1

Failed to parse (Missing texvc executable; please see math/README to configure.): 100_2 \rightarrow 1

Since all sequences end in 1, we conclude that all numbers are happy in base 2. This makes base 2 a happy base.

The only known happy bases are 2 and 4, yet more could exist.

Origin

Happy numbers were brought to the attention of Reg Allenby [4], a British author and Senior Lecturer in pure mathematics at Leeds University, by his daughter. She had learned of them at school, but they "may have originated in Russia" (Guy 2004:§E34).