# Happy Numbers (#93)

Roland S. wrote:

Sorry, should have been 7 ** 2

Out of interest, any mathmaticians care to enlighten me as to whether
happy numbers are in any way âusefulâ?

Considering this thread and the quiz question, I think maybe a
psychologist
might be a better person to ask.

In my experience, ârealâ mathematicians shudder at the thought that a
result
might prove useful.

Sorry, should have been 7 ** 2

Out of interest, any mathmaticians care to enlighten me as to whether
happy numbers are in any way âusefulâ?

Cheers,
Roland

James Edward G. II wrote:

/ âŠ

# >> Multiply: 1.760000 0.010000 1.770000 ( 1.775988)

One canât argue with results, but this is some kind of language-specific
anomaly if one considers the operations (presumably) taking place behind
the scenes. For arbitrary numbers n,p and the operation n^p,

n^p = e^(log(n)*p)

where âeâ = base of natural logarithms, âlogâ = base e logarithm.

So it seems thereâs at least one multiply no matter what one does. So,
for
n^2, itâs hard to see how n * n could be slower, for either integers or
floats.

But âŠ in this case, it is.

Although others are sure to have better results, I thought Iâd post
mine (no spoilers). I did it a simple way first, and then another more
sophisticated way second. Nice speed improvement.

The below tests 1000 numbers for happiness in 33 different bases.

range = 1âŠ1000
require âBenchmarkâ
Benchmark.bm(20){ |r|
r.report( âTechnique 1â ){
3.upto(36){ |base|
range.select{ |i|
# find out if âiâ is a happy number in the supplied base
}
}
}

r.report( âTechnique 2â ){
3.upto(36){ |base|
range.select{ |i|
# find out if âiâ is a happy number in the supplied base
}
}
}
}

``````                 user     system      total        real
``````

Technique 1 19.282000 0.031000 19.313000 ( 19.359000)
Technique 2 2.140000 0.000000 2.140000 ( 2.156000)

Interestingly, there doesnât seem to be a pattern as to the number of
happy numbers in a given range as the base changes:

