[QUIZ] Happy Numbers (#93)

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.

James Gray wrote:

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.

-Boggles-

Okay, I'm feeling stupid here. What MAKES that number be happy? The
nearest I can find is that if it's an infinite loop, it isn't happy. If
it's not a loop, and resolves to 1 eventually. (It has to resolve to 1,
or it's be a loop.) It's happy.

Is that right?

···

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

Now that you have this program, what is the largest happy number you can find?

(10 ** N) where N is anything. You name N, I'll say N+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?

Clearly, there is no largest happy number. Any number of the form 10**n in base b is b-relative happy (with rank 1). I feel this makes the stated question an ill-conditioned one.

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.

This seems a better question to pursue than the first. Other questions one might explore: how does rank vary as the numbers increase? Does maximum rank grow as happy numbers get bigger? Is there a pattern? Are there interesting statistics?

Regards, Morton

···

On Sep 1, 2006, at 9:01 AM, Ruby Quiz wrote:

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?

Clearly, there is no largest happy number. Any number of the form 10**n in base b is b-relative happy (with rank 1). I feel this makes the stated question an ill-conditioned one.

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.

This seems a better question to pursue than the first. Other questions one might explore: how does rank vary as the numbers increase? Does maximum rank grow as happy numbers get bigger? Is there a pattern? Are there interesting statistics?

Regards, Morton

···

On Sep 1, 2006, at 9:01 AM, Ruby Quiz wrote:

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

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)

Here's my solution. Writing a method that can determine whether a number is
happy, and how happy it is, is fairly simple. Once the method exists, it's
fairly trivial to write short programs that use the method to determine the
happiness of a number, or to find the highest happy number or the happiest
number in a range, as requested by the quiz. But the Ruby Quiz generally
requests that you write a program, not a single method, so I decided to write a
program that can perform all of these tasks, depending on the input parameter.
And handle bases other than ten if desired, to boot.

Once I decided to do that, it made sense to optimize the method over multiple
runs, by memoizing results, and taking algorithmic shortcuts based on previously
memoized results. So my get_happy method is a bit more complicated than it was
originally, due to the optimizations.

Of course, once I added optimizations, I introduced bugs. They were subtle and a
bit tricky to track down. But they basically boiled down to this question: Is 1
a happy number, and if so, how happy? It's obvious that when you perform one
iteration of the happiness algorithm, the next number in the sequence has a
happiness value of one less than the current number. For example, take the
sequence used in the quiz description. It starts with 7, which is finally stated
to have a happiness value of 4. The remaining numbers in the sequence, 49, 97,
130, and 10, thus have happiness values of 3, 2, 1, and 0 respectively.

So, is 1 happy? If the definition of a happy number is that the algorithm
evenually reaches 1, then yes it is. What is its happiness value? It could
arguably be 0, because the algorithm goes to 1 right away, without generating
any other happy numbers. But, any number with a happiness value of 0, such as
10, has 1 as its next iterated value, which means that, according to the
paragraph above, 1 should have a happiness value of 1 less than 0, which would
be -1. So is 1's happiness value 0 or -1?

I guess it's an arbitrary choice. But until I realized what was going on, I had
a bug in which a number's happiness value would either be correct, or 1 higher
than correct, depending on whether or not it was being calculated based on a
previous memoized intermediate value. I had originally set 1's happiness value
to 0, but this caused 10's value to be calculated as 1 instead of 0, because it
was 1 higher than the happiness value of the next number in the sequence, which
was of course 1, whose happiness is 0. This happened only when 10's happiness
value was memoized during another number's sequence, but not when 10 itself had
been passed into the get_happy method. Then I naively changed 1's happiness
value to -1, to try to fix this. But this didn't work either, since -1 is my
magic value meaning "unhappy", so all numbers were determined to be unhappy
since 1's memoized value returned as -1 in the first optimization. So I changed
1's happiness value back to 0, and unconditionally decreased all numbers'
happiness values by 1, which also turned out to be wrong.

