The three rules of Ruby Q.:

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

Support Ruby Q. by submitting ideas as often as you can:
http://www.rubyquiz.com/
 Enjoy!
========================================
by Martin DeMello
A weird number is defined as a number, n, such that the sum of all its
divisors
(excluding n itself) is greater than n, but no subset of its divisors
sums up to
exactly n.
Write a program to find all the weird numbers less than a given input.
On 02/12/05, Ruby Q. [email protected] wrote:
I imagine that 1 is also excluded as a divisor, otherwise the answer
would be the empty set always.
Brian
–
http://ruby.brianschroeder.de/
Stringed instrument chords: http://chordlist.brianschroeder.de/
On 02/12/05, Brian Schröder [email protected] wrote:
 Enjoy!
I imagine that 1 is also excluded as a divisor, otherwise the answer
would be the empty set always.
Brian
Sorry for the noise…
–
http://ruby.brianschroeder.de/
Stringed instrument chords: http://chordlist.brianschroeder.de/
please give an example of such a number. english is my second language,
and
english math speak is more like my sixth language or so (below
german,swedish techspeak and english techspeak).
On Dec 3, 2005, at 10:47 AM, Hampton wrote:
Meh. I’ve done it (dont’ worry, not posting it…), but this thing’s
gotta be like O(n^3) at least.
When this quiz was posed to me, the creator thought it would be
interesting to see what optimizations people came up with. Now,
watching the discussions since it has released, I have an idea for
another hefty one. Think outside the box…
James Edward G. II
Meh. I’ve done it (dont’ worry, not posting it…), but this thing’s
gotta be like O(n^3) at least.
hampton.
On Dec 3, 2005, at 12:37 PM, Hampton wrote:
I have a feeling we have the same idea.
Code it up and send it in tomorrow. I’ll create my idea if I don’t
see a match for it…
James Edward G. II
I have a feeling we have the same idea.
hampton.
My first Ruby Q. solution…
Cheers,
rob
#! /usr/bin/ruby
Ruby program to find all the weird numbers less than a given input
class Integer
WEIRD_ODD_UNKNOWN_THRESHOLD = 10 ** 18
def weird?
# Odd numbers less than 10**18 are not weird. (Bob Hearn, July
2005)
return false if self & 1 == 1 && self < WEIRD_ODD_UNKNOWN_THRESHOLD
# Weird numbers are abundant. To be abundant, the sum of the
divisors
# must be greater than twice this number. Equivalently, the sum of
# the proper divisors (excluding the number itself) must be greater
# than this number.
divisors = self.divisors
sum = divisors.inject { sum, x sum + x }  self
return false unless sum > self
# Weird numbers are not semiperfect. To be semiperfect, the sum
of a
# subset of the divisors must be equal to this number.
Equivalently,
# the sum of another subset (the complement set) of divisors
must be
# equal to the difference between this number and the sum of all
its
# divisors.
excess = sum  self
addends = divisors.reject { x x > excess }
sum = addends.inject { sum, x sum + x }
# Trivially semiperfect or nonsemiperfect?
return false if sum == excess  addends.include?(excess)
return true if sum < excess
# Default nonsemiperfect test (with special case speed
optimization)
self < 222_952 ? 9_272 == self : !excess.sum_of_subset?(addends)
end
def divisors
# Naive implementation; OK for small numbers
list = (1…Math.sqrt(self).floor).select { i (self % i).zero? }
list + list.reverse.collect { i self / i }
end
def sum_of_subset?(addends)
first = addends.first
return true if self == first
return false unless addends.length > 1
rest = addends[1…1]
(self  first).sum_of_subset?(rest) or self.sum_of_subset?(rest)
end
end
input = ARGV.shift.to_i
70.upto(input  1) do number
puts number if number.weird?
end
This thread was getting a little crowded, so I started a new one for
solutions.
On 12/4/05, Rob L. [email protected] wrote:
And immediately upon posting my first Ruby Q. solution, I
discovered a small bug. :{
Perhaps someone will notice it.
I’ve found this one:
$ irb r weird.rb
irb(main):001:0> 4.divisors
=> [1, 2, 2, 4]
Paolo
And immediately upon posting my first Ruby Q. solution, I
discovered a small bug. :{
Perhaps someone will notice it.
On Dec 4, 2005, at 9:03 AM, Paolo C. wrote:
Exactly right.
I had previously written Integer#divisors something like this:
def divisors
list = (2…Math.sqrt(self).floor).select { i (self % i).zero? }
list += list.collect { i self / i }
[1, *list].uniq
end
but forgot the value of calling Array#uniq upon simplifying and
refactoring.
This is my solution:
class Integer
def divisors
res = []
i = 1
while ii < self
if self % i == 0
res << i
end
i += 1
end
(res.size  1).downto(1) do k
res << self / res[k]
end
res << i if ii == 0
res
end
end
def weird(n)
div_sum = 0
possible_sums = Hash.new
possible_sums[0] = true
n.divisors.each do i
div_sum += i
possible_sums.keys.each do s
new_sum = s + i
possible_sums[new_sum] = true if new_sum <= n
return false if new_sum == n
end
end
return div_sum > n
end
n = ARGV.shift or exit
n = n.to_i
m = ARGV.shift
m = m.to_i if m
range = m ? (n…m) : (1…n)
for i in range
puts i if weird(i)
end
On Dec 5, 2005, at 9:38 AM, Mike H. wrote:
each_divisor do i
return false if sumi == self
end
Hmm, does that work?
I’m not trying to slander your code. I’m actually asking because I
think it’s very elegant, if it’s also correct.
You’re code removes divisors onebyone, but what if our divisors
looked something like:
1, …, 50, …, 100
And the total sum was just 50 over the number we’re testing? The
order we remove divisors might be significant then. Am I right?
James Edward G. II
My solution. Error checking is minimal to nonexistent.
class Integer
def each_divisor
for i in 1…self
yield(i) if self%i == 0
end
end
def weird?
sum = 0
each_divisor do i sum += i end
return false if sum <= self
each_divisor do i
return false if sumi == self
end
end
end
print "Enter Number (Program will print all lesser weird numbers): "
num = gets
for i in 1…num.to_i
puts i if i.weird?
end
James Edward G. II wrote:
think it’s very elegant, if it’s also correct.
ah, I screwed up and scrambled the problem description inbetween reading
it and writing it. My solution only considers subsets of size N1,
where N is the divisor count.
James Edward G. II wrote:
think it’s very elegant, if it’s also correct.
looks like the proper way I should have done this is to define
Array#each_subset (or possibly Enumerable#each_subset) and cycle through
divisors.each_subset
Here’s my solution, made before peeking at any of the other submissions.
It’s not too bad; generates the weird numbers up to 100,000 in about 3
minutes on a pokey 233 Celeron.
http://users.adelphia.net/~showaltb/rubyquiz/57/weird.rb
Now I’m off to peek at the other solutions to see how bad my algorithm
is!
This is my first ruby quiz solution since Quiz #1 : ) Thanks, it was
fun.
Moses