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 <math>b</math>-'''happy number''' is a [[natural number]] in a given [[number base]] <math>b</math> that eventually reaches 1 when iterated over the [[Narcissistic number#Perfect digital invariant|perfect digital invariant function]] for <math>p = 2</math>. Those numbers that do not end in 1 are <math>b</math>-'''unhappy numbers''' (or <math>b</math>-'''sad numbers''').<ref>{{cite web|url=http://mathworld.wolfram.com/SadNumber.html|title=Sad Number|publisher=Wolfram Research, Inc.|accessdate=2009-09-16}}</ref> 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}}. == Happy numbers and the perfect digital invariant function == More formally, let <math>n</math> be a natural number. Given the [[Narcissistic number#Perfect digital invariant|perfect digital invariant function]] :<math>F_{p, b}(n) = \sum_{i=0}^{\lfloor \log_{b}{n} \rfloor} {\left(\frac{n \bmod{b^{i+1}} - n \bmod{b^{i}}}{b^{i}}\right)}^p</math>. for base <math>b > 1</math>, a number <math>n</math> is <math>b</math>-happy if there exists a <math>j</math> such that <math>F_{2, b}^j(n) = 1</math>, where <math>F_{2, b}^j</math> represents the <math>j</math>-th [[Iterated function|iteration]] of <math>F_{2, b}</math>, and <math>b</math>-unhappy otherwise. If a number is a [[Narcissistic number#Perfect digital invariant|nontrivial perfect digital invariant]] of <math>F_{2, b}</math>, then it is <math>b</math>-unhappy. For example, 19 is 10-happy, as : <math>F_{2, 10}(19) = 1^2 + 9^2 = 82</math> : <math>F_{2, 10}^2(19) = F_{2, 10}(82) = 8^2 + 2^2 = 68</math> : <math>F_{2, 10}^3(19) = F_{2, 10}(68) = 6^2 + 8^2 = 100</math> : <math>F_{2, 10}^4(19) = F_{2, 10}(100) = 1^2 + 0^2 + 0^2 = 1</math> For example, 347 is 6-happy, as : <math>F_{2, 6}(347) = F_{2, 6}(1335_6) = 1^2 + 3^2 + 3^2 + 5^2 = 44</math> : <math>F_{2, 6}^2(347) = F_{2, 6}(44) = H_{2, 6}(112_6) = 1^2 + 1^2 + 2^2 = 6</math> : <math>F_{2, 6}^3(347) = F_{2, 6}(6) = H_{2, 6}(10_6) = 1^2 + 0^2 = 1</math> There are infinitely many <math>b</math>-happy numbers, as 1 is a <math>b</math>-happy number, and for every <math>n</math>, <math>b^n</math> (<math>10^n</math> in base <math>b</math>) is <math>b</math>-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. If <math>m</math> is a [[prime number|prime]] [[divisor]] of <math>b - 1</math>, and the power <math>p \equiv 1 \bmod (m - 1)</math>, then all (<math>p</math>, <math>b</math>)-happy numbers <math>n</math> must satisfy the congruence relation <math>n \equiv 1 \bmod m</math>. <ref>{{Cite arxiv |title=Consecutive Happy Numbers |arxiv=math/0607213 |author1=Pan |first1=Hao |year=2006}}</ref> For example, all happy numbers in [[base 3]] when summing up powers of their digits must be odd, and all happy numbers in [[base 4]] and [[base 10]] 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. === Natural density of <math>b</math>-happy numbers === By inspection of the first million or so 10-happy numbers, it appears that they have a [[natural density]] of around 0.15. Perhaps surprisingly, then, the 10-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> === Happy bases === {{unsolved|mathematics|Are [[base 2]] and [[base 4]] the only bases that are happy?}} A happy base is a number base <math>b</math> where every number is <math>b</math>-happy. The only happy bases less than {{val|5e8}} are [[base 2]] and [[base 4]].<ref>{{Cite OEIS|sequencenumber=A161872|name=Smallest unhappy number in base n}}</ref> ==Specific <math>b</math>-happy numbers== ===4-happy numbers=== It is proved [[Narcissistic number#Perfect digital invariant|here]] that for <math>p = 2</math> in base <math>b > 2</math> one only needs to check numbers <math>n \leq (2 - 2)^2 + 2 (b - 1)^2 = 2 (b - 1)^2</math> for cycles and fixed points of <math>F_{2, b}</math>. For <math>b = 4</math>, that upper limit is <math>2 \cdot 3^2 = 18_{10} = 102_4</math>. The following sequences lead to the fixed point 1: * 3 → 21 → 11 → 2 → 10 → 1 * 23 → 31 → 22 → 20 → 10 → 1 * 33 → 102 → 11 → 2 → 10 → 1 With rearrangements and/or insertions of zero digits, this shows that every number in the interval [1,&nbsp;102] is happy. As a result, every number in base 4 is happy, and [[base 4]] is a happy base. ===10-happy numbers=== It is proved [[Narcissistic number#Perfect digital invariant|here]] that for <math>p = 2</math> in base <math>b > 2</math> one only needs to check numbers <math>n \leq (2 - 2)^2 + 2 (b - 1)^2 = 2 (b - 1)^2</math> for cycles and fixed points of <math>F_{2, b}</math>. For <math>b = 10</math>, that upper limit is <math>2 \cdot 9^2 = 162</math>. An exhaustive search then shows that every number in the interval [1,&nbsp;162] eventually reaches either the eight-number cycle : 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ... and is unhappy or the trivial fixed point 1 and is happy. Because base 10 has no other fixed points except for 1, no positive integer other than 1 is the sum of the squares of its own digits. 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}}. 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, ... The number of 10-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 primes== A <math>b</math>-happy prime is a number that is both <math>b</math>-happy and [[prime number|prime]]. Unlike happy numbers, rearranging the digits of a <math>b</math>-happy prime will not necessarily create another happy prime. For instance, while 19 is a 10-happy prime, 91&nbsp;=&nbsp;13&nbsp;×&nbsp;7 is not prime (but is still 10-happy). All prime numbers are 2-happy and 4-happy primes, as [[base 2]] and [[base 4]] are happy bases. ===10-happy primes=== In [[base 10]], the 10-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}}. The [[palindromic prime]] {{nowrap|10¹⁵⁰⁰⁰⁶ + {{val|7426247e75000}} + 1}} is a 10-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 10-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 10-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> ==Extension to negative integers== Happy numbers can be extended to the negative integers by use of a [[Signed-digit representation#Balanced form|balanced base]] to represent each integer. ===Balanced ternary=== In [[balanced ternary]], the digits are 1, −1 and 0. This results in the following: * With even powers <math>p \equiv 0 \bmod 2</math>, 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. As <math>0^p = 0</math> and <math>{(-1)}^p = 1^p = 1</math>, for every pair of digits 1 or −1, their sum is 0 and the sum of their squares is 2. If there are an even number of {1,&nbsp;−1} sets, the number is sad and if there are an odd number, the number 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}} * With odd powers <math>p \equiv 1 \bmod 2</math>, the process of defining numbers reduces down to [[digit sum]] iteration, as <math>{(-1)}^p = -1</math>, <math>0^p = 0</math> and <math>1^p = 1</math>. ==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 [[Cycle detection|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:Arithmetic functions]] [[Category:Base-dependent integer sequences]] [[Category:Number theory]] [[Category:Recreational mathematics]]'