When I finally understood what was going on, I realized that the correct fix was
to add the "(temp != 1)" conditional in the first "if" statement, and the "ret
-= 1" line if the algorithm has iterated all the way to 1. At this point, 1's
happiness value isn't actually used in the algorithm for computing any other
number's happiness. It's only ever used if get_happy is called on the value 1
itself. And at last, the program works! (At least, I'm pretty sure it does :slight_smile: )

#!/usr/bin/env ruby

···

#
# =Description
#
# This program determines the happiness of a number, or the happiest number and
# highest happy number in a range of numbers.
#
# A number's happiness is determined as follows: Sum the squares of the number's
# individual digits. Repeat this process with the result, until a value of 1 is
# reached, or until a value is repeated, thus indicating a loop that will never
# reach 1. A number for which 1 is reached is "happy". The number of other
# numbers generated besides 1 and the original number is its happiness value.
#
# =Usage
#
# happy.rb num1[-num2][:base]
#
# happy.rb takes a single argument. If the argument is a single number, that
# number's happiness value is displayed, or the number is said to be unhappy.
# If the argument is a range of numbers, such as "1-400", the happiness value of
# the happiest number (lowest number breaking ties) in that range is returned.
# If the argument ends with a colon and a number, such as "50:8" or "1-100:2",
# the number after the colon specifies the base of the first number(s). An
# unspecified base implies base ten.

require 'rdoc/usage'

#==============================================================================
# ----- Global variables -----
#==============================================================================

$hap_map = {} # Hash for memoization of happiness values

#==============================================================================
# ----- Instance methods -----
#==============================================================================
class String
  # Indicates whether the string is a valid number of the specified base.
  def is_num_of_base?(base)
    # sub() call removes leading zeros for comparison
    self.sub(/\A0+/, '').downcase == self.to_i(base).to_s(base).downcase
  end
end

class Integer
  # Pretty-print string including base, if base is not 10
  def pretty(base)
    self.to_s(base) + ((base == 10) ? "" : " (base #{base})")
  end
end

#==============================================================================
# ----- Global methods -----
#==============================================================================

# This method returns the happiness value of the given number. A value of -1
# indicates that the number is unhappy.
def get_happy(num, base=10)
  $hap_map[num] = 0 if num == 1 # Handles trivial case
  return $hap_map[num] if $hap_map[num]

  ret = 0
  done = false
  inters = []
  temp = num
  
  until done
    digits = temp.to_s(base).split(//).map{|c| c.to_i(base)}
    temp = digits.inject(0) {|sum, d| sum + d**2}
    ret += 1

    if (temp != 1) && $hap_map[temp]
      # Optimization; use knowledge stored in $hap_map
      if $hap_map[temp] == -1
        ret = -1
        done = true
      else
        ret += $hap_map[temp]
        done = true
      end
    else
      if temp == 1
        ret -= 1 # Don't count 1 as an intermediate happy number
        done = true
      elsif inters.include?(temp)
        ret = -1
        done = true
      else
        inters << temp
      end
    end
  end

  $hap_map[num] = ret

  # Optimization
  if ret == -1
    # If num is not happy, none of the intermediates are happy either
    inters.each {|n| $hap_map[n] = -1}
  else
    # If num is happy, each intermediate has a happiness value determined by
    # its position in the array
    inters.each_index {|idx| $hap_map[inters[idx]] = (ret - 1) - idx}
  end

  return ret
end

# nums is a range of integers. This method returns two values: the happiest
# number, and the highest happy number, in the range. Two nil values will be
# returned if there are no happy numbers in the range.
def get_superlatives(nums, base)
  happiest_num = nil
  happiest_ness = nil
  highest = nil

  nums.each do |n|
    happy = get_happy(n, base)
    next if happy == -1
    highest = n

    if (!happiest_ness) || (happy > happiest_ness)
      happiest_num = n
      happiest_ness = happy
    end
  end

  return happiest_num, highest
end

#==============================================================================
# ----- Script start -----
#==============================================================================

if ARGV.size != 1
  RDoc.usage('Usage', 'Description')
end

# Parse arg
ARGV[0] =~ /\A([\d\w]+)(?:\-([\d\w]+))?(?::(\d+))?\Z/
num1, num2, base = $1, $2, $3

# Ensure legal arg
RDoc.usage('Usage', 'Description') unless num1

# Fill in defaults
base = 10 unless base
num2 = num1 unless num2

# Convert numbers from strings to numeric values
base = base.to_i

[num1, num2].each do |s|
  unless s.is_num_of_base?(base)
    puts "Error: #{s} is not a valid base #{base} number"
    exit
  end
end

num1 = num1.to_i(base)
num2 = num2.to_i(base)

# Calculate and print results
if num1 == num2
  happiness = get_happy(num1, base)
  
  print num1.pretty(base)
  
  if happiness == -1
    print " is not happy.\n"
  else
    print " has a happiness of #{happiness}\n"
  end
else
  if num1 > num2
    num1, num2 = num2, num1
  end

  happiest, highest = get_superlatives((num1..num2), base)

  if !highest
    puts "None of those numbers are happy."
  else
    puts "The happiest number is " + happiest.pretty(base) +
      ", with a happiness of #{get_happy(happiest, base)}"

    puts "The highest happy number is " + highest.pretty(base) +
      ", with a happiness of #{get_happy(highest, base)}"
  end
end

--
Karl von Laudermann - karlvonl(a)rcn.com - http://www.geocities.com/~karlvonl
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?" ":"@@");puts if x==w-1;}}

