Examine individual changes

'{{short description|Numbers with a certain property involving recursive summation}} {{distinguish|text=[[Harshad number]] (derived from Sanskrit ''harśa'' meaning "great joy")}} A '''happy number''' in [[base]]-<math>b</math> is defined by the following process: Starting with any [[positive number|positive]] [[integer]], replace the number by the [[summation|sum]] of the squares of its [[numerical digit|digits]] in base-<math>b</math>, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle that does not include&nbsp;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''').<ref>{{cite web|url=http://mathworld.wolfram.com/SadNumber.html|title=Sad Number|publisher=Wolfram Research, Inc.|accessdate=2009-09-16}}</ref> == 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" {{harvcol|Guy|2004|p=§E34}}. == Overview == More formally, given a number <math>n = n_0</math> of base <math>b</math>, define a sequence <math>n_1, n_2, ...</math> where <math>n_{i+1}</math> is the sum of the squares of the digits of <math>n_i</math>. Let <math>n_i</math> be the <math>i</math>-th number of the sequence beginning with <math>n_0</math>. The number of digits in <math>n_i</math> can be found by :<math>k_i = 1 + \lfloor \log_{b}{n_i} \rfloor </math>, where <math>b</math> is the number base. The digits of <math>n_i</math> can be found as follows: :<math>n_{i, 0} = n_i \bmod{b}</math> and :<math>n_{i, j} = \frac{n_i \bmod{b^{j+1}} - n_i \bmod{b^{j}}}{b^{j}}</math> where <math>0 < j < k_i - 1</math>. The next number in the sequence is defined thus as :<math>n_{i+1} = \sum_{j=0}^{k_i-1} n_{i, j}^2</math>. A cycle is a sequence where two numbers in the sequence <math>n_i</math> and <math>n_{i+j}</math> are equal, where <math>j</math> is the length of the cycle. A fixed point is a cycle where <math>j = 1</math>. 0 and 1 are trivially fixed points in all bases. <math>n</math> is happy if and only the sequence starting with <math>n</math> ends in the fixed point of <math>1</math>. For example, in [[base 10]], 19 is happy, as the associated sequence is : 1² + 9² = 82, : 8² + 2² = 68, : 6² + 8² = 100, : 1² + 0² + 0² = 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. The happiness of a number is unaffected by rearranging the digits and by inserting or removing any number of zeros anywhere in the number. There are infinitely many happy numbers, as 1 is a happy number, and for every <math>n</math>, <math>b^n</math> (<math>10^n</math> in base <math>b</math>) is happy, since its sum is 1. 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 0s on the end of the number. ===Upper limits to numbers in cycles=== Numbers in base <math>b</math> lead to cycles or fixed points of numbers less than <math>b^3</math>. If <math>k_i \geq 4</math> : <math>n_i \geq b^{k_i-1} > b^2 k_i,</math> so any number <math>n_i \geq b^3</math> gets smaller as the sequence continues until <math>n_i < b^3</math>. Let <math>n_j</math> be the number for which the sum of squares of digits is largest among the numbers less than <math>b^3</math>. :<math>n_j = b^3 - 1 = (b - 1)b^2 + (b - 1)b + (b - 1)</math>, :<math>n_{j+1} = 3(b - 1)^2 = 2 b^2 + (b - 6) b + 3 = b^2 + (2b - 6) b + 3</math>. If <math>b < 6</math>, then :<math>n_{j+1} = b^2 + (2b - 6) b + 3 < b^2 + (b - 1) b + (b - 1)</math>. If <math>b \geq 6</math>, then :<math>b^2 + (b - 1) b + (b - 1) < n_{j+1} = 2 b^2 + (b - 6) b + 3 < 2 b^2 + (b - 1) b + (b - 1)</math> in which case, :<math>n_{j+2} = 2^2 + 3^2 + (b - 6)^2 < b^2 + (b - 1) b + (b - 1)</math>. Let <math>n_k</math> be the number for which the sum of squares of digits is largest among the numbers less than <math>n_{j+2}</math>. :<math>n_k = b^2 + (b - 1) b + (b - 1) = 2b^2 - 1</math> :<math>n_{k+1} = 1 + 2 (b - 1)^2 = 2b^2 - 4b + 3 = b^2 + (b - 4) b + 3 < b^2 + (b - 1) b + (b - 1)</math> Let <math>n_l</math> be the number for which the sum of squares of digits is largest among the numbers less than <math>n_{j+1}</math> for <math>b < 6</math> and less than <math>n_{k+1}</math> for <math>b \geq 6</math>. :<math>n_l = (b - 1) b + (b - 1) = b^2 - 1</math> :<math>n_{l+1} = 2(b - 1)^2</math> <math>n_l < n_{l+1} < n_{j+1}</math> for <math>b < 6</math> and <math>n_l < n_{l+1} < n_{k+1}</math> for <math>b \geq 6</math>. Thus, numbers in base <math>b</math> lead to cycles or fixed points of numbers <math>n < 1 + n_{l+1} = 1 + 2 (b - 1)^2</math>. This means that only numbers <math>n < 1 + 2 (b - 1)^2</math> are allowed to be fixed points or in cycles. For example, in base <math>b = 10</math> this means one only needs to check numbers <math>n < 163 = 1 + 2 (10 - 1)^2</math> for cycles and fixed points. === Happy bases === {{unsolved|mathematics|Are base 2 and 4 the only happy bases?}} A happy base is a number base <math>b</math> that has no cycles and whose only fixed point is 1. The only known happy bases are 2 and 4. There are no others less than {{val|5e8}}.<ref>{{Cite OEIS|sequencenumber=A161872|name=Smallest unhappy number in base n}}</ref> ==Cycles and fixed points== ===Fixed points (Cycles of length 1)=== ====Base b = km² + m + k==== Let <math>m, k</math> be integers and the number base <math>b = k m^2 + m + k > 1</math>. Let the digits of <math>n = n_0 = n_{0, 1} b + n_{0, 0}</math> be <math>n_{0, 1} = k</math> and <math>n_{0, 0} = m k + 1</math>. Then :<math>n_1 = (n_{0, 1})^2 + (n_{0, 0})^2</math> ::<math> = k^2 + (m k + 1)^2</math> ::<math> = k^2 + m^2 k^2 + 2 m k + 1</math> ::<math> = (m^2 + 1) k^2 + m k + m k + 1</math> ::<math> = k (k m^2 + m + k) + (m k + 1)</math> ::<math> = n_{0, 1} b + n_{0, 0}</math> ::<math> = n_0</math> Thus, <math>n</math> is a fixed point for base <math>b</math> for all <math>m > 0, k > 0</math>. Let the digits of <math>p = p_0 = p_{0, 1} b + p_{0, 0}</math> be <math>p_{0, 1} = m^2 k + m</math> and <math>p_{0, 0} = m k + 1</math>. Then :<math>p_1 = (p_{0, 1})^2 + (p_{0, 0})^2</math> ::<math> = (m^2 k + m)^2 + (m k + 1)^2</math> ::<math> = (m^2 + 1) (m k + 1)^2</math> ::<math> = (m^2 + 1) (m k)(m k + 1) + (m^2 + 1) (m k + 1)</math> ::<math> = (m^3 k + m k + m^2)(m k + 1) + (m k + 1)</math> ::<math> = m (k m^2 + m + k)(m k + 1) + (m k + 1)</math> ::<math> = p_{0, 1} b + p_{0, 0}</math> ::<math> = p_0</math> Thus, <math>p</math> is a fixed point for base <math>b</math> for all <math>m > 0, k > 0</math>. The table below gives the number base (in decimal) and the fixed points (in the number base) for every <math>m, k < 5</math>. {| class="wikitable" style="text-align:center; float:center" |+ Bases and Fixed points |- ! <math>b_{10}, n, p</math> || 0 || 1 || 2 || 3 || 4 |- ! 0 | 0, (01)*, (01)* || 1, (11)*, (01)* || 2, (21)*, 01 || 3, (31)*, 01 || 4, (41)*, 01 |- ! 1 | 1, (01)*, (11)* || 3, 12, 22 || 5, 23, 33 || 7, 34, 44 || 9, 45, 55 |- ! 2 | 2, 01, (21)* || 7, 13, 63 || 12, 25, A5 || 17, 37, E7 || 22, 49, I9 |- ! 3 | 3, 01, (31)* || 13, 14, C4 || 23, 27, L7 || 33, 3A, UA || 43, 4D, [39]D |- ! 4 | 4, 01, (41)* || 21, 15, K5 || 38, 29, [36]9 || 55, 3D, [52]D || 72, 4H, [68]H |} ====Base b = T_k + 2 + (k² + 4)m==== Let <math>m, k</math> be integers. Then the [[triangular number]] <math>T_k = \frac{k(k+1)}{2}</math> and the number base <math>b = T_k + 2 + (k^2 + 4)m</math>. Let the digits of <math>n = n_0 = n_{0, 1} b + n_{0, 0}</math> be <math>n_{0, 1} = 2 (2m + 1)</math> and <math>n_{0, 0} = (2m + 1) k + 1</math>. Then :<math>n_1 = (n_{0, 1})^2 + (n_{0, 0})^2</math> ::<math> = (2(2m + 1))^2 + (((2m + 1))k + 1)^2</math> ::<math> = 4(2m + 1)^2 + (2m + 1)^2 k^2 + 2 (2m + 1) k + 1</math> ::<math> = (4 + k^2)(2m + 1)^2 + (2m + 1) k + ((2m + 1) k + 1)</math> ::<math> = (4 (2m + 1) + k^2 (2m + 1) + k)(2m + 1) + ((2m + 1) k + 1)</math> ::<math> = 2(2m + 1)(2 (2m + 1) + k^2 m + \frac{k^2 + k}{2}) + ((2m + 1) k + 1)</math> ::<math> = 2(2m + 1)(4m + 2 + k^2 m + T_k) + ((2m + 1) k + 1)</math> ::<math> = 2(2m + 1)((4 + k^2) m + T_k + 2) + ((2m + 1) k + 1)</math> ::<math> = n_{0, 1} b + n_{0, 0}</math> ::<math> = n_0</math> Thus, <math>n</math> is a fixed point for base <math>b</math> for all <math>n, k</math>. Let the digits of <math>p = p_0 = p_{0, 1} b + p_{0, 0}</math> be <math>p_{0, 1} = T_k + k^2 m</math> and <math>p_{0, 0} = (2m + 1) k + 1</math>. Then :<math>p_1 = (p_{0, 1})^2 + (p_{0, 0})^2</math> ::<math> = ((T_k + k^2 m))^2 + ((2m + 1) k + 1)^2</math> ::<math> = ((T_k + k^2 m))^2 + (2m + 1)^2 k^2 + 2 (2m + 1) k + 1</math> ::<math> = ((T_k + k^2 m))^2 + (4m^2 + 4m + 1) k^2 + (2m + 1) k + ((2m + 1) k + 1)</math> ::<math> = ((T_k + k^2 m))^2 + (4m^2 + 2m) k^2 + (2m + 1) k^2 + (2m + 1) k + ((2m + 1) k + 1)</math> ::<math> = ((T_k + k^2 m))^2 + 2(2m + 1) m k^2 + 2 (2m + 1) T_k + ((2m + 1) k + 1)</math> ::<math> = ((T_k + k^2 m))^2 + (4m + 2) (T_k + k^2 m) + ((2m + 1) k + 1)</math> ::<math> = (T_k + k^2 m + 4m + 2) (T_k + k^2 m) + ((2m + 1) k + 1)</math> ::<math> = (T_k + 2 + (k^2 + 4)m) (T_k + k^2 m) + ((2m + 1) k + 1)</math> ::<math> = p_{0, 1} b + p_{0, 0}</math> ::<math> = p_0</math> Thus, <math>p</math> is a fixed point for base <math>b</math> for all <math>m, k</math>. {| class="wikitable" style="text-align:center; float:center" |+ Bases and Fixed points |- ! <math>b_{10}, n, p</math> || 0 || 1 || 2 || 3 || 4 |- ! 1 | 2, (21)*, 01 || 3, 22, 12 || 5, 23, 33 || 8, 24, 64 || 12, 25, A5 |- ! 2 | 6, (61)*, 01 || 8, 64, 24 || 13, 67, 77 || 21, 6A, FA || 32, 6D, QD |- ! 3 | 10, (A1)*, 01 || 13, A6, 36 || 21, AB, BB || 34, AG, OG || 52, AL, [42]L |- ! 4 | 14, (E1)*, 01 || 18, E8, 48 || 29, EF, FF || 57, EM, XM || 72, ET, [58]T |} ===Cycles of length 2=== ====Base b = k³==== Let <math>k</math> be a positive integer and the number base <math>b = k^3</math>. Let <math>n_0 = k^2</math>. Then :<math>n_1 = (k^2)^2</math> ::<math> = k k^3</math> ::<math> = k b</math> :<math>n_2 = k^2 + 0^2</math> ::<math> = k^2</math> ::<math> = n_0</math> Thus, <math>k b</math> and <math>k^2</math> form a cycle of length 2 for base <math>b</math> for all <math>k > 1</math>. {| class="wikitable" ! <math>k</math> ! <math>b</math> ! Cycles |--- | 2 || [[base-8|8]] || 4 → 20 → 4 |--- | 3 || [[base-27|27]] || 9 → 30 → 9 |--- | 4 || [[base-64|64]] || G → 40 → G |} ====Base b = k³ + 2k==== Let <math>k</math> be a positive integer and the number base <math>b = k^3 + 2 k</math>. Let <math>n_0 = k^2 + 1</math>. Then :<math>n_1 = (k^2 + 1)^2</math> ::<math> = k^4 + 2 k^2 + 1</math> ::<math> = k (k^3 + 2k) + 1</math> ::<math> = k b + 1</math> :<math>n_2 = k^2 + 1^2</math> ::<math> = k^2 + 1</math> ::<math> = n_0</math> Thus, <math>k b</math> and <math>k^2 + 1</math> form a cycle of length 2 for base <math>b</math> for all <math>k \geq 1</math>. {| class="wikitable" ! <math>k</math> ! <math>b</math> ! Cycles |--- | 1 || [[base-3|3]] || 2 → 11 → 2 |--- | 2 || [[base-12|12]] || 5 → 21 → 5 |--- | 3 || 33 || A → 31 → A |} ==Base 10== In base 10, the 143 happy numbers up to 1000 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 {{OEIS|id=A007770}}. The distinct combinations of digits that form happy numbers below 1000 are (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. {{OEIS|id=A124095}}. Numbers that are happy follow a sequence that ends in 1. All unhappy numbers follow sequences that eventually reach the eight-number cycle : 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ... To see this fact, first note that it has been proven above that in base <math>b = 10</math> one only needs to check numbers <math>n < 1 + 2 (10 - 1)^2 = 163</math> for cycles and fixed points. An exhaustive search then shows that every number in the interval [1,&nbsp;162] either is happy or goes to the above unhappy 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. The first pair of consecutive happy numbers is 31 and 32.<ref>{{cite OEIS |1=A035502 |2=Lower of pair of consecutive happy numbers |accessdate=8 April 2011}}</ref> The first set of three consecutive is 1880, 1881, and 1882.<ref>{{cite OEIS |1=A072494 |2=First of triples of consecutive happy numbers |accessdate=8 April 2011}}</ref> It has been proved that there exist sequences of consecutive happy numbers of any natural-number length.<ref>{{Cite arxiv |title=Consecutive Happy Numbers |arxiv=math/0607213 |author1=Pan |first1=Hao |year=2006}}</ref> The beginning of the first run of at least ''n'' consecutive happy numbers for ''n''&nbsp;= 1, 2, 3, ... is<ref>{{Cite OEIS |1=A055629 |2=Beginning of first run of at least ''n'' consecutive happy numbers}}</ref> : 1, 31, 1880, 7839, 44488, 7899999999999959999999996, 7899999999999959999999996, ... By inspection of the first million or so happy numbers, it appears that they have a [[natural density]] of around 0.15. Perhaps surprisingly, then, the happy numbers do not have an asymptotic density. The upper density of the happy numbers is greater than 0.18577, and the lower density is less than 0.1138.<ref>{{Cite journal |title=On the Density of Happy Numbers |journal=Integers |volume=13 |issue=2 |arxiv=1110.3836 |last1=Gilmer |first1=Justin |year=2011 |bibcode=2011arXiv1110.3836G}}</ref> The number of happy numbers up to 10^''n'' for 1&nbsp;≤''n''&nbsp;≤&nbsp;20 is<ref>{{Cite OEIS |1=A068571 |2=Number of happy numbers <= 10^n}}</ref> : 3, 20, 143, 1442, 14377, 143071, 1418854, 14255667, 145674808, 1492609148, 15091199357, 149121303586, 1443278000870, 13770853279685, 130660965862333, 1245219117260664, 12024696404768025, 118226055080025491, 1183229962059381238, 12005034444292997294. ===Happy prime=== A happy prime is a number that is both happy and [[prime number|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 {{OEIS|id=A035497}}. All numbers, and therefore all primes, of the form 10^''n''&nbsp;+&nbsp;3 or 10^''n''&nbsp;+&nbsp;9 for ''n'' greater than 0 are happy.{{clarify|reason=are there infinitely many primes of these forms?|date=January 2019}} 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^''n''. * 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. (This does not mean that these are the only happy primes, as evidenced by the sequence above.) The [[palindromic prime]] {{nowrap|10¹⁵⁰⁰⁰⁶ + {{val|7426247e75000}} + 1}} is also a happy prime with {{val|150,007}} digits because the many 0s do not contribute to the sum of squared digits, and {{nowrap|1² + 7² + 4² + 2² + 6² + 2² + 4² + 7² + 1²}} =&nbsp;176, which is a happy number. Paul Jobling discovered the prime in 2005.<ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=76550 |title=The Prime Database: 10¹⁵⁰⁰⁰⁶ + 7426247 · 10⁷⁵⁰⁰⁰ + 1 |author=Chris K. Caldwell |work=utm.edu}}</ref> {{As of|2010}}, the largest known happy prime is 2^42643801&nbsp;−&nbsp;1 (a [[Mersenne prime]]).{{Dubious|date=December 2017}} Its decimal expansion has {{val|12,837,064}} digits.<ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=88847 |title=The Prime Database: 2^42643801 − 1 |author=Chris K. Caldwell |work=utm.edu}}</ref> Unlike happy numbers, rearranging the digits of a happy prime will not necessarily create another happy prime. For instance, while 19 is a happy prime, 91&nbsp;=&nbsp;13&nbsp;×&nbsp;7 is not prime (but is still happy). ==Happy numbers in other bases== The definition of happy numbers depends on the decimal ([[base 10]]) representation of the numbers. The definition can be extended to other [[Radix|bases]]. === Other bases === {| class="wikitable" ! Base ! Cycles |--- | [[base-5|5]] || 4 → 31 → 20 → 4 |--- | [[base-6|6]] || 5 → 41 → 25 → 45 → 105 → 42 → 32 → 21 → 5 |--- | 7 || 2 → 4 → 22 → 11 → 2 |--- | [[base-8|8]] || 5 → 31 → 12 → 5 15 → 32 → 15 |--- | [[base-9|9]] || 58 → 108 → 72 → 58 |--- | [[base-10|10]] || 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 |--- | [[base-12|12]] ||8 → 54 → 35 → 2A → 88 → A8 → 118 → 56 → 51 → 22 → 8 18 → 55 → 42 → 18 68 → 84 → 68 |--- | 14 || 5 → 1B → 8A → BA → 11B → 8B → D3 → CA → 136 → 34 → 5 29 → 85 → 61 → 29 |--- | [[base-16|16]] || D → A9 → B5 → 92 → 55 → 32 → D |} === Balanced ternary === [[Balanced ternary]] is a special case in that the happiness (or sadness) of a number is an indication also of being odd (or even). Specifically, because 3&nbsp;−&nbsp;1&nbsp;=&nbsp;2, the sum of every digit of a base-3 number will indicate divisibility by 2 [[if and only if]] the sum of digits ends in 0 or 2. This is the general application of the test for divisibility by 9 in base 10. In [[balanced ternary]], the digits are 1, −1 and 0. The square of both 1 and −1 are 1, and 1&nbsp;+&nbsp;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,&nbsp;−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.{{citation needed|date=June 2013}} ==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. Given a number <math>n = n_0</math> of base <math>b</math>, define a sequence <math>n_1, n_2, ...</math> where <math>n_{i+1}</math> is the sum of the cubes of the digits of <math>n_i</math>. A cycle is a sequence where two numbers in the sequence <math>n_i</math> and <math>n_{i+j}</math> are equal, where <math>j</math> is the length of the cycle. A fixed point is a cycle where <math>j = 1</math>. 0 and 1 are trivially fixed points in all bases. <math>n</math> is happy if and only the sequence starting with <math>n</math> ends in the fixed point of <math>1</math>. ===Sequence algorithm=== Let <math>n_i</math> be the <math>i</math>-th number of the sequence beginning with <math>n_0</math>. The number of digits in <math>n_i</math> can be found by :<math>k_i = 1 + \lfloor \log_{b}{n_i} \rfloor </math>, where <math>b</math> is the number base. The digits of <math>n_i</math> can be found as follows: :<math>n_{i, 0} = n_i \bmod{b}</math> and :<math>n_{i, j} = \frac{n_i \bmod{b^{j+1}} - n_i \bmod{b^{j}}}{b^{j}}</math> where <math>0 < j < k_i - 1</math>. The next number in the sequence is defined thus as :<math>n_{i+1} = \sum_{j=0}^{k_i-1} n_{i, j}^3</math>. ===Upper limits to numbers in cycles=== Numbers in base <math>b</math> lead to cycles or fixed points of numbers less than <math>b^4</math>. If <math>k_i \geq 5</math> : <math>n_i \geq b^{k_i-1} > b^3 k_i,</math> so any number <math>n_i \geq b^4</math> gets smaller as the sequence continues until <math>n_i < b^4</math>. ===Base 10=== 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 (=&nbsp;3&nbsp;×&nbsp;9²) produces a number that is strictly smaller, when summing the cubes of the digits each number above 2916 (=&nbsp;4&nbsp;×&nbsp;9³) produces a number that is strictly smaller. By conducting an exhaustive search of [1,&nbsp;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; and *those that eventually reach one of the loops: :: 133 → 55 → 250 → 133 :: 217 → 352 → 160 → 217 :: 1459 → 919 → 1459 :: 136 → 244 →136 All multiples of three terminate at 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, fifth powers, seventh powers, etc.) of their digits must have a remainder of 1 when dividing by 3. All numbers that are congruent to 2 [[Modulo operation|modulo]] 3 terminate at either 371 or 407. The only positive whole numbers that are the sum of the cubes of their digits are 1, 153, 370, 371 and 407 {{OEIS|id=A046197}}. === Other bases === In [[base 2]], the process of defining numbers reduces down to [[digit sum]] iteration, as <math>0^3 = 0</math> and <math>1^3 = 1</math>, and iterated digit sums always reduces down to 1, making base 2 a happy base. == 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 between 1 and 100 end in the loop: : 13139 → 6725 → 4338 → 4514 → 1138 → 4179 → 9219 → 13139, or alternate between 2178 and 6514, or terminate at 1634, 8208 or 9474 which perpetually produce themselves. === Other bases === It is easy to see that there are infinitely many happy numbers in every base. For instance, the numbers :<math>1_b,10_b,100_b,1000_b,... \quad(= b^n \text{ for all positive integers } n)</math> are all happy, for any base ''b''. By a similar argument to the one above for decimal happy numbers, for a given power <math>p</math> unhappy numbers in base <math>b</math> lead to cycles of numbers less than <math>(10^{p+1})_b</math>. If <math>n < (10^{p+1})_b</math>, then the sum of the squares of the base-''b'' digits of <math>n</math> is less than or equal to :<math>(p+1)(b-1)^{p}</math>, which is less than <math>b^{p+1}</math> for all bases, as the [[polynomial]] of degree <math>p</math> : <math>f(b) = b^{p+1} - (p+1)(b - 1)^{p} </math> is [[monotonically increasing]] and has only one root <math>b < 1</math> if <math>p</math> is even, and is always positive if <math>p</math> is odd. This shows that once the sequence reaches a number less than <math>(10^{p+1})_b</math>, it stays below <math>(10^{p+1})_b</math>, and hence must cycle or reach 1. In [[base 2]], the process of defining numbers reduces down to [[digit sum]] iteration, as <math>0^p = 0</math> and <math>1^p = 1</math>, and iterated digit sums always reduces down to 1, making base 2 a happy base. ==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 bookkeeping (for example, the Python example precomputes the squares of all 10 digits). A simple test in [[Python (programming language)|Python]] to check if a number is happy:<ref>[http://rosettacode.org/wiki/Happy_Number Happy Number] Rosetta Code</ref> <source lang=python> 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 </source> 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: <source lang=python> def is_happy(n): return (n == 1 or n > 4 and is_happy(happy(n))) </source> ==See also== *[[Fortunate number]] *[[Harshad number]] *[[Lucky number]] ==References== {{reflist}} ==Literature== * {{Cite book | last = Guy | first = Richard | authorlink = Richard K. Guy | year = 2004 | title = Unsolved Problems in Number Theory |edition=3rd | publisher = [[Springer-Verlag]] | isbn= 0-387-20860-7 | ref = harv }} ==External links== * Schneider, Walter: [https://web.archive.org/web/20060204094653/http://www.wschnei.de/digit-related-numbers/happy-numbers.html Mathews: Happy Numbers.] * {{MathWorld|urlname=HappyNumber|title=Happy Number}} * [http://nazgul04.ddns.net/happy/happy.php calculate if a number is happy] * [http://mathforum.org/library/drmath/view/55856.html Happy Numbers] at The Math Forum. * [http://numberphile.com/videos/melancoil.html 145 and the Melancoil] at Numberphile. * {{cite web|last=Symonds|first=Ria|title=7 and Happy Numbers|url=http://www.numberphile.com/videos/7happy.html|work=Numberphile|publisher=[[Brady Haran]]}} {{Use dmy dates|date=June 2011}} {{Classes of natural numbers}} {{Prime number classes}} {{DEFAULTSORT:Happy Number}} [[Category:Base-dependent integer sequences]] [[Category:Recreational mathematics]]'