Happy number
From Wikipedia, the free encyclopedia
A happy number is any number that eventually reduces to 1 when the following process is used: take the sum of the squares of its digits, and continue iterating this process until it yields 1, or produces an infinite loop. Numbers that are not happy are called unhappy numbers. A computer search up to 1020 suggests that about 12% of numbers are happy, though no proof is known. Happy numbers were originated by Reg. Allenby's daughter (Guy 2004:§E34)
For example, 7 is happy, as the associated sequence is:
- 72 = 49
- 42 + 92 = 97
- 92 + 72 = 130
- 12 + 32 + 02 = 10
- 12 + 02 = 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.
The study of happy numbers is an example of recreational mathematics in that it can involve extensive mathematical knowledge, but the topic is not a central part of serious research.
More formally, given a number n = n0, define a sequence n1, n2, ... where ni + 1 is the sum of the squares of the digits of ni. Then n is happy if and only if this sequence goes to 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)
Contents |
[edit] Sequence behavior
If 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 n has m digits, then the sum of the squares of its digits is at most 81m. For m = 4 and above,
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.
[edit] 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 (sequence A035497 in OEIS)
[edit] 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, 1002 represents the number 4, and
- .
Then, it is easy to see that there are happy numbers in every base. For instance, the numbers
- 1b,10b,100b,1000b,...
are all happy, for any base b.
By a similar argument to the one above for decimal happy numbers, we can see that unhappy numbers in base b lead to cycles of numbers less than 1000b. We can use the fact that if n < 1000b, then the sum of the squares of the base-b digits of n is less than or equal to
- 3(b − 1)2
which can be shown to be less than b3. This shows that once the sequence reaches a number less than 1000b, it stays below 1000b, and hence must cycle or reach 1.
In base 2, all numbers are happy. All binary numbers larger than 10002 decay into a value equal to or less than 10002, and all such values are happy: The following four sequences contain all numbers less than 10002:
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. Many bases have no happy numbers between one and b = 10b; the first few such are 9, 16, 18, 19, 20, 29, 30, and 34.
[edit] References
- Walter Schneider, Mathews: Happy Numbers.
- Eric W. Weisstein, Happy Number at MathWorld.
- Happy Numbers at The Math Forum.
- Guy, Richard (2004). Unsolved Problems in Number Theory (third edition). Springer-Verlag. ISBN 0-387-20860-7.