Author |
Topic: Happy and Sad Numbers (Read 10681 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Happy and Sad Numbers
« on: Oct 16th, 2002, 8:04am » |
 Quote  Modify
|
OK, this one is driving me insane. I don't think there exists a closed-from expression for happy or sad numbers. All I've managed to notice so far is that happy numbers are far less numerous than sad ones. Between 1 and 170, there are only about 20 happy numbers, 30 tops.
One other result is that, if a number is happy, then the penultimate number of the sequence of transformations (i.e. the one reached right before 1) must be a power of 10. This is pretty obvious, as the sum of integer squares can only be 1 if one of the integers is 1 and the others are 0.
However, you can construct an infinite number of numbers that are transformed to a given number! OK, maybe that wasn't clear. Consider the number 13, which is happy. The number 1111111111111 will transform to it, and hence be happy. If you take away k2 of the ones and replace them with a k, in any order, that number will also be happy. However, if you take a huge number made up of 1111111111111 consecutive ones, that will also be happy. And the numbers built from that one with the above replacements.
Similar remarks apply to sad numbers. Needless to say, a number is happy if and only if it transforms to a happy number.
Other results: because of the nature of the transformation, which in general greatly diminishes the number it is applied to (for a number of n digits, i.e. greater than 10n-1, it returns at most 81n), there can only be a finite number of loops. Further, these loops will involve numbers of at most 3 digits. By brute-force checking (by hand!  ), I'm almost sure there is in fact only one loop, that which "begins" with 4:
4, 16, 37, 58, 89, 145, 42, 20, 4.
Consider the integers to be vertices of an infinite graph and suppose there is a directed edge a->b if b transforms to a (yes, direction reversed). Then "loop" has the same meaning in both contexts. It is clear that happy numbers cannot form loops, so the structure of the happy numbers is that of a tree with root at 1. The structure of sad numbers is similar: each vertex in the (single?) loop is the root of an infinite tree.
As I said, this is driving me mad. Because of the considerations in the third paragraph, I fail to see how a closed-form formula would be. Your thoughts?
|
|
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Happy and Sad Numbers
« Reply #1 on: Oct 16th, 2002, 8:36am » |
Quote Modify
|
Pietro,
I agree that there is only one loop. This is pretty easy to prove--just brute-force your way up to 162, and then prove that all numbers eventually cycle below 162, and stay there.
As for a closed-form expression, I also doubt it. The easiest way of deciding whether or not a number is happy or sad is undoubtedly just to do the transformation given, then wait until the number is 1 or 4. It is practically a constant-time operation (faster than O(log log log log ... log n) for any number of logs).
Here's something interesting, however: consider the small happy numbers (less than 162). The following are congruent to 1 (mod 3):
1, 7, 10, 13, 19, 28, 31, 49, 70, 79, 82, 91, 94, 97, 100, 103, 109, 130, 133, 139
These are congruent to 2 (mod 3):
23, 32, 44, 68, 86
These are congruent to 0 (mod 3):
129
This seems a little lop-sided! Could this just be coincidence?(ala strong law of small numbers). If you try the same thing, but cubing the digits, then you get just a few happy numbers, but more than a single sad number cycle, and which cycle a number ends up in is strongly dependent on its value mod 3 (again, for small n--is this a general rule?)
And of course, the question "are any numbers with a digit 5 happy?"--obviously there are a few. The smallest one is 356, closely followed by 365 -- the number of days in a regular calendar year! -- another coincidence? Yeah, probably 
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Happy and Sad Numbers
« Reply #2 on: Oct 16th, 2002, 9:28am » |
Quote Modify
|
I extended James' analysis (mod 3) for integers up to 10000, 1442 of which are happy. Among these the following numbers of integers have a remainder of r when divided by 3:
r: 0 1 2
392 523 537
For other divisors I couldn't find any absolutely convincing imbalance either. The most lopsided distribution of remainders is the result of mod 9:
r: 0 1 2 3 4 5 6 7 8
156 221 101 178 94 228 58 208 198
In view of this, I don't think congruence classes can lead us to a closed-form expression.
Even if you only consider small integers: How are they supposed to help us with the large ones?
The extension of adding the p-th power of the digits looks interesting to me. Maybe there's some scaling law for the fraction of p-happy numbers? But I really don't have the time now for stuff like that...
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Happy and Sad Numbers
« Reply #3 on: Oct 16th, 2002, 9:51am » |
Quote Modify
|
Wowbagger,
Yeah, I came to the conclusion that it was just a coincidence too. The coincidence is helped by the fact that permutation of the digits produces more happy numbers, and also preserves the congruence mod 3. The bunch of happy numbers with 1s in them (1, 13, 19 and their permutations) account for a lot of these, and the others--I guess they're just a happy coincidence!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Happy and Sad Numbers
« Reply #4 on: Oct 16th, 2002, 1:05pm » |
Quote Modify
|
I'm not placing much hope in those congruence classes either... this problem is too specific. If we changed from base 10 to any other base, the results would be totally different, I think. For instance, in base 2 EVERY number is happy.
Anyway, I'm so pissed at this unyielding problem that I've stooped to using a computer.  I've discovered that, for some weird reason, the density of happy numbers is around 1/7. Yes, as n gets large, about n/7 numbers below n are happy! Here are some values of the proportion, i.e. n/happy(n):
n=100 : 5.0000000
n=1000 : 6.9930072
n=10000 : 6.9348125
n=100000 : 6.9555540
n=1000000 : 6.9895368
n=10000000 : 7.0479417
n=500000000 : 7.0328178
n=1000000000 : 6.8646049
Though I suspect the last one is prone to roundoff errors. It took the computer around 30 minutes to come up with it.
Well?
|
| « Last Edit: Oct 16th, 2002, 2:23pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Happy and Sad Numbers
« Reply #5 on: Oct 21st, 2002, 1:58pm » |
Quote Modify
|
Just to complete the above table, the density of happy numbers below 2,147,483,647 is one in every 6.8755331... so maybe the density isn't really approaching 1/7, but it sure seems to be approaching something.
And, on second thought, I don't think there are roundoff errors, as only one division is performed, and there is no error propagation.
Has ANYONE made ANY progress?
|
| « Last Edit: Oct 21st, 2002, 1:59pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: Happy and Sad Numbers
« Reply #6 on: Oct 30th, 2002, 3:17am » |
Quote Modify
|
The contributor, Robert Lange, said this was a kind of game he and his peers used to play in grade school. They invented the idea of happy and sad numbers on a whim, and just kept playing with the concept, trying to figure out in general what kinds of numbers were happy or sad. So he posed the question to our site. Robert and his peers made some of the observations you guys have made, but they also were unable to find closed-form expressions for happy and sad numbers. If there's a special solution out there, none of us know about it yet. This information will either make you more excited about the problem, or decide there's no solution. Maybe I should have revealed this beforehand to avoid unnecessary (?) agony, but such information might have stifled progress that otherwise would have never flowered. Hmm. In any case, I apologize if you would have preferred that I disclosed these facts beforehand.
|
| « Last Edit: Oct 30th, 2002, 3:18am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Robert Lange
Guest
|
|
Re: Happy and Sad Numbers
« Reply #7 on: Oct 30th, 2002, 6:04am » |
Quote Modify
 Remove
|
I can't actually claim credit for the concept - happy and sad numbers were not my creation (new puzzle: find the inventor?), they were merely something fun to play with. I think any 'solution' will come down to knowing what branch of number theory to use. Has anyone examined powers greater than 2?
|
|
IP Logged |
|
|
|
jakevil
Newbie
Gender:
Posts: 2
|
|
Re: Happy and Sad Numbers
« Reply #9 on: Jan 8th, 2003, 7:25pm » |
Quote Modify
|
Greetings
I don't have much to offer on this (yet), but I figured that in case there was someone out there who wanted to look at a bunch of happy numbers for whatever reason (like I did) but didn't know how to write programs (I don't), that they might benefit from my labor:
http://www.jakevil.com/docs/happy.csv
Unfortunately, not being a programmer, the best way I could figure out how to do this was with Excel, which limits you to about 65000 lines (rounded to the nearest power of 2). So the above file contains all the "happy" numbers up to 65527, along with their tranformation into happiness, so to speak (e.g.the line for "31" would read "31, 10, 1".
Anyhow.. I was hoping this might help somebody. I've been reading for a while, but haven't posted anything before now, though I was tempted to butt into the ".99999... <=> 1" thread.
Regards
jake
|
|
IP Logged |
|
|
|
Robert Lange
Guest
|
|
Re: Happy and Sad Numbers
« Reply #10 on: Jan 10th, 2003, 7:51am » |
Quote Modify
Remove
|
Jake, if you want to play with these numbers it might be worth learning to program, say in the vb part within excel - it's not that much harder than the formulae you must have used to get to your spreadsheet (unless you did them all by hand ).
You can then have all kinds of fun with these numbers and start examining higher powers (cube the digits instead etc).
[new puzzle: determine a dna formula that identifies the weird and eccentric people who enjoy puzzles and numbers  ]
Alternatively you can save space in various ways such as eliminating duplicates (e.g. happy 111239 is the same as 932111).
PS If you want to know about .999... and 1 then ask a turing machine or Bertrand Russell .
|
|
IP Logged |
|
|
|
Wacky
Newbie
Posts: 6
|
|
Re: Happy and Sad Numbers
« Reply #11 on: Jan 11th, 2003, 4:42am » |
Quote Modify
|
Whoever the inventor of Happy and Sad numbers is, he's quite old. I have a Sept/Oct 1974 article on the topic by a W. Moore M.C.A.E. (whatever that means). It doesn't actually have any much information except calling the operation "ZAP" denoted with Z_, and mentioning that
Quote:
HAPPINESS IS BASE DEPENDENT
This means that happiness depends on the numeration system unlike the properties of primeness or evenness since these are the properties of the number itself and not the numeral.
A remarkable and very important difference.
A whole new area is opened up; happiness in other bases, self generation numbers like 23five (are there any others in base five? base 6? base 7? etc?) zapping to higher powers (e.g. cubed, fourth power, etc).
......
Questions:
Can you find any consecutive happy numbers? These are called lovers.
Do you know of any number that is happy in any base?
Find a base that makes all numbers happy.
Link some of the happy numbers together in a network. (Note: this is called a tree. Why?)
|
|
Hope that helped!
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Happy and Sad Numbers
« Reply #12 on: Jan 13th, 2003, 5:57am » |
Quote Modify
|
Let me refer you to http://www.wschnei.de/digit-related-numbers/happy-numbers.html where you can find results of a computer search up to 1010 along with tables of the fixed points and cycles of the generating procedure for exponents 2 and 3 and bases 2 to 10 inclusive.
There is much more information on number theory-related fun to be found on the corresponding home page, by the way.
|
| « Last Edit: Jan 13th, 2003, 6:01am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print