Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

Relative frequency of happy numbers up to 1e10000

share|improve this question
    
Is it decidable whether or not a positive integer is happy? –  Ricky Demer Oct 16 '11 at 2:55
    
Interesting question. Where did the terminology of happy number come from? –  Spice the Bird Oct 16 '11 at 2:58
    
The orbit of $4$ is not $4\to 16\to 65\to 61\to 37\to\dots$, but $4\to 16\to 37\to\dots$. –  GH from MO Oct 16 '11 at 3:05
    
My apologies. I fixed the error. –  Dave R Oct 16 '11 at 3:19
9  
@Ricky: It is decidable if a positive integer $n$ is happy. Indeed, $s(n)<n$ for $n\geq 1000$, therefore the sequence $n,s(n),s(s(n)),\dots$ contains some $m<1000$ twice which can be found by calculating enough terms of the sequence. If $m=1$ then $n$ is happy, otherwise it is unhappy. –  GH from MO Oct 16 '11 at 3:22
add comment

4 Answers 4

up vote 9 down vote accepted

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.

share|improve this answer
    
I agree that it's implausible that there would be a limiting density. I'm reminded of this question: mathoverflow.net/questions/11255/…. –  Douglas Zare Oct 19 '11 at 5:12
    
Thanks Justin, this is fascinating stuff. I am persuaded that a limiting density cannot exist. –  Dave R Oct 19 '11 at 5:49
    
Then, I wonder: is there a convenient set of hypotheses on a function s: N $\to$ N that guarantees that, for any $a\in$ N, the set {x $\in$ N : $\exists m \in$ N s.t. $s^m(x)=a$ } does have a density? Say, let's keep $s(x) < x$ for large $x$; then, I guess, some condition on the relative density of the fibers $s^{-1}(x)$ vs $s^{-1}(y)$ may be useful; etc. –  Pietro Majer Oct 19 '11 at 19:11
add comment

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.

share|improve this answer
add comment

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$."

share|improve this answer
6  
There is no citation in the Wikipedia reference (Richard Guy's Unsolved Problems in Number Theory, p. 357) indicating how happy numbers may have originated in Russia. I wonder if there is confusion here with a happy ticket, which is a bus or train ticket in Russia for which the sum of the first half of the digits equals the sum of the second half of the digits. See bilet.hdd1.ru/en, where most likely you will see an example of a ticket that is not happy and you can click on Try Again to generate another random ticket number. For 6 digit numbers the chance of a happy ticket is 5.5%. –  KConrad Oct 16 '11 at 5:10
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.