Here are my two solutions. Both take arbitrary bases. Neither counts
the number of steps between a number and its happiness. The hash-based
one is based on the auto-memoizing idea previously discussed on this
list for a speedy fibonacci calculation.

The core of both calculations is calculating the next happy step via:
num.to_s(base).split('').map{ |c| c.to_i(base)**2 }.inject{ |s,i| s+i }

class Integer
@@happysteps = Hash.new{ |k,v| k[v] = {} }
def happy?( base=10 )
  seen = {}
  num = self
  until num==1 or seen[ num ]
   seen[ num ] = true
   num = num.to_s(base).split('').map{ |c| c.to_i(base)**2 }.inject{

s,i| s+i }

  end
  num == 1
end
end

happy = Hash.new{ |h1,base|
h1[ base ] = Hash.new{ |h2, n|
  if n == 1
   h2[ 1 ] = true
  else
   h2[ n ] = :not_happy
   sum_of_squares = n.to_s(base).split('').map{ |c| c.to_i(base)**2
}.inject{ |s,i| s+i }
   if sum_of_squares == 1
    h2[ n ] = true
   else
    subn = h2[ sum_of_squares ]
    if subn == true
     h2[ n ] = true
    elsif subn == false || subn == :not_happy
     h2[ n ] = h2[ sum_of_squares ] = false
    end
   end
  end
}
}

range = 1..1000
puts "How many Happy numbers between #{range}?"
3.upto(36){ |base|
puts "Base #{base}: #{range.select{|i| happy[ base ][ i ] }.length}
happy numbers."
puts "Base #{base}: #{range.select{|i| i.happy?( base ) }.length}
happy numbers."
}