(My resultsâŠmight be wrong.
How many Happy numbers between 1âŠ10000?
Base 2: 10000 happy numbers.
Base 3: 1988 happy numbers.
Base 4: 10000 happy numbers.
Base 5: 2571 happy numbers.
Base 6: 645 happy numbers.
Base 7: 162 happy numbers.
Base 8: 549 happy numbers.
Base 9: 627 happy numbers.
Base 10: 1442 happy numbers.
Base 11: 196 happy numbers.
Base 12: 24 happy numbers.
Base 13: 582 happy numbers.
Base 14: 93 happy numbers.
Base 15: 164 happy numbers.
Base 16: 2585 happy numbers.
Base 17: 253 happy numbers.
Base 18: 4154 happy numbers.
Base 19: 3647 happy numbers.
Base 20: 1616 happy numbers.
Base 21: 45 happy numbers.
Base 22: 17 happy numbers.
Base 23: 19 happy numbers.
Base 24: 9 happy numbers.
Base 25: 519 happy numbers.
Base 26: 377 happy numbers.
Base 27: 279 happy numbers.
Base 28: 6 happy numbers.
Base 29: 1730 happy numbers.
Base 30: 5266 happy numbers.
Base 31: 11 happy numbers.
Base 32: 11 happy numbers.
Base 33: 84 happy numbers.
Base 34: 192 happy numbers.
Base 35: 77 happy numbers.
Base 36: 50 happy numbers.

Out of interest, any mathmaticians care to enlighten me as to whether
happy numbers are in any way âusefulâ?

As has been said, âreal mathematiciansâ shudder that their work might be
useful.

In actuality, sometimes things like this arenât, and sometimes they
are years later. Prime numbers never had much use until recent years,
where they have become very important for encryption.

Maybe happy numbers have a useâŠ just no one knows it yet!

Paul L. wrote:

Peter H. wrote:

Problem is that from the quiz it states that you either get a 1 or an
infinite loop and that an unhappy number is âobviousâ. Which is a sign
that something has not been explained clearly. Given that the Wolfram
page was clearer than the quiz at to what constitutes happy donât be
surprised if some people go off down the wrong path.

As I understand the Wolfram article, an unhappy number never hits 1 as a
result, whereas a happy number eventually hits 1:

What you have described here is the halting problem. Good luck with
that.

âUnhappy numbers have eventually periodic sequences of s(sub)i which never
reach 1.â

And what stops it from being a 1x10^50 length period, or any arbitrary
length?

The quiz item emphasizes a criterion that is only mentioned in passing on
the Wolfram page, that is, there are degrees of happiness, and a number
that has many happy predecessors is, umm, more happy. So a relatively large
number that eventually results in 1, but with a lot of steps along the way
(therefore more happy ancestors), is happier.

And what the quiz neglected to mention is that there is an easy test for
unhappy number, which the mathworld page enumerates:

``````Iterating this sum-of-squared-digits map always eventually
reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
or 145 (Sloane's A039943; Porges 1945).
``````

So if you hit one of those unhappy numbers you know youâre in an unhappy
loop.

Hans F. wrote:

And what the quiz neglected to mention is that there is an easy test for
unhappy number, which the mathworld page enumerates:

Iterating this sum-of-squared-digits map always eventually
reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
or 145 (Sloaneâs A039943; Porges 1945).

So if you hit one of those unhappy numbers you know youâre in an unhappy
loop.

IMO, thatâs an unnecessary spoiler (which is why I didnât look at the
Wolfram page). You can figure it out on your own without a âcheat
sheetâ of numbers.

Hans F. wrote:

Iterating this sum-of-squared-digits map always eventually
reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
or 145 (Sloaneâs A039943; Porges 1945).

As long as weâre noting strategy, the site also noted that 16 and 61 are
identical in terms of the next number. Any set of digits can be
scrambled any which way and it wonât matter. 61 will eventually work
around to 16 also. (As shown by the proof of 3, earlier.)

On 9/1/06, Paul L. [email protected] wrote:

where âeâ = base of natural logarithms, âlogâ = base e logarithm.

So it seems thereâs at least one multiply no matter what one does. So, for
n^2, itâs hard to see how n * n could be slower, for either integers or
floats.

I was quite surprised at first too, however, the interpreter knows how
to
treat n ** 2, it does not in a sense know how to treat n * n, it treats
it
as n * m,
replace n with literals in the above tests e.g. 4_710_815 * 4_710_815
and
4_710_815 ** 2 and run the benchmark again,
you will be much happier with the result

Cheers

But âŠ in this case, it is.

â
Paul L.
http://www.arachnoid.com

â
Deux choses sont infinies : lâunivers et la bĂÂȘtise humaine ; en ce qui
concerne lâunivers, je nâen ai pas acquis la certitude absolue.

• Albert Einstein

Phrogz wrote:

IMO, thatâs an unnecessary spoiler (which is why I didnât look at the
Wolfram page). You can figure it out on your own without a âcheat
sheetâ of numbers.

This isnât a math quiz. Itâs a programming quiz.

On 9/1/06, Hans F. [email protected] wrote:

result, whereas a happy number eventually hits 1:

What you have described here is the halting problem. Good luck with that.

Something which reduces to HP is not equivalent to HP, only if you can
reduce HP to this problem is it equivalent to HP/undecidable.

âUnhappy numbers have eventually periodic sequences of s(sub)i which never
reach 1.â

And what stops it from being a 1x10^50 length period, or any arbitrary
length?

Basic math does.
number of length 100 : 99999âŠ, next step = 100*9^2 = 8100, i.e.
large numbers always go down a lot, and therefore cannot be part of
a cycle.
Proving this for n >= 243 (or even smaller n) is left as an exercise

On 9/1/06, Jacob F. [email protected] wrote:

Now, take any i >= 4. For all x in Qi, xâ <= Miâ = 81 * i. But 81 * i
< 10^(i-1) (see below), so 81 * i <= M(i-1), and xâ <= M(i-1) for all
x in Qi. But since x > M(i-1) by our choice, we know that xâ < x. This
is true for all x > 999.

And hereâs the âbelowâ referred to (I forgot it earlier).

Remember that i >= 4. Letâs take i = 4 as a basis case.

81 * 4 = 324 < 1000 = 10^(4-1)

Now, assume the hypothesis for some i >= 4. We will prove the
hypothesis continues to hold for j = i + 1.

Since 1/9 < i; 81 < 9 * 81 * i.
Adding 81 * i to both sides of that inequality we get:
81 * j < 10 * 81 * i

From the other side, we can start with the inequality for i (81 * i <
10^(i-1)) and multiply both sides by 10 to get:
10 * 81 * i < 10^(j-1)

Combining those two inequalities, we have: 81 * j < 10^(j-1).

Isnât induction great?

Jacob F.

On 9/1/06, Hans F. [email protected] wrote:

Paul L. wrote:

âUnhappy numbers have eventually periodic sequences of s(sub)i which never
reach 1.â

And what stops it from being a 1x10^50 length period, or any arbitrary
length?

The period cannot be any larger than 1000. The largest period is
probably quite a bit smaller than this, but this is a upper bound.
Why?

Some definitions, first.

Letâs define g(x) as the function that takes a number to itâs
successor. For example, g(42) = 4^2 + 2^2 = 20.

For a variable x, we will denote the result of applying our function
as xâ. That is, xâ = g(x).

Let Mi = 10^i - 1 for all i. For example, M4 = 9999. Each Mi is the
number made up of i nines. Miâ is then 81 * i.

Let Qi = { x | M(i-1) < x <= Mi }. For example, Q4 is the range of
integers from 1000 to 9999. Itâs easy to see that the union of all
Qiâs cover the natural numbers and that they are all disjoint. So the
set of all Qiâs is a partitioning of the natural numbers.

For each x in Qi, it is easy to see that xâ <= Miâ.

Now, take any i >= 4. For all x in Qi, xâ <= Miâ = 81 * i. But 81 * i
< 10^(i-1) (see below), so 81 * i <= M(i-1), and xâ <= M(i-1) for all
x in Qi. But since x > M(i-1) by our choice, we know that xâ < x. This
is true for all x > 999.

So, for those of you glossing over the math, the conclusion is that
applying the âhappy functionâ to any number greater than or equal to
1000 will necessarily result in a smaller number.

Since the sequence canât loop if weâre constantly decreasing (until we
get down to 999 or less), none of the numbers in a period can be
greater than 999 â thereâs no way to get back up to any of those
numbers.

So, for any loop resulting from a number, the space of numbers liable
to be in that loop is no larger than 1000 number (0 through 999). So
no loop can have a period greater than 1000.

Jacob F.

Jacob F. wrote:

On 9/1/06, Hans F. [email protected] wrote:

And what stops it from being a 1x10^50 length period, or any arbitrary
length?

The period cannot be any larger than 1000. The largest period is
probably quite a bit smaller than this, but this is a upper bound.
Why?

to be in that loop is no larger than 1000 number (0 through 999). So
no loop can have a period greater than 1000.

And that, my friends, is what stops it from being a 1x10^50 length
period, or any arbitrary length.

If the intent of the quiz was to be mathemeticians and figure all this
mathy stuff out, I apologize for dragging it into the open.

Hans F. wrote:

/ âŠ

As I understand the Wolfram article, an unhappy number never hits 1 as a
result, whereas a happy number eventually hits 1:

What you have described here is the halting problem. Good luck with that.

Possibly, I havenât thought it through. I canât find any numbers that
fail
to get to either 1 or 4 in a short time. Doesnât mean they arenât out
there.

âUnhappy numbers have eventually periodic sequences of s(sub)i which
never reach 1.â

And what stops it from being a 1x10^50 length period, or any arbitrary
length?

As the algorithm proceeds, the length of the numbers tends to decline,
until
it reaches one of 0,1, or 4. The first two are dead ends, the third
cycles
a short loop forever, such that it is adequate to detect one of [ 0,1,4
]
as a halting criterion.

reaches one of the 10 numbers 0, 1, 4, 16, 20, 37, 42, 58, 89,
or 145 (Sloaneâs A039943; Porges 1945).

So if you hit one of those unhappy numbers you know youâre in an unhappy
loop.

My relatively unsophisticated program simply loops and halts on reaching
0,1
or 4.

Hans F. wrote:

This isnât a math quiz. Itâs a programming quiz.

Yes, true, but to program efficiently, you need to know at least some of
the
math. Like my earlier expressed notion that n * n computes faster than n
**
2, which appears not to be true in Ruby for God knows what reason.

The example I just gave would seem to argue against understanding the
math
behind a stated problem, but I think itâs true in general. Like the day,
many years ago, when I wrote a program to find even prime numbers. It
ran
for a week and only found one!

Paul L. wrote:

Another example is non-Euclidean geometry, which was an impractical,
exotic
plaything for about 100 years, until general relativity came along and
required it. Without non-Euclidean geometry, Einstein wouldnât have been
able to express GR at all.

Prior to that, few would have guessed that the universe isnât Euclidean.

Wait, are you suggesting that in a hundred years, Happy Numbers could
prove the universe isâŠ Happy?

Matthew M. wrote:

Out of interest, any mathmaticians care to enlighten me as to whether
happy numbers are in any way âusefulâ?

As has been said, âreal mathematiciansâ shudder that their work might be
useful.

In actuality, sometimes things like this arenât, and sometimes they
are years later. Prime numbers never had much use until recent years,
where they have become very important for encryption.

Another example is non-Euclidean geometry, which was an impractical,
exotic
plaything for about 100 years, until general relativity came along and
required it. Without non-Euclidean geometry, Einstein wouldnât have been
able to express GR at all.

Prior to that, few would have guessed that the universe isnât Euclidean.

Paul L. [email protected] writes:

One canât argue with results, but this is some kind of language-specific
anomaly if one considers the operations (presumably) taking place behind
the scenes. For arbitrary numbers n,p and the operation n^p,

n^p = e^(log(n)*p)

Thatâs not the way anyone does exponentiation with integers. Instead,
you represent the exponent as a sum of powers of 2 (which you already
have as its binary representation) and then do something like, e.g.,
this to find n ** 10:

n2 = n * n
n4 = n2 * n2
n8 = n4 * n4
n ** 10 = n8 * n2

Still, n ** 2 does result in a multiplication, but I think that what
weâre seeing is that n * n involves two lookups of the value of the
variable ânâ, whereas n ** 2 involves only one retrieval of n. That
extra lookup operation swamps any of the actual mathematical
operations. This also explains why with a large literal simple
multiplication is faster than doing ** 2.