Forum: Ruby Weird Numbers (#57)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2005-12-02 15:46
(Received via mailing list)
The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  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.
ruby.brian (Guest)
on 2005-12-02 15:54
(Received via mailing list)
On 02/12/05, Ruby Q. <removed_email_address@domain.invalid> 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/
ruby.brian (Guest)
on 2005-12-02 15:54
(Received via mailing list)
On 02/12/05, Brian Schröder <removed_email_address@domain.invalid> wrote:
> > 3.  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/
mrkode (Guest)
on 2005-12-02 16:51
(Received via mailing list)
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).
hcatlin (Guest)
on 2005-12-03 18:48
(Received via mailing list)
Meh. I've done it (dont' worry, not posting it...), but this thing's
gotta be like O(n^3) at least.

-hampton.
James G. (Guest)
on 2005-12-03 18:56
(Received via mailing list)
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
hcatlin (Guest)
on 2005-12-03 20:38
(Received via mailing list)
I have a feeling we have the same idea.

-hampton.
James G. (Guest)
on 2005-12-03 20:42
(Received via mailing list)
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
rob (Guest)
on 2005-12-04 15:52
(Received via mailing list)
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. <removed_email_address@domain.invalid>
#

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
rob (Guest)
on 2005-12-04 16:08
(Received via mailing list)
And immediately upon posting my first Ruby Q. solution, I
discovered a small bug.  :-{

Perhaps someone will notice it.  :-)
hcatlin (Guest)
on 2005-12-04 16:21
(Received via mailing list)
This thread was getting a little crowded, so I started a new one for
solutions.
p.capriotti (Guest)
on 2005-12-04 19:04
(Received via mailing list)
On 12/4/05, Rob L. <removed_email_address@domain.invalid> 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
p.capriotti (Guest)
on 2005-12-04 19:08
(Received via mailing list)
This is my solution:

class Integer
  def divisors
    res = []
    i = 1
    while i*i < 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 i*i == 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
rob (Guest)
on 2005-12-04 20:39
(Received via mailing list)
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.
GENIE (Guest)
on 2005-12-05 17:39
(Received via mailing list)
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
James G. (Guest)
on 2005-12-05 17:52
(Received via mailing list)
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
bob_showalter (Guest)
on 2005-12-05 18:00
(Received via mailing list)
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!
GENIE (Guest)
on 2005-12-05 18:29
(Received via mailing list)
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.
GENIE (Guest)
on 2005-12-05 18:37
(Received via mailing list)
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
leavengood (Guest)
on 2005-12-05 19:43
(Received via mailing list)
Your solution is definitely in the faster group Bob, though about a
third as fast as the fastest (based on quick and dirty testing on my
laptop.)

In general your algorithm is pretty similar to the faster ones. You
know, it seems like it would be useful to analyze all the solutions to
possibly find Ruby "performance anti-patterns", since there are some
wildly different performance numbers in the solutions for this quiz.

If you think about it, people who complain about Ruby's performance
may just be using some of these "performance anti-patterns", and could
greatly increase performance with some knowledgeable tweaking. For
example the blogger who was analyzing his web server logs and
unnecessarily parsing a lot of dates, which slowed things down a lot.
When I politely corrected him on this and he changed the code,
performance greatly increased, and his view of Ruby improved a lot too
[1].

Ryan

1. http://www.pankaj-k.net/archives/2005/11/revised_r...
mmhohman (Guest)
on 2005-12-05 23:31
(Received via mailing list)
This is my first ruby quiz solution since Quiz #1 : ) Thanks, it was
fun.

Moses
p.capriotti (Guest)
on 2005-12-06 16:14
(Received via mailing list)
My previous solution contained an error. This is a new version,
corrected and slightly optimized, but still not quite as fast as the
fastest solutions.

Paolo

--

class Integer
  def divisors
    res = []
    i = 1
    while i*i < 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 i*i == self
    res
  end
end

