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:
/ âŠ
>> Exponent: 1.370000 0.000000 1.370000 ( 1.372358)
>> Multiply: 1.730000 0.010000 1.740000 ( 1.747647)
>> ------------------------------------ total: 3.110000sec
>>
>> user system total real
>> Exponent: 1.440000 0.000000 1.440000 ( 1.452441)
>> 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.
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
for the reader
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.
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs