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! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 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 2005-12-02 14:46

on 2005-12-02 14:54

On 02/12/05, Ruby Quiz <james@grayproductions.net> 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/

on 2005-12-02 14:54

On 02/12/05, Brian SchrÃ¶der <ruby.brian@gmail.com> 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/

on 2005-12-02 15:51

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 2005-12-03 17:48

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

on 2005-12-03 17:56

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 Gray II

on 2005-12-03 19:42

```
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 Gray II
```

on 2005-12-04 14:52

My first Ruby Quiz solution... Cheers, -rob #! /usr/bin/ruby # # Ruby program to find all the weird numbers less than a given input # Rob Leslie <rob@mars.org> # 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

on 2005-12-04 15:08

And immediately upon posting my first Ruby Quiz solution, I discovered a small bug. :-{ Perhaps someone will notice it. :-)

on 2005-12-04 15:21

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

on 2005-12-04 18:04

On 12/4/05, Rob Leslie <rob@mars.org> wrote: > And immediately upon posting my first Ruby Quiz 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

on 2005-12-04 18:08

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

on 2005-12-04 19:39

On Dec 4, 2005, at 9:03 AM, Paolo Capriotti 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.

on 2005-12-05 16:39

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

on 2005-12-05 16:52

On Dec 5, 2005, at 9:38 AM, Mike Harris 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 Gray II

on 2005-12-05 17:00

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!

on 2005-12-05 17:29

James Edward Gray 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.

on 2005-12-05 17:37

James Edward Gray 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

on 2005-12-05 18:43

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

on 2005-12-05 22:31

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

on 2005-12-06 15:14

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

on 2005-12-08 11:21

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/

on 2005-12-08 15:40

On Dec 8, 2005, at 4:19 AM, Dan Diebolt 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 Gray II

on 2005-12-08 16:13

On Thu, Dec 08, 2005 at 07:19:43PM +0900, Dan Diebolt 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