Happy number

From Wikipedia, the free encyclopedia

Not to be confused with Harshad number (derived from Sanskrit harsa: "great joy").

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 (or sad numbers^[1]).

[edit] Overview

More formally, given a number $n = n 0$ , define a sequence $n 1$ , $n 2$ , ... where $n i + 1$ is the sum of the squares of the digits of $n i$ . Then $n$ is happy if and only if there exists i such that $n i = 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 happy numbers below 500 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).

Rearranging the digits of a number does not change whether the number is happy, nor does for example multiplying a number by any positive integer power of ten.

[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 $92 m$ , or $81 m$ .

For $m = 4$ and above,

$n\geq10^{m-1}>81m$

so any number over 1000 gets smaller under this process and in particular becomes a number with strictly fewer digits. 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. An exhaustive search then shows that every number in the interval [1,99] is either happy or goes to the above cycle.

The above work produces the interesting result that no positive whole number other than 1 is the sum of the squares of its own digits.

There are infinitely many happy numbers and infinitely many unhappy numbers. For example, if you wonder if any number will produce 14308, say, the quick response is to write down the digit 1 14308 times and you have created such a number. In fact, you have created infinitely many such numbers since there is nothing to stop you slotting in as many zero digits as you fancy.

The first pair of consecutive happy numbers is 31, 32. The first set of triplets is 1880, 1881, and 1882.

An interesting question is to wonder about the density of happy numbers. In the interval [1,243] 15.6% (3s.f.) are Happy.

[edit] Happy primes

A happy prime is a happy number that is prime. The happy primes below 500 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).

All numbers, and therefore all primes, of the form $10 n + 3$ and $10 n + 9$ for n greater than 0 are Happy. To see this, note that

All such numbers will have at least 2 digits;
The first digit will always be 1 due to the 10ⁿ
The last digit will always be either 3 or 9.
Any other digits will always be 0 (and therefore will not contribute to the sum of squares of the digits).
- The sequence for adding 3 is: 1² + 3² = 10 → 1² = 1
- The sequence for adding 9 is: 1² + 9² = 82 → 64 + 4 = 68 → 100 -> 1

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 $12 + 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.^[2]

As of June 2007^[update], 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.^[3] ^[4] Jens K. Andersen identified it as the largest known happy prime in June 2007.

