Happy number

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

A happy number is a number 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 either 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]

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 the sequence are unhappy.

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

1² + 9² = 82

8² + 2² = 68

6² + 8² = 100

1² + 0² + 0² = 1.

The 143 happy numbers up to 1,000 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, 536, 556, 563, 565, 566, 608, 617, 622, 623, 632, 635, 637, 638, 644, 649, 653, 655, 656, 665, 671, 673, 680, 683, 694, 700, 709, 716, 736, 739, 748, 761, 763, 784, 790, 793, 802, 806, 818, 820, 833, 836, 847, 860, 863, 874, 881, 888, 899, 901, 904, 907, 910, 912, 913, 921, 923, 931, 932, 937, 940, 946, 964, 970, 973, 989, 998, 1000 (sequence A007770 in the OEIS).

The happiness of a number is unaffected by rearranging the digits, and by inserting or removing any number of zeros anywhere in the number.

The distinct combinations of digits that form happy numbers below 1,000 follow (the rest are just rearrangements and/or insertions of zero digits):

1, 7, 13, 19, 23, 28, 44, 49, 68, 79, 129, 133, 139, 167, 188, 226, 236, 239, 338, 356, 367, 368, 379, 446, 469, 478, 556, 566, 888, 899. (sequence A124095 in the OEIS).

Sequence behavior

Numbers that are happy follow a sequence that ends in 1. All non-happy numbers follow sequences that reach the cycle:

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

\dots

To see this fact, first note that if n has m digits, then the sum of the squares of its digits is at most $9^{2}m$ , or $81m$ .

For $m=4$ and above,

n\geq 10^{{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] either is happy or goes to the above cycle.

The above work produces the interesting result that no positive integer other than 1 is the sum of the squares of its own digits, since any such number would be a fixed point of the described process.

There are infinitely many happy numbers and infinitely many unhappy numbers. Consider the following proof:

1 is a happy number, and for every n, 10ⁿ is happy since its sum is 1
and for every n, 2 × 10ⁿ is unhappy since its sum is 4 and 4 is an unhappy number.

Indeed, the happiness of a number is preserved by removing or inserting zeroes at will, since they do not contribute to the cross sum. See the above proof, especially by appending zeroes on the end of the number (by multiplying with 10ⁿ).

The first pair of consecutive happy numbers is 31, 32.^[2] The first set of triplets is 1880, 1881, and 1882.^[3] For any natural number n, there exists a sequence of n consecutive happy numbers.^[4] The beginning of the first run of at least n consecutive happy numbers for n = 1, 2, 3, $\ldots$ is:

1, 31, 1880, 7839, 44488, 7899999999999959999999996, 7899999999999959999999996,

\ldots

(

A055629).

There is an outstanding question about the density of happy numbers. It is unknown whether the happy numbers have an asymptotic density. Currently, it is known that the upper density is less than 18.577%, and the lower density is greater than 11.38%.^[5]

Happy prime

A happy prime is a number that is both happy and 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 the OEIS).

All numbers, and therefore all primes, of the form 10ⁿ + 3 or 10ⁿ + 9 for n greater than 0 are happy. This does not mean that these are the only happy primes, as evidenced by the sequence above. To see this, note that

All such numbers will have at least two 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 numbers ending in 3 is: 1² + 3² = 10 → 1² = 1.
- The sequence for numbers ending in 9 is: 1² + 9² = 82 → 8² + 2² = 64 + 4 = 68 → 6² + 8² = 36 + 64 = 100 -> 1.

The palindromic prime 10¹⁵⁰⁰⁰⁶ + 7426247×10⁷⁵⁰⁰⁰ + 1 is also a happy prime with 150,007 digits because the many 0's do not contribute to the sum of squared digits, and $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.^[6]

As of 2010, the largest known happy prime is $2^{{42643801}}-1$ (Mersenne prime). Its decimal expansion has 12,837,064 digits.^[7]

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, $100_{2}$ 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, unhappy numbers in base b lead to cycles of numbers less than $1000_{b}$ . 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}$ , for $b\geq 5$ . 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 $1000_{2}$ :

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.^[8]

Base 3 is also a special case in that the happiness (or sadness) of a number is an indication also of being odd (or Even). Specifically, because 3 - 1 = 2, the sum of every digit of a base 3 number will indicate divisibility by 2 IFF the sum of digits ends in 0 or 2. This is the general application of the test for 9-divisibility in base 10. In balanced ternary, the digits are 1, -1 and 0. The square of both 1 and -1 are 1, and 1 + 1 is 2, which is the only balanced ternary cycle. For every pair of digits 1 or -1, their sum is 0 and the sum of their squares is 2 and if there are an even number of 1, -1 sets, the number divisible by 2 and sad and if odd, it is happy. In this case, the result always end in a one-digit cycle of 0, 1 or 2, repeated infinitely. In unbalanced ternary, the digits square to 1 and 4, and in this case there are 5 loops: 0, 1, 2→4→2, 5 and 8. While all even numbers are sad because they end in the 0, 2 or 8 cycle, some odd numbers are also sad because they end in 5 or 1, and are thus occasionally sad.

In base 12, there is no other happy number between 10 (decimal 12) and 100 (decimal 144), there are 3 fixed points: 1, 25, ᘔ5, and 4 cycles:

5 -> 21 -> 5 (length 2)

8 -> 54 -> 35 -> 2ᘔ -> 88 -> ᘔ8 -> 118 -> 56 -> 51 -> 22 -> 8 (length ᘔ)

18 -> 55 -> 42 -> 18 (length 3)

68 -> 84 -> 68 (length 2)

