[QUIZ] Happy Numbers (#93)

[Ken Bloom]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Shane Emmons

Write a program that tells whether a given integer is happy. A happy number is
found using the following process: Take the sum of the squares of its digits,
and continue iterating this process until it yields 1, or produces an infinite
loop.

For example the number 7:

7^2 = 49
4^2 + 9^2 = 97
9^2 + 7^2 = 130
1^2 + 3^2 + 0^2 = 10
1^2 + 0^2 = 1

If a number is not happy than it is obviously unhappy. Now that you have this
program, what is the largest happy number you can find? What is the happiest
number between 1 and 1,000,000. I define the happiest number as the smallest
number that finds the most other happy numbers with it, i.e. 7 found four other
numbers (49, 97, 130, and 10) making it a rank 4 in happiness.

If you find all these examples trivial, write you program so that it will find
happy numbers in other bases such as base 2 or 16. From there you can extend the
program so that it finds happy bases (other than 2 and 4). A happy bases is a
base where all numbers are happy. Good luck.

require 'enumerator'
require 'jcode'


module Happy
#1 is a success terminator, from Wolfram's MathWorld
FAIL_TERMINATORS=[0, 4, 16, 20, 37, 42, 58, 89, 145]

def internal_happy? number
return 0 if number==1
return false if FAIL_TERMINATORS.include? number
it=Enumerable::Enumerator.new(number.to_s,:each_char)
newnumber=it.inject(0) { |partial_sum,char| partial_sum+(char.to_i)**2 }
x=happy?(newnumber)
return x+1 if x
return false
end

@@memo=Hash.new

def happy? number
return @@memo[number] || @@memo[number]=internal_happy?(number)
end
end

include Happy

#there is no largest happy number because any 10**n is happy for any n.
#since ruby can represent all integers, there's no "largest number I can
#find" (given enough RAM)

#to find the happiest number between 1 and 1_000_000, we use the
#following code (which takes advantage of the memoization that I have
#included)

minhappy=[]
1_000_001.times do |n|
puts "Progress #{n}" if n%1000==0
if x=happy?(n)
if minhappy[x]==nil or minhappy[x]>n
minhappy[x]=n
end
end
end

puts minhappy.last

#after a long time running, this prints that
#the happiest number is 78999

#by clearing the memoization hash and adding a strategically placed
#puts, I can see this computes happiness for the following
#numbers: [78999, 356, 70, 49, 97, 130, 10, 1]

--Ken Bloom

Since the order of digits in the number doesn't matter, here's code to
generate digits whose numbers are in nondecreasing order. This makes the
"happiest number" test finish almost instantly when the numbers are
generated this way:

#generates all numbers in the given range whose digits are in
#nondecreasing order. the order in which the numbers are generated is
#undefined, so it's possible for 123 to appear before 23, for
#example.
def nondec_digits(range,&b)
yield 0 if range.first<=0
(1..9).each { |x| noninc_digits_internal(x,x,range,&b) }
end

def nondec_digits_internal(last,accum,range,&b)
(last..9).each do |x|
iaccum=accum*10+x
b.call(iaccum) if range.include?(iaccum)
noninc_digits_internal(x,iaccum,range,&b) if iaccum<=range.last
end
end

 

[Bob Showalter]

I'm just posting my happy? method since it's a little different from
the others. I opted for a recursive solution that records its results
as it goes. I set the cache value to false before recursing; if the
number winds up being happy, the true values are set as the recursion
unwinds.

class Integer

# cache of happy true/false by number
@@happy = Hash.new

# sum of squares of digits
def sosqod
sum = 0
self.to_s.each_byte { |d| d -= ?0; sum += d * d }
sum
end

# am I a happy number?
def happy?
return true if self == 1
return @@happy[self] if @@happy.include?(self)
@@happy[self] = false
@@happy[self] = self.sosqod.happy?
end

end

 

[Jacob Fugal]

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)

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 Fugal

 

[Jacob Fugal]

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

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)

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 Fugal

 

[Matthew Moss]

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

 

[Matthew Moss]

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