wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Happy and Sad Numbers
        
(Message started by: Pietro K.C. on Oct 16^th, 2002, 8:04am)

Title: Happy and Sad Numbers
Post by Pietro K.C. on Oct 16^th, 2002, 8:04am

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 k² 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 10^n-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! :P), 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?

Title: Re: Happy and Sad Numbers
Post by James Fingas on Oct 16^th, 2002, 8:36am

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 ;)

Title: Re: Happy and Sad Numbers
Post by wowbagger on Oct 16^th, 2002, 9:28am

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... ;)

Title: Re: Happy and Sad Numbers
Post by James Fingas on Oct 16^th, 2002, 9:51am

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!

Title: Re: Happy and Sad Numbers
Post by Pietro K.C. on Oct 16^th, 2002, 1:05pm

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?

Title: Re: Happy and Sad Numbers
Post by Pietro K.C. on Oct 21^st, 2002, 1:58pm

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?

Title: Re: Happy and Sad Numbers
Post by william wu on Oct 30^th, 2002, 3:17am

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.

Title: Re: Happy and Sad Numbers
Post by Robert Lange on Oct 30^th, 2002, 6:04am

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?

Title: Re: Happy and Sad Numbers
Post by william wu on Oct 30^th, 2002, 9:24am

hrm

http://www.nzamt.org.nz/mathsweek99/activities/7_8/act7_89.html

Title: Re: Happy and Sad Numbers
Post by jakevil on Jan 8^th, 2003, 7:25pm

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

Title: Re: Happy and Sad Numbers
Post by Robert Lange on Jan 10^th, 2003, 7:51am

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 ;D]

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 ;).

Title: Re: Happy and Sad Numbers
Post by Wacky on Jan 11^th, 2003, 4:42am

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 23_five (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!

Title: Re: Happy and Sad Numbers
Post by wowbagger on Jan 13^th, 2003, 5:57am

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 10¹⁰ 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 (http://www.wschnei.de/), by the way.