The numbers 25 (decimal) and ᘔ5 (decimal 125) are Armstrong numbers in base 12 A161949, there are no 2-digit Armstrong numbers in base 10.

In hexadecimal, there is only 1 fixed point: 1, and 1 cycle:

D, A9, B5, 92, 55, 32, D (length 7)

The status in base 16 is similar to base 10.

Cubing the digits rather than squaring

A variation 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 $153,370,371,$ or $407$ which perpetually produce themselves.

those that eventually reach the loops:

$133\rightarrow 55\rightarrow 250\rightarrow 133\rightarrow 55\rightarrow 250...$

$217\rightarrow 352\rightarrow 160\rightarrow 217\rightarrow 352\rightarrow 160...$ ,

as well as those that alternate between $1459$ and $919$ or between $136$ and $244$ .

All multiples of three end in 153. This fact can be proved by the exhaustive search up 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 when summing up odd powers (e.g. cubes, 5th powers, 7th powers, etc.) of their digits must have a remainder of 1 when dividing by 3.

All numbers that are congruent to 2 (mod 3) end in either 371 or 407.

The only positive whole numbers which are the sum of the cubes of their digits are 1, 153, 370, 371 and 407 (sequence A046197 in the OEIS).

Higher powers

For higher powers, the density of happy numbers declines.

Taking the sum of the fourth powers of the digits, one can find that most numbers in the range 1-100 end in the loop:

13139, 6725, 4338, 4514, 1138, 4179, 9219, 13139, 6725, 4338, 4514, 1138, 4179, 9219, etc.

as well as those that alternate between 2178 and 6514 and those that end in $1634,8208$ , or $9474$ which perpetually produce themselves.

Origin

The origin of happy numbers is not clear. Happy numbers were brought to the attention of Reg Allenby (a British author and senior lecturer in pure mathematics at Leeds University) by his daughter, who had learned of them at school. However, they "may have originated in Russia" (Guy 2004:§E34).

Popular culture

In the 2007 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 star. When the Doctor learns that nobody on the spaceship besides himself has heard of happy numbers, he asks, "Don't they teach recreational mathematics anymore?"

The contestants in the 2012 University Challenge final were asked to identify a sequence of numbers as happy primes in a picture round.

Programming example

The examples below apply the 'happy' process described in the definition of happy given at the top of this article, repeatedly; after each time, they check for both halt conditions: reaching 1, and repeating a number. Everything else is book-keeping (for example, the Python example precomputes the squares of all 10 digits).

A simple test in Python to check if a number is happy:^[9]

def square(x):
    return int(x) * int(x)

def happy(number):
    return sum(map(square, list(str(number))))

def is_happy(number):
    seen_numbers = set()
    while number > 1 and (number not in seen_numbers):
        seen_numbers.add(number)
        number = happy(number)
    return number == 1

When the algorithm ends in a cycle of repeating numbers, this cycle always includes the number 4, so it is not even necessary to store previous numbers in the sequence:

def is_happy(number):
    if number == 1:
        return True
    elif number == 4:
        return False
    else:
        return is_happy(happy(number))

References

↑ "Sad Number". Wolfram Research, Inc. Retrieved 2009-09-16.
↑ "Lower of pair of consecutive happy numbers". Online Encyclopedia of Integer Sequences. Retrieved 8 April 2011.
↑ "First of triples of consecutive happy numbers". Online Encyclopedia of Integer Sequences. Retrieved 8 April 2011.
↑ Pan, Hao (2006). "Consecutive Happy Numbers". arXiv:math/0607213.
↑ Gilmer, Justin (2011). "On the Density of Happy Numbers". Integers. 13 (2). arXiv:1110.3836.
↑ Chris K. Caldwell. "The Prime Database: 10^150006+7426247*10^75000+1". utm.edu.
↑ Chris K. Caldwell. "The Prime Database: 2^42643801-1". utm.edu.
↑ "Sloane's A161872 : Smallest unhappy number in base n". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
↑ Happy Number Rosetta Code

Literature

Guy, Richard (2004). Unsolved Problems in Number Theory (3rd ed.). Springer-Verlag. ISBN 0-387-20860-7.

External links

Schneider, Walter: Mathews: Happy Numbers.
Weisstein, Eric W. "Happy Number". MathWorld.

Happy Numbers at The Math Forum.
145 and the Melancoil at Numberphile.
Symonds, Ria. "7 and Happy Numbers". Numberphile. Brady Haran.

Classes of natural numbers

Powers and
related numbers

Of the form
a × 2^b ± 1

Other polynomial
numbers

Recursively defined
numbers

Possessing a
specific set
of other numbers

Expressible via
specific sums

Generated
via a sieve

Lucky

Code related

Meertens

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star

non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral

non-centered	Tetrahedral Octahedral Dodecahedral Icosahedral Stella octangula

pyramidal	Square pyramidal Pentagonal pyramidal Hexagonal pyramidal Heptagonal pyramidal

4-dimensional

centered	Centered pentachoric Squared triangular

non-centered	Pentatope

Pseudoprimes

Combinatorial
numbers

Arithmetic functions

By properties of σ(n)	Abundant Almost perfect Arithmetic Colossally abundant Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical number Primitive abundant Quasiperfect Refactorable Sublime Superabundant Superior highly composite Superperfect

By properties of Ω(n)	Almost prime Semiprime

By properties of φ(n)	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient

By properties of s(n)	Amicable Betrothed Deficient Semiperfect

Dividing a quotient

Other prime factor
or divisor related
numbers

Recreational
mathematics

Base-dependent
numbers

This article is issued from Wikipedia - version of the 11/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.