[QUIZ] Happy Numbers (#93)

ruby-talk
41

Peter Hickman 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:

"Unhappy numbers have eventually periodic sequences of s(sub)i which never
reach 1."

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.

···

--
Paul Lutus
http://www.arachnoid.com

42

Please stop it, you are ruining my day, just to be sure, are you seriously
claiming that

   - The universe is not Euclidian?
   - 42 is not a happy number?

Tomorrow you will probably tell me that the world is not a disk!
C'on guys please stay reasonable.

Cheers
Robert

···

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

43

knaveofdiamonds wrote:

One note of advice - the operator to use is actually ** not ^ as might
be expected:

> 7 ^ 2 # Gives 5
> 7 ** 49 # Gives 49

I think you meant 7 ** 2 = 49, whereas
7 ** 49 = 256923577521058878088611477224235621321607

But, since these are integers, we are better off computing n * n,
not n ** 2. There's really no point (in time efficiency) to explicitly
raising n to a power p unless n is not an integer or p is relatively large.

···

--
Paul Lutus
http://www.arachnoid.com

44

Sorry, I should have clarified that a Happy number results in 1, and an
Unhappy number results in an infinite loop.

That's not quite what the cited article says. it says that happy numbers result in an infinite loop on 1 and unhappy numbers result in an infinite loop on the series: 4, 16, 37, 58, 89, 145, 42, 20, 4, ... and that there are no other possibilities.

···

On Sep 1, 2006, at 7:58 AM, Shane Emmons wrote:

On 9/1/06, William Crawford <wccrawford@gmail.com> wrote:

James Gray wrote:
> On Sep 1, 2006, at 8:41 AM, Peter Hickman wrote:
>
>> Doesn't this mean that all numbers are happy?
>
> Here's some further reading for those still confused:
>
> Happy Number -- from Wolfram MathWorld
>
> James Edward Gray II

Wow. Lots of strategy on that page. Almost like cheating :wink:

On a side note... Did anyone NOT calculate 3 by hand? Heh.

--
Posted via http://www.ruby-forum.com/\.

--
--- Shane Emmons <semmons99@gmail.com>

--
Vegetarians eat Vegetables, Humanitarians frighten me

45

One note of advice - the operator to use is actually ** not ^ as might
be expected:

> 7 ^ 2 # Gives 5
> 7 ** 49 # Gives 49

I hope that's not cut & pasted! 7 ** 49 is a little bigger:

ratdog:~ mike$ irb --prompt simple
>> 7 ^ 2
=> 5
>> 7 ** 2
=> 49
>> 7 ** 49
=> 256923577521058878088611477224235621321607

Mike

···

On 1-Sep-06, at 11:00 AM, knaveofdiamonds wrote:

--

Mike Stok <mike@stok.ca>
http://www.stok.ca/~mike/

The "`Stok' disclaimers" apply.

46

Paul Lutus wrote:

Peter Hickman 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.

47

#!/usr/bin/env ruby -w

require "benchmark"

TESTS = 1_000_000
Benchmark.bmbm(10) do |results|
   results.report("Exponent:") { TESTS.times { |n| n ** 2 } }
   results.report("Multiply:") { TESTS.times { |n| n * n } }
end
# >> Rehearsal ---------------------------------------------
# >> 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)

James Edward Gray II

···

On Sep 1, 2006, at 10:40 AM, Paul Lutus wrote:

knaveofdiamonds wrote:

One note of advice - the operator to use is actually ** not ^ as might
be expected:

> 7 ^ 2 # Gives 5
> 7 ** 49 # Gives 49

I think you meant 7 ** 2 = 49, whereas
7 ** 49 = 256923577521058878088611477224235621321607

But, since these are integers, we are better off computing n * n,
not n ** 2. There's really no point (in time efficiency) to explicitly
raising n to a power p unless n is not an integer or p is relatively large.

48

Hans Fugal 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.

49

Hans Fugal 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.)

···

--
Posted via http://www.ruby-forum.com/\.

50

Paul Lutus wrote:
> Peter Hickman 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.

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 :wink:

···

On 9/1/06, Hans Fugal <fugalh@xmission.com> wrote:

51

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 Fugal

···

On 9/1/06, Hans Fugal <fugalh@xmission.com> wrote:

Paul Lutus 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?

52

Hans Fugal 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.

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.

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

···

--
Paul Lutus
http://www.arachnoid.com

53

James Edward Gray II wrote:

/ ...

#!/usr/bin/env ruby -w

require "benchmark"

TESTS = 1_000_000
Benchmark.bmbm(10) do |results|
   results.report("Exponent:") { TESTS.times { |n| n ** 2 } }
   results.report("Multiply:") { TESTS.times { |n| n * n } }
end
# >> Rehearsal ---------------------------------------------
# >> 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.

···

--
Paul Lutus
http://www.arachnoid.com

54

Phrogz wrote:

Hans Fugal 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.

This isn't a math quiz. It's a programming quiz.

55

And here's the "below" referred to (I forgot it earlier). :slight_smile:

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? :slight_smile:

Jacob Fugal

···

On 9/1/06, Jacob Fugal <lukfugl@gmail.com> 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.

56

Jacob Fugal 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?

<mathematical proof proof />

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.

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.

···

On 9/1/06, Hans Fugal <fugalh@xmission.com> wrote:

57

Jacob Fugal wrote:

Paul Lutus 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.

--snip--

Actually, it is possible to show that for any three digit number

g(x) < x.

This holds in any base. The proof:

Let the base be b > 1, and the number x be
x = u + b * v + b^2 * w,
with 0 <= u, v, w < b, and w > 0.
Then

x - g(x) = u + b * v + b^2 * w - (u^2 + v^2 + w^2)
  = u (1 - u) + v * (b - v) + w * (b^2 - w)
  > u (1 - u) + b^2 - 1
  > (b - 1) (2 - b) + b^2 - 1 = 3 * (b - 1) > 0

Regards,

Michael

···

On 9/1/06, Hans Fugal <fugalh@xmission.com> wrote:

--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com

58

James Edward Gray II wrote:

/ ...

> #!/usr/bin/env ruby -w
>

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.

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 :wink:

Cheers

But ... in this case, it is.

···

On 9/1/06, Paul Lutus <nospam@nosite.zzz> wrote:

--
Paul Lutus
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

59

Hans Fugal 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! :slight_smile:

···

--
Paul Lutus
http://www.arachnoid.com

60

Paul Lutus <nospam@nosite.zzz> 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.

···

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1] )
       puts "s=%q(#{s})",s.map{|i|i}[1]