[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

$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

1 b,10 b,100 b,1000 b,...

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 $1000 b$ . We can use the fact that if $n < 1000 b$ , 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 $b 3$ . This shows that once the sequence reaches a number less than $1000 b$ , it stays below $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 $10002$ :

$111_2 \rightarrow 11_2 \rightarrow 10_2 \rightarrow 1$

$110_2 \rightarrow 10_2 \rightarrow 1$

$101_2 \rightarrow 10_2 \rightarrow 1$

$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. There are no others less than 500,000,000.^[5]

In base 3, other than the happy numbers, there are three types of unhappy number:

those that eventually reach the loop $2_3 \rightarrow 11_3 \rightarrow 2_3 \rightarrow ...$

those that eventually reach $123$ which perpetually produces itself.

those that eventually reach $223$ which perpetually produces itself.

In base 5, other than the happy numbers, there are also three types of unhappy number:

those that eventually reach the loop $4_5 \rightarrow 31_5 \rightarrow 20_5 \rightarrow 4 \rightarrow ...$

those that eventually reach $235$ which perpetually produces itself.

those that eventually reach $335$ which perpetually produces itself.

In base 6, other than the happy numbers, there is just the one type of unhappy number: any number which does not eventually reach $16$ instead eventually reaches the loop $32_6 \rightarrow 21_6 \rightarrow 5_6 \rightarrow 41_6 \rightarrow 25_6 \rightarrow 45_6 \rightarrow 105_6 \rightarrow 42_6 \rightarrow 32_6 \rightarrow ...$ .

In base 7, other than the happy numbers, there are six different types of unhappy number:

those that eventually reach the loop $2_7 \rightarrow 4_7 \rightarrow 22_7 \rightarrow 11_7 \rightarrow 2_7 \rightarrow ...$

those that eventually reach $347$ which perpetually produces itself.

those that eventually reach $137$ which perpetually produces itself.

those that eventually reach the loop $23_7 \rightarrow 16_7 \rightarrow 52_7 \rightarrow 41_7 \rightarrow 23_7 \rightarrow ...$

those that eventually reach $637$ which perpetually produces itself.

those that eventually reach $447$ which perpetually produces itself.

In base 8, other than happy numbers, there are five different types of unhappy number:

those that eventually reach the loop $4_8 \rightarrow 20_8 \rightarrow 4_8 \rightarrow ...$

those that eventually reach the loop $5_8 \rightarrow 31_8 \rightarrow 12_8 \rightarrow 5_8 \rightarrow ...$

those that eventually reach the loop $32_8 \rightarrow 15_8 \rightarrow 32_8 \rightarrow ...$

those that eventually reach $248$ which perpetually produces itself.

those that eventually reach $648$ which perpetually produces itself.

In base 9, other than happy numbers, there are four different types of unhappy number:

those that eventually reach $559$ which perpetually produces itself.

those that eventually reach the loop $58_9 \rightarrow 108_9 \rightarrow 72_9 \rightarrow 58_9 \rightarrow ...$

those that eventually reach $459$ which perpetually produces itself.

those that eventually reach the loop $75_9 \rightarrow 82_9 \rightarrow 75_9 \rightarrow ...$

[edit] Cubing the digits rather than squaring

An interesting extension to the Happy Numbers problem is to find the sum of the cubes of the digits rather than the sum of the squares of the digits. For example, working in base 10, 1579 is happy, since:

1³+5³+7³+9³=1+125+343+729=1198

1³+1³+9³+8³=1+1+729+512=1243

1³+2³+4³+3³=1+8+64+27=100

1³+0³+0³=1

In the same way that when summing the squares of the digits (and working in base 10) each number above 243(=3*81) produces a number which is strictly smaller, when summing the cubes of the digits each number above 2916(=4*729) produces a number which is strictly smaller.

By conducting an exhaustive search of [1,2916] one finds that for summing the cubes of digits base 10 there are happy numbers and eight different types of unhappy number:

those that eventually reach $371$ which perpetually produces itself.

those that eventually reach $153$ which perpetually produces itself.

those that eventually reach the loop $133 \rightarrow 55 \rightarrow 250 \rightarrow 133 \rightarrow ...$

those that eventually reach $370$ which perpetually produces itself.

those that eventually reach the loop $217 \rightarrow 352 \rightarrow 160 \rightarrow 217 \rightarrow ...$

those that eventually reach $407$ which perpetually produces itself.

those that eventually reach the loop $1459 \rightarrow 919 \rightarrow 1459 \rightarrow ...$

those that eventually reach the loop $136 \rightarrow 244 \rightarrow 136 \rightarrow ...$

Starting with the happy numbers and then following with the unhappy numbers in the order given above, the density of each type of number in the interval [1,2916] is 1.54%, 28.4%, 34.7%, 5.73%, 17.4%, 4.60%, 3.60%, 2.67% and 1.34% (all to 3s.f.).

Intriguingly, the second type of unhappy number includes all multiples of three . This fact can be proved by the exhaustive search up to 2916 and noting that a number is a multiple of three if and only if the sum of digits is a multiple of three if and only if the sum of its cubed digits are a multiple of three. By similar reasoning, all happy numbers of this type must have a remainder of 1 when dividing by 3.

One interesting result which comes from the above work is that the only positive whole numbers which are the sum of the cubes of their digits are 1, 153, 370, 371 and 407.

[edit] Origin

Happy numbers were brought to the attention of Reg Allenby,^[6] 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).

[edit] Popular culture

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 about to collide with a sun.

[edit] Notes

^ "Sad Number". Wolfram Research, Inc.. http://mathworld.wolfram.com/SadNumber.html. Retrieved 2009-09-16.
^ The Prime Database: 10^150006+7426247*10^75000+1
^ The Prime Database: 4847*2^3321063+1
^ http://www.seventeenorbust.com/documents/prime-101205.txt
^ OEIS
^ Reg Allenby page

[edit] References

Walter Schneider, Mathews: Happy Numbers.
Weisstein, Eric W., "Happy Number" from MathWorld.
Happy Numbers at The Math Forum.

Guy, Richard (2004), Unsolved Problems in Number Theory (third edition), Springer-Verlag, ISBN 0-387-20860-7

[0] "Sad Number". Wolfram Research, Inc.. http://mathworld.wolfram.com/SadNumber.html. Retrieved 2009-09-16.

[1] The Prime Database: 10^150006+7426247*10^75000+1

[2] The Prime Database: 4847*2^3321063+1

[3] ttp://www.seventeenorbust.com/documents/prime-101205.txt

[4] OEIS

[5] Reg Allenby page

[1]

[2]

[3]

[4]

[5]

[6]

Happy number

From Wikipedia, the free encyclopedia

Contents

[edit] Overview

[edit] Sequence behavior

[edit] Happy primes

[edit] Happy numbers in other bases

[edit] Cubing the digits rather than squaring

[edit] Origin

[edit] Popular culture

[edit] Notes

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages