From: Hampton <hcatlin@...>
Date: 2005-12-04T22:27:32+09:00
Subject: [QUIZ] Weird Numbers (#57) Solution

Here is my solution. Its not the most beautiful thing in the world, but
its effective.

-----------------------------------------

def weirdo_exhaustive(from, max)
  puts "none found" and return 0 if max < 70
  (from..max).each do |num|
    if num % 2 == 0
      list, sum= [], 0
      (1...num).each do |div|
        list << div and sum += div if num % div == 0
      end
      puts "==" + num.to_s if sum > num and has_sum(num, list) == false
    end
  end
end

def has_sum(num, array)
  if array.is_a? Integer then return false end
  sum = 0
  array.each do |val| sum += val end
  if sum === num then return true end
  #this next line saves a BUNCH of checks.
  if sum < num then return false end
  array.each do |removeme|
    copy = array.dup
    copy.delete(removeme)
    if copy.size > 1 and has_sum(num, copy) == true then return true
end
  end
  return false
end

----------------------------------------

It took a good number of optimizations that make it less pretty, but
much faster. The first time I ran it it took 4 hours to reach 1,000.
Its faster than that now, but its still somewhere around O(3^n).

SO... I thought of a way to speed up the algorithm a lot! So, with a
*few* more optimizations, here's the weirdo_fast algorithm.

-------------------------------------------------------

def weirdo_fast(max)
  list = [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
	83312,91388,113072,243892,254012,338572,343876,388076,  #
        519712,539744,555616,682592,786208,1188256,1229152,1713592, #
        1901728,2081824,2189024,3963968 ]
  list.each do |num|
    puts num if num <= max
  end
  if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1],
max) end
end

-----------------------------------------------------

A little faster, eh? It will start exhaustively searching if your max
is out of its range.... but I warn you, my computer has been
calculating 3963970 for the last 24 hours. And, not the range up to it,
just that number. Remember, its 3^3963970 = 62_286_091_158_062_773_000
which takes a minute to calculate. Well, with my other optimizations,
its a tad faster than that.... a tad.

I'm interested to see if anyone else found a much better way to test
for has_sum(num, array). It seems to me like there must be a clever
mathematical trick for getting the job done. Or perhaps the only clever
way is my "fast" algorithm. But, that's not even that clever.

-Hampton Catlin.
hcatlin@gmail.com