Velocity Reviews > Ruby > [QUIZ] Happy Numbers (#93)

# [QUIZ] Happy Numbers (#93)

Ken Bloom
Guest
Posts: n/a

 09-05-2006
On Sun, 03 Sep 2006 14:31:09 +0000, Ken Bloom wrote:

> On Fri, 01 Sep 2006 22:01:41 +0900, Ruby Quiz wrote:
>
>> 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
>> 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_ch ar)
> 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

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

Bob Showalter
Guest
Posts: n/a

 09-06-2006
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
Guest
Posts: n/a

 09-06-2006
On 9/4/06, Michael Ulm <(E-Mail Removed)> wrote:
> 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

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
Guest
Posts: n/a

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

On 9/4/06, Michael Ulm <(E-Mail Removed)> 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 Fugal

Matthew Moss
Guest
Posts: n/a

 09-07-2006
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
Guest
Posts: n/a

 09-07-2006
> 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