def weird(n)
  possible_sums = Hash.new
  possible_sums[0] = true

  divisors = n.divisors

  div_sum = divisors.inject(0) {|s, i| s+i }

  return false if div_sum <= n

  diff = div_sum - n
  return false if divisors.include? diff

  divisors.each do |i|
    possible_sums.keys.sort.each do |s|
      new_sum = s + i
      case new_sum <=> diff
      when -1
        possible_sums[new_sum] = true
      when 0
        return false
      when 1
        break
      end
    end
  end

  return true
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
dandiebolt (Guest)
on 2005-12-08 12:21
(Received via mailing list)
I found this program msieve.exe that does Quadratic Seive Factoring of
arbitrary integers and I wonder if there is time enough to put together
a brute force solution to the Weird Number quiz before the summary comes
out. The basic idea would be to find the prime factors of successive
integers using the output msieve.exe and testing for abundance and
weirdness based on these factors. Is there any rule on the Quiz the
prevents helper codes from being used? The Quadratic Seive is the
fastest algorithm known for factoring integers with less than 110
digits. In the search for Weird Numbers the speed of the Quadratic Seive
factoring of sufficiently large numbers will probably overcome the
repeated system calls and text parsing of the output.

  Here is the Ruby code that will factor 2_138_723_987 in the blink of
an eye into a 2 two digit (p2 token) and a seven digit (prp7 token)
factors:

  irb(main):010:0> puts `msieve -q 2138723987`
  2138723987
p2: 29
p2: 37
prp7: 1993219
  => nil

check: 2_138_723_987 = 29 * 37 * 1_993_219

  Here is the program:

  http://www.boo.net/~jasonp/qs.html

  and here is a summary of the theory:

  http://en.wikipedia.org/wiki/Quadratic_sieve

  Here are the switches for controlling msieve:

  msieve -h displays command options:

  C:\DOCUME~1\OWNER\DESKTOP>msieve -h
  Msieve v. 1.03
  usage: MSIEVE [options] [one_number]
  options:
   -s <name> save intermediate results to <name>
             instead of the default msieve.dat
   -l <name> append log information to <name>
             instead of the default msieve.log
   -i <name> read one or more integers to factor from
             <name> (default worktodo.ini) instead of
             from the command line
   -m        manual mode: enter numbers via standard input
   -q        quiet: do not generate any log information,
             only print any factors found
   -d <min>  deadline: if still sieving after <min>
             minutes, shut down gracefully (default off)
   -r <num>  stop after finding <num> relations
   -c        client: only perform sieving
   -v        verbose: write log information to screen
             as well as to logfile

  Here is a list of 15 million prime numbers that might be helpful
checking computations:

  http://primes.utm.edu/lists/small/millions/
James G. (Guest)
on 2005-12-08 16:40
(Received via mailing list)
On Dec 8, 2005, at 4:19 AM, Dan D. wrote:

> I found this program msieve.exe that does Quadratic Seive Factoring
> of arbitrary integers and I wonder if there is time enough to put
> together a brute force solution to the Weird Number quiz before the
> summary comes out.

No.  ;)  But don't let that discourage you from playing with the
idea.  Summaries are about my schedule.  Solutions are about yours.
They're only loosely related.

> Is there any rule on the Quiz the prevents helper codes from being
> used?

Not at all.  We're not much of a rules bunch.

James Edward G. II
ef (Guest)
on 2005-12-08 17:13
(Received via mailing list)
On Thu, Dec 08, 2005 at 07:19:43PM +0900, Dan D. wrote:
> I found this program msieve.exe that does Quadratic Seive Factoring
> of arbitrary integers and I wonder if there is time enough to put
> together a brute force solution to the Weird Number quiz before the
> summary comes out. The basic idea would be to find the prime factors
> of successive integers using the output msieve.exe and testing for
> abundance and weirdness based on these factors.

I'd be curious to see how it works out, but my guess is that it won't
speed things up much.  My solution sieves for prime numbers too (using
the simpler Sieve of Eratosthenes), and that only takes a tiny
fraction of the running time.  The computationally hard part is
proving non-semiperfect.

regards,
Ed
This topic is locked and can not be replied to.