Happy Numbers (#93)

Ruby
61

On 9/4/06, Michael U. [email protected] wrote:

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

Cool, thanks.

I had suspected as much, but didn’t want to try and prove it. The
proof for x >= 1000 (or x >= b ** 3, for arbitrary base) came to me
rather intuitively, so that’s why I chose that one as a loose upper
bound.

Jacob F.

62

WARNING: Just more math geeking ahead. If you don’t care for this
section of the thread, just skim on past… :slight_smile:

On 9/4/06, Michael U. [email protected] wrote:

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

A nitpick, it should be:

u (1 - u) + v * (b - v) + w * (b^2 - w) >= u (1 - u) + b^2 - 1

rather than a strict less than. Doesn’t affect the outcome of the
proof, since the following inequality is still correct. In the case
where v = 0 and w = 1

u (1 - u) + v * (b - v) + w * (b^2 - w)
= u (1 - u) + 0 * (b - 0) + 1 * (b^2 - 1)
= u (1 - u) + b^2 - 1

For those following along at home, it might be hard to see why it must
be less in all other cases – I had a hard time with it for a while.
Imagine v > 0. v * (b - v) > 0 since b > v. So that term can only make
the expression larger.

Also imagine w > 1.

w * (b^2 - w)
= w * b^2 - w^2
= b^2 + (w - 2) * b^2 + b^2 - w^2
= b^2 + (w - 2) * b^2 + (b - w) (b + w)

Since b > w, b - w > 0. Also, b + w > b >= 2. So (b - w) (b + w) >= 2 >
1:

w * (b^2 - w) > b^2 + 1 + (w - 2) * b^2

Now since w >= 2, (w - 2) * b^2 >= 0, and we have:

w * (b^2 - w) > b^2 + 1

And that term can only increase as well. So as Michael showed, g(x) <
x for all x with three or more digits in the respective base.

Jacob F.

63

My bit o’ solution… only had a few minutes to do a few lines, it’s
about as small and compact as I can get a happy test without golfing
it:

class Integer
def happy?
return false if zero?
return false if (self ^ 4).zero?
return true if (self ^ 1).zero?
to_s.split(//).inject(0) { |s,x| s + (x.to_i ** 2) }.happy?
end
end

64 
  return false if (self ^ 4).zero?
  return true  if (self ^ 1).zero?

Okay, these two lines were silly; replace with:

return false if self == 4
return true if self == 1

65

Jacob F. wrote:

x - g(x) = u + b * v + b^2 * w - (u^2 + v^2 + w^2)
proof, since the following inequality is still correct. In the case
where v = 0 and w = 1
–snip more explanations–

You are right, thanks for the correction and explanations.

Some other simple facts:

If x is a two-digit number in base b then g(x) < 2 * b^2,
so if g(x) is a three-digit number in base b, the most
significant digit is always one. This also means that all
cycles in base b consist of numbers less than 2 * b^2.

No odd number b is a happy base, because the number
x = (b + 1)**2 / 2 is a fixed point of g; i.e.
g(x) = x.

The only happy bases < 700 are 2 and 4.

To get more on topic for this list, I have attached a ruby
script that computes all cycles for any given base.

Regards,

Michael

–
Michael U.
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: [email protected]
Visit our Website: www.isis-papyrus.com