Does the set of happy numbers have a limiting density? - MathOverflow

Does the set of happy numbers have a limiting density?

2011-10-16T02:49:35Z

A positive integer $n$ is said to be happy if the sequence $$n, s(n), s(s(n)), s(s(s(n))), \ldots$$ eventually reaches 1, where $s(n)$ denotes the sum of the squared digits of $n$.

For example, 7 is happy because the orbit of 7 under this mapping reaches 1. $$7 \to 49 \to 97 \to 130 \to 10 \to 1$$ But 4 is not happy, because the orbit of 4 is an infinite loop that does not contain 1. $$4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4 \to \ldots$$

I have tabulated the happy numbers up to $10^{10000}$, and it appears that they have a limiting density, although the rate of convergence is slow. Is it known if the happy numbers do in fact have a limiting density? In other words, does $\lim_{n\to\infty} h(n)/n$ exist, where $h(n)$ denotes the number of happy numbers less than $n$?

Answer by Joe Silverman for Does the set of happy numbers have a limiting density?

2011-10-16T03:31:30Z

Helen Grundman has a written a number of articles about happy numbers. (I first heard of them at a talk of hers at a JMM.) References for her articles are listed below. I don't know if they discuss densities. One can also look at happy numbers to other bases, of course. According to Wikipedia: "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'."

To answer Ricky Demer's question, yes, it's easily decidable, since if $N$ is large enough, then it's easy to see that $s(N)$ is a lot smaller than $N$. More precisely, $s(N)\le 81*\lceil\log_{10}(N)\rceil$. So one rapidly gets into and remains within a bounded range, after which one can check if the sequence cycles at 1, or in some other way.

MR2382633 (2008m:11020) Grundman, H. G. ; Teeple, E. A. Sequences of consecutive happy numbers. Rocky Mountain J. Math. 37 (2007), no. 6, 1905--1916.
MR2285991 (2007i:11016) Grundman, H. G. ; Teeple, E. A. Sequences of generalized happy numbers with small bases. J. Integer Seq. 10 (2007), no. 1, Article 07.1.8, 6 pp. (electronic).
MR2022409 Grundman, H. G. ; Teeple, E. A. Heights of happy numbers and cubic happy numbers. Fibonacci Quart. 41 (2003), no. 4, 301--306.
MR1866364 (2002h:11010) Grundman, H. G. ; Teeple, E. A. Generalized happy numbers. Fibonacci Quart. 39 (2001), no. 5, 462--466.

Added 18 October 2011: A relevant ArXiv post just appeared: On the Density of Happy Numbers, Justin Gilmer, http://arxiv.org/abs/1110.3836. The author proves that "happy numbers have upper density $\geq .18$ and lower density $\leq .12$."

Answer by Gerry Myerson for Does the set of happy numbers have a limiting density?

2011-10-16T03:34:09Z

Guy, Unsolved Problems In Number Theory, 3rd edition, problem E34, writes, "It seems that about 1/7 of all numbers are happy, but what bounds on the density can be proved?" He doesn't give an answer, so I suppose nothing was known as of the publication of the book. Helen Grundman has written several papers on happy numbers, maybe you could ask her.

Answer by Justin Gilmer for Does the set of happy numbers have a limiting density?

2011-10-19T04:56:23Z

The answer is almost certainly that the limiting density does not exist. Without going into the details of the proof allow me to give a heuristic argument which is based on how the OP likely generated his graph of the relative frequency of happy numbers.

Let $Y_n$ be the r.v. uniformly distributed amongst integers in the interval $[0,10^n -1]$ (that is $Y_n$ picks a random $n$-digit integer). If $X_i$ denotes the r.v. for the digit of $10^i$ in $Y_n$, then $s(Y_n) = \sum\limits_{i=0}^{n-1} s(X_i)$.

I'm guessing the way you generated your graph was you first computed the distribution of $s(Y_n)$ (this can be done recursively) then computed $\mathbb{P}\big(s(Y_n) \text{ is happy}\big)$. This would give the relative density of happy numbers amongst all $n$ digit integers.

Studying the distribution of $s(Y_n)$ can tell us a lot. Its equivalent to rolling $n$ times a 10-sided die with faces $0,1,4,\dots, 81$ and finding the sum. Its distribution is Gaussian as $n$ gets large by the central limit theorem. More importantly most of the distribution is concentrated near the mean, which is $28.5n$. This implies that the density happy numbers amongst all $n$-digit integers depends almost entirely on the distribution of happy numbers near $28.5n$.

For example, there is a peak in your graph at around $n = 400$ of about $.185$ density. Calculating the density of happy numbers within one standard deviation from the mean of $s(Y_{400})$ we get a density of .1911 (the interval I looked at was $[10916,11884]$). If you assume $s(Y_{400})$ is "exactly" normally distributed and estimated the density in this manner you would get a much better approximation.

This means picking $n$ s.t. the mean of $s(Y_n)$ lands in the interval $[10^{400},10^{401}-1]$ then the density of happy numbers amongst $n$-digit integers should be around $.185$. Likely some choices of $n$ will give densities strictly larger than $.185$ and some strictly smaller. This has led me to suspect that by iterating this process, the upper density of happy numbers may be $1$, and lower density $0$.

The article Joe Silverman mentioned is my own. In it I attempt to give the above heuristic a rigorous foundation. It is still a rough draft and has only been reviewed by one of my fellow graduate students, so I won't to say it is definitely correct, although I am very confident it is. I have been working on it for the past few weeks, seeing your question on MO I decided to go ahead and upload a rough draft. In it I use an averaging argument to say that if you find experimentally a large interval of $n$-digit integers ($n$ sufficiently large) which contain happy numbers with density $d$, then the upper density of happy numbers is at least $d(1 - o(1))$. That is where the upper density $\geq .18$ and lower density $ \leq .12$ comes from.

Answer by David Moews for Does the set of happy numbers have a limiting density?

2011-11-10T22:55:56Z

I started working on this question after it was posted to MathOverflow and found bounds similar to those found by Justin Gilmer: upper asymptotic density of the happy numbers 0.1962 or greater, lower asymptotic density no more than 0.1217. However, I was also able to prove that the upper asymptotic density of the happy numbers was no more than 0.38; Gilmer mentioned in his paper that the question of whether the upper asymptotic density was less than 1 was still open.

A writeup of the result is at http://djm.cc/dmoews/happy.zip. The method used to find an upper bound on the upper asymptotic density was to start with a random number with decimal expansion $??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, where the digits # are independent and uniformly distributed, and the digits ? are arbitrarily distributed and may depend on each other, but are independent of the #s. Then if there are $n$ #s, asymptotic normality implies that after applying $s$, we get a mixture of translates of a distribution which is approximately normal, with mean $28.5n$ and standard deviation proportional to $\sqrt{n}$. If $10^{n'}/\sqrt{n}$ is sufficiently small, each translate of this normal distribution will have its last $n'$ digits approximately uniformly distributed, so we get a random number which can be approximated by the same form of decimal expansion we started with, $??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, where now there are $n'$ digits #. Repeating this eventually brings us to numbers small enough to fit on a computer.

The method used to find the bounds similar to Gilmer's was to start with a random number of the form $dd\dots{}dd??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, where the ?s and #s are as before, the $d$s are fixed digits, and there are the same number of $d$s and #s, but very few ?s. Then if the parameters are appropriately chosen, we can show that after applying $s$, we again get a random number which can be approximated by the same form of decimal expansion, $dd\dots{}dd??\dots{}??\hbox{#}\hbox{#}\dots{}\hbox{#}\hbox{#}$, and repeat this step until the number is small.