Weird Numbers (#57)

bbazzarrakk · December 2, 2005, 2:46pm

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.

bbazzarrakk · December 2, 2005, 2:54pm

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.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

bbazzarrakk · December 2, 2005, 2:54pm

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.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

bbazzarrakk · December 2, 2005, 3:51pm

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

bbazzarrakk · December 3, 2005, 5:56pm

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

bbazzarrakk · December 3, 2005, 5:48pm

Meh. I’ve done it (dont’ worry, not posting it…), but this thing’s
gotta be like O(n^3) at least.

-hampton.

bbazzarrakk · December 3, 2005, 7:42pm

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

bbazzarrakk · December 3, 2005, 7:38pm

I have a feeling we have the same idea.

-hampton.

bbazzarrakk · December 4, 2005, 2:52pm

My first Ruby Q. solution…

Cheers,
-rob

#! /usr/bin/ruby

Ruby program to find all the weird numbers less than a given input

Rob L. [email protected]

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 non-semiperfect?
 return false if sum == excess || addends.include?(excess)
 return true if sum < excess

 # Default non-semiperfect 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

bbazzarrakk · December 4, 2005, 3:21pm

This thread was getting a little crowded, so I started a new one for
solutions.

bbazzarrakk · December 4, 2005, 6:04pm

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

bbazzarrakk · December 4, 2005, 3:08pm

And immediately upon posting my first Ruby Q. solution, I
discovered a small bug. :-{

Perhaps someone will notice it.

bbazzarrakk · December 4, 2005, 7:39pm

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.

bbazzarrakk · December 4, 2005, 6:08pm

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

bbazzarrakk · December 5, 2005, 4:52pm

On Dec 5, 2005, at 9:38 AM, Mike H. wrote:

each_divisor do |i|
return false if sum-i == 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 one-by-one, 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

bbazzarrakk · December 5, 2005, 4:39pm

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 sum-i == 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

bbazzarrakk · December 5, 2005, 5:29pm

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 N-1,
where N is the divisor count.

bbazzarrakk · December 5, 2005, 5:37pm

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

bbazzarrakk · December 5, 2005, 5:00pm

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!

bbazzarrakk · December 5, 2005, 10:31pm

This is my first ruby quiz solution since Quiz #1 : ) Thanks, it was
fun.

Moses