Attached is my solution (shiawase_kazu_keikaku.rb and also available
at http://www.makenai.net/tmp/shiawase_kazu_keikaku.rb ):

It's definitely not going to win any speed contests, but I'm happy
enough that it's short and fairly readable. I didn't try to
over-optimize - after all, I had two days to run the happiness of
1..1,000,000 and it took quite a long time, but not nearly that long!

The second file (sekeol_happy.rb and also available at
http://www.makenai.net/tmp/sekeol_happy.rb ) is being submitted on
behalf of my coworker, Sekeol Kim. Unfortunately, he didn't leave me
any commentary other than the request that I submit the file for him
after the deadline lapsed.

Thanks!

-Pawel

shiawase_kazu_keikaku.rb (1.18 KB)

sekeol_happy.rb (1.09 KB)

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

···

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

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

Hi!

I'd just like to post my isHappy? method:

class Integer
  def isHappy?
    return to_s.split(//).collect{|digit| digit.to_i**2}.inject{|sum, n| sum +
n }.isHappy? while self!=1
    true
    rescue
    false
  end
end

puts
115485454654987986246476765451256546545241654555555555555555555555555555555555554125665146454122345444487.isHappy?
true

This method may return false negative (if happiness>maximum stack level),
though I doubt no one will ever find one!

Thanks for the quiz,

Eric

···

On Friday 01 September 2006 15:01, 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 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.

I wrote it and then added some lookup table optimizations which resulted
in a 1.5 speedup when executed over the numbers 1 through 10,000.

First the naive:

#!/usr/bin/ruby
# Ruby happy number quiz solution. September 2006
# Hans Fugal

class Happy
   def initialize
     @happy_numbers = { 1 => 0 }
   end

   def happy(n)
     return true if n == 1

     x = n
     rank = 0
     loop do
       sum = 0
       while x > 0
         x, r = x.divmod(10)
         sum += r**2
       end

       rank += 1

       if [0, 1, 4, 16, 20, 37, 42, 58, 89, 145].include?(sum)
         if sum == 1
           @happy_numbers[n] = rank
           return true
         else
           return false
         end
       end

       x = sum
     end
   end

   def rank(x)
     raise ArgumentError, "#{x} is unhappy." unless happy(x)
     return @happy_numbers[x]
   end
end

haphap = Happy.new
ARGF.each_line do |l|
   l.scan(/\d+/) do |token|
     x = token.to_i
     if haphap.happy(x)
       puts "#{x} is happy with rank #{haphap.rank(x)}"
     end
   end
end

Now the optimized:

#!/usr/bin/ruby
# Ruby happy number quiz solution. September 2006
# Hans Fugal

require 'set'

class Happy
   def initialize
     @happy_numbers = { 1 => 0 }
     @unhappy_numbers = Set.new
   end

   def happy(x)
     return true if @happy_numbers.has_key?(x)
     return false if @unhappy_numbers.include?(x)

     path = [x]
     loop do
       sum = 0
       while x > 0
         x, r = x.divmod(10)
         sum += r**2
       end

       if @unhappy_numbers.include?(sum)
         return false
       elsif @happy_numbers.has_key?(sum)
         r = @happy_numbers[sum]
         path.each_with_index do |x,i|
           @happy_numbers[x] = r + path.size - i
         end
         return true
       end

       path.push sum

       if [0, 1, 4, 16, 20, 37, 42, 58, 89, 145].include?(sum)
         if sum == 1
           s = path.size
           path.each_with_index do |x,i|
             @happy_numbers[x] = s - i - 1
           end
           return true
         else
           path.each do |x|
             @unhappy_numbers.add x
           end
           return false
         end
       end

       x = sum
     end
   end

   def rank(x)
     raise ArgumentError, "#{x} is unhappy." unless happy(x)
     return @happy_numbers[x]
   end
end

haphap = Happy.new
ARGF.each_line do |l|
   l.scan(/\d+/) do |token|
     x = token.to_i
     if haphap.happy(x)
       puts "#{x} is happy with rank #{haphap.rank(x)}"
     end
   end
end

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
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.
  
#! /usr/bin/env ruby

def sum_dig_sq(ival)
  sum = 0
  while ival > 0 do
    ival,dig = ival.divmod(10)
    sum += (dig * dig)
  end
  return sum
end

def happy?(ival)
# sad #s from http://mathworld.wolfram.com/HappyNumber.html
sad = [0, 4, 16, 20, 37, 42, 58, 89, 145]
rank = 0
while true do
  return -1 if sad.include?(ival) # check sad 1st - ~87% are sad
  ival = sum_dig_sq(ival)
  return rank if ival == 1
  rank += 1
end

if ARGV[0].to_i <= 0
  warn "usage: #{$0} <number>\n number must be > 0"
  exit
end

processed = []
happiest = []
(0..ARGV[0].to_i).each {|cur_num|
  base = cur_num.to_s.split('').sort.join.to_i
  processed[base] = happy?(cur_num) unless processed[base]
  rank = processed[base]
  next if rank < 0

  puts "#{cur_num} is happy - rank #{rank}"
  happiest[rank] = cur_num unless happiest[rank]
}

happiest.each_with_index do |val, ndx|
  puts "Happiest number of rank #{ndx} is #{val}"
end

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

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

Sounds right on to me.

James Edward Gray II

···

On Sep 1, 2006, at 8:12 AM, William Crawford wrote:

Okay, I'm feeling stupid here. What MAKES that number be happy? The
nearest I can find is that if it's an infinite loop, it isn't happy. If
it's not a loop, and resolves to 1 eventually. (It has to resolve to 1,
or it's be a loop.) It's happy.

Is that right?

Sorry, should have been 7 ** 2 :slight_smile:

Out of interest, any mathmaticians care to enlighten me as to whether
happy numbers are in any way "useful"?

Cheers,
Roland

I solved the question of the happiness of 1 by simply giving 10 and
such a happiness of 2, and 7 a happiness of 5.
This doesn't matter for determining the happiest number anyway, and is
a bit more consistent.

For finding the happiest numbers it only searches numbers with non
decreasing digits (eg. 123 but not 312 and 321).
This speeds up the search a lot, it can handle searching up to 10^10 in seconds.

It can also search for happy bases, because of this my solution has to
work for any base and is a bit messy as to_s is useless for this and
recursion is impossible for bases above 250 or so (stack overflow and
such).
To speed up searches it doesn't clear the cache from previous bases,
so memory uses increases until 300Mb at base 3000 or so.

Anyway, the world is a better place now that we know there are no
happy bases under 3202 :wink:

Usage:
happy.rb find [base] - find the happiest number under base^7
happy.rb without parameters: search for happy bases

Code:

class Array
  def sum
    inject(0){|a,b| a+b}
  end
end

class Integer

  def to_digits(base)
    return [self] if self < base
    (self/base).to_digits(base) << self%base
  end

  def happy_function
    to_digits($base).map{|d| d ** 2}.sum
  end

  def happiness
    num = self
    chain = [num]
    until num == 1 || num.cached_happiness == -1
      num.cached_happiness = -1
      chain << num = num.happy_function
    end
    if num == 1
      chain.shift.cached_happiness = chain.size until chain.empty?
    end
    self.cached_happiness
  end

  def happy?
    happiness >= 0
  end

  protected
  def cached_happiness
    return 0 if self==1
    (@happiness||={})[$base]
  end

  def cached_happiness=(val)
    (@happiness||={})[$base] = val
  end
end

def nondec_nums(len,min=0,n=0,&b) # yields all numbers with
non-decreasing digit sequences of length <= len
  if len==0
    yield n
  else
    [*min...$base].each{|m| nondec_nums(len-1, m ,n * $base + m,&b) }
  end
end

maxn = maxh = 1
s = Time.now

if ARGV[0] == 'find'
  $base = (ARGV[1] || 10 ).to_i
  MAXLEN = 7
  puts "searching happiest number < #{$base**MAXLEN} in base #{$base}"
  max_n, max_h = 1,0
  nondec_nums(MAXLEN) {|n| # length 7 / up to 9,999,999
  if n.happiness > max_h
    max_n, max_h = n, n.happiness
    puts "n=#{n}\th=#{max_h}\tdigits=#{n.to_digits($base).inspect}"
  end
}
else
  puts "searching for happy bases, press ctrl-c to quit"
  (2..1_000_000).each {|$base|
    len = 3 # len * (base-1)^2 < b^len - 1 for len >= 3 and any base
    max = $base**len - 1 # upper bound for when \forall n>=max
n.happy_function < n => if all numbers of up to and including this
length are happy then all numbers are
    max -= $base**(len-1) while max.happy_function < max # further
decrease upper bound, for base 10 this is : 999, 899, 799, etc
    max += $base**(len-1) # previous loop always does 1 step too much
    happy_base = true
    min_unhappy = nil
    nondec_nums(len) {|n|
      if !n.happy? && n>0
        min_unhappy = n
        happy_base = false
        break
      end
      break if n > max
    }
    puts happy_base ? "base #{$base} is a happy base!" : "base
#{$base} is not a happy base because #{min_unhappy} is unhappy."
  }
end

My solution. Not nearly as short as the others, and I didn't implement
bases.

use like:
h = Happy.new(5)
puts h.happy

class Happy
    @@cache = []
    attr_accessor :num,:happy,:friends,:checked
    def initialize(num,friends=[])
        @num=num.to_i
        (return @@cache[@num]) if @@cache[@num]
        @friends=friends
        @happy=false
        check
        self
    end

    def check
        return @happy if @checked
        dig = @num.to_s.split("")
        dig = dig.map{|n| n.to_i }
        res = dig.inject(0){|sum,d| sum + d * d }
        if(res==1)
            @friends = []
            return save(true)
        else
            if(@friends.include?(res))
                return save(false)
            else
                h = Happy.new(res,@friends + [@num])
                if(@happy=h.happy)
                    @friends = h.friends + [h.num]
                    return save(true)
                else
                    return save(false)
                end
            end
        end
    end

    def save(happy)
        @happy=happy
        @checked=true
        @@cache[@num]=self
        self
    end
end