[QUIZ] Weird Numbers (#57) Solution

[Ryan Leavengood]

Just up to 100,000 you are missing 191 weird numbers. Run my, Rob or
Edward's solution to see exactly which ones.

Up to 3963968, I don't even want to guess how many are missing. Even
Edward's solution would take some time to find out. They aren't quite
as rare as you think.

Ryan

 

[Hampton]

I realized it was a list of primitive weird numbers instead of weird
numbers.

Down below I have links to the two lists of numbers.

My bad.

-hampton.

 

[Ryan Leavengood]

I did mine with a good dose of humor.

Hehehe, I could see that a bit.

I certainly know that my weirdo_exhaustive is slow... hell, I called it
both "weirdo" and "exhaustive". However, I thought of the fast solution
as a bit of humor for everyone to enjoy. I do think it has merit in
*some* ways only because its damn hard to make anything go faster than
that.

Well there is no doubt that in a real application there would be a
cache for weird numbers, should that application need them frequently.

I did not mean any previous comments to be "i'm better than you" in any
real way. They were all made tounge in cheek because of course just
accessing an array is going to be orders of magnatude faster.

Fair enough, and I would have appreciated the solution more had it been cor=
rect.

These quizes are not for points and there is no "winner" (at least not
that i've seen assigned in previous iterations of the quiz. In fact,
there is never any qualifications for what makes the best one!

Of course, but quizzes like this benefit from analyzing which
algorithms are the fastest. This one in particular had a HUGE margin
between the fast and slow solutions. Other quizzes are more about the
structure of the code and solving the problem elegantly, and you won't
see me or anyone else getting out the benchmarking tools.

And yes, I did use the wrong number set. I found the number set for
primitive weird numbers, not exhaustive.

I used this:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi= ?Anum=3DA002975
As opposed to this:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi= ?Anum=3DA006037

My mistake....

I see, easy enough mistake to make I suppose.

But, lets all be friends! How about a beer?

Don't take my criticism as being hostile. In fact if you read this
list you'll find me most helpful when newbies have problems. But I
don't hesitate to tell people when they are wrong. A beer would be
fine if you happen to live where I am, in South Florida

Ryan

 

[Hampton]

I'm from Jacksonville originally, but now live in the cold tundra of
Toronto.

However, I will be there for christmas!

Yes, it was hostile. And I will beat up both your *and* your mom for
what you said about my misfunctioning algorithm!

-hampton.

PS: However, I will say that on the next one, I'm going to be debugging
just a tad more.

 

[Ryan Leavengood]

NOW you're talking! You could just calculate them once and that's
the best of both worlds...

Well I coded this up. Instead of pasting my whole solution I'll just
paste the cache class and the updated "main" block for my solution.
I've also added some timing code so one can see the speed
improvements. To try this out, replace my if $0 =3D=3D __FILE__ code from
my original solution with all of the following:

class WeirdCache
def initialize(filename=3D'.weirdcache')
@filename =3D filename
if test(?e, filename)
@numbers =3D IO.readlines(filename).map do |i|
i.chomp.to_i
end
else
@numbers=3D[]
end
@added =3D false
end

def each(&block)
@numbers.each(&block)
end

def <<(i)
@added =3D true
@numbers << i
end

def save
if @added
File.open(@filename, File::RDWR|File::CREAT|File::TRUNC) do |file|
file.puts @numbers
end
end
end
end

if $0 =3D=3D __FILE__
if ARGV.length < 1
puts "Usage: #$0 <upper limit>"
exit(1)
end

puts "Weird numbers up to and including #{ARGV[0]}:"
start =3D Time.now
cache =3D WeirdCache.new
at_exit {cache.save}
limit =3D ARGV[0].to_i
i =3D 69
cache.each do |i|
if i <=3D limit
puts i
end
end
(i+1).upto(limit) do |j|
if j.weird?
cache << j
puts j
end
end
puts "This took #{Time.now - start} seconds"
end

 

[Dan Diebolt]

--0-240704300-1133733392=:26971
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable

His caching optimization is certainly a good idea (and fairly
obvious), though it would be better if it actually generated the cache
and reused it so that subsequent runs got faster. I may code up
something like this.

Why not take the Seti-At-Home approach and parcel out ranges of numbers=
that can be checkout by home users with spare cycles on their machines, =
searched for WeirdNumbers and reported back to the mothership.

=09

 

[James Edward Gray II]

Well I coded this up.

Just so others see the effect of this, here are some timings from
runs. The first is Ryan's original code, the second is the new
version's first (cache-less) run, and the third is the code taking
advantage of the cache:

Neo:~/Documents/Ruby/Ruby Quiz$ time ruby solutions/Ryan\ Leavengood/
weird_numbers.rb 50000
Weird numbers up to and including 50000:
...

real 0m6.258s
user 0m6.170s
sys 0m0.046s
Neo:~/Documents/Ruby/Ruby Quiz$ time ruby solutions/Ryan\ Leavengood/
weird_numbers.rb 50000
Weird numbers up to and including 50000:
...
This took 6.231214 seconds

real 0m6.253s
user 0m6.169s
sys 0m0.044s
Neo:~/Documents/Ruby/Ruby Quiz$ time ruby solutions/Ryan\ Leavengood/
weird_numbers.rb 50000
Weird numbers up to and including 50000:
...
This took 0.096576 seconds

real 0m0.116s
user 0m0.102s
sys 0m0.011s

James Edward Gray II

 

[Christer Nilsson]

This was really a good and enjoyable exercise. I learnt a lot. One of
the best solutions is made by Leavengood. I would like to point out a
small error. 36.calc_divisors returns [1,2,3,4,6,6,9,12,18,36]. 6 is
reckoned twice. This seems to have no implication on the result though.

def calc_divisors
res=[1]
2.upto(Math.sqrt(self).floor) do |i|
if self % i == 0
res << i
end
end
res.reverse.each do |i|
res << self / i
end
res
end

The part I appreciate most is the beautiful and fast handling of the
binary set:

def sum_in_subset?(a)
if self < 0
false
elsif a.include?(self)
true
else
if a.length == 1
false
else
f = a.first
remaining = a[1..-1]
(self - f).sum_in_subset?(remaining) or
sum_in_subset?(remaining)
end
end
end

I also learnt that Ruby is really quick once you leave the debugger!

Here is my solution. It is short but slow.

def divisors(n) (1..n.div(2)).collect {|i| i if n.modulo(i)==0}.compact
end
def sum(arr) arr.inject(0) {|sum,element| sum+element} end

def subset?(n, divisors)
arr=[]
divisors.each do |i|
arr.concat arr.collect {|j| i+j}
arr << i
arr.uniq!
return true if arr.member?(n)
end
false
end

def weird(n)
return if n.modulo(2)==1
coll = divisors(n)
diff = sum(coll)-n
return if diff <= 0
return n unless subset?(diff,coll)
end

def all_weird(n) (1..n).collect {|i| weird(i)}.compact end

assert_equal [1,2,3,4,6], divisors(12)
assert_equal [1,2,5,7,10,14,35], divisors(70)
assert_equal 16, sum(divisors(12))
assert_equal 74, sum(divisors(70))
assert_equal true, subset?(12,divisors(12))
assert_equal false, subset?(70,divisors(70))
assert_equal false, subset?(4,divisors(70))
assert_equal nil, weird(2)
assert_equal nil, weird(12)
assert_equal nil, weird(20)
assert_equal 70, weird(70)
assert_equal [70], all_weird(70)
assert_equal [70,836], all_weird(836)

Christer

 

[Ryan Leavengood]

This was really a good and enjoyable exercise. I learnt a lot. One of
the best solutions is made by Leavengood. I would like to point out a
small error. 36.calc_divisors returns [1,2,3,4,6,6,9,12,18,36]. 6 is
reckoned twice. This seems to have no implication on the result though.

Thank you for the compliment and for catching the error. It seems
calc_divisors will always have two divisors for the square root of any
perfect square. I suppose it was just luck that this didn't mess up
the algorithm. But there might be some number where this could cause a
problem, so res.uniq should probably be called at the end.

Ryan

 

[Martin DeMello]

#!ruby
=begin

The Quiz was real fun and I spent quite a lot of time on it. Below
source is rather easy, but believe me I tried lots of different ways
(such as dynamic binary knapsacks etc.), most of them suck because they
need to many method calls.

Same here - I tried a bunch of stuff, but the code ended up being rather
slow, so I discarded it. It's still rather slow

N = ARGV[0].to_i

# precalculate the list of primes

def primes_to(n)
sieve = (0..n).to_a
2.upto(n) {|i|
next unless sieve
(i*i).step(n, i) {|j| sieve[j] = nil}
}
sieve[2..-1].compact
end

PRIMES = primes_to(N)

# helper method
class Array
def bsearch(n)
i = 0
j = size - 1
k = (i+j)/2
while i < k
if at(k) > n
j = k
elsif at(k) < n
i = k
else
return k
end
k = (i+j)/2
end
return i
end
end

# factorisation routines - find the prime factors, then combine them to get a
# list of all factors

def prime_factors(x)
pf = Hash.new {|h, k| h[k] = 0}
PRIMES.each {|p|
break if p > x
while x % p == 0
pf[p] += 1
x /= p
end
}
pf
end

def expand_factors(f, pf)
return f if pf.empty?
p, n = pf.shift
powers = [p]
(n-1).times { powers << p * powers[-1] }
g = f.dup
powers.each {|i| f.each {|j| g << i*j } }
expand_factors(g, pf)
end

def factors(n)
a = expand_factors([1], prime_factors(n)).sort
a.pop
a
end

# and finally, the weirdness test

def weird?(n)
fact = factors(n)
#
# test for abundance (sum(factors(n)) > n)
sum = fact.inject {|a, i| a+i}
return false if sum < n # weird numbers are abundant

# now the hard part
partials = [0]

fact.each {|f|
if sum < n
# discard those partials that are lower than the sum of all remaining
# factors
i = partials.bsearch(n-sum)
return false if partials == (n-sum)
partials = partials[(i+1)..-1]
end

sum -= f # sum of all remaining factors
temp = []

partials.each {|p|
j = f + p
break if j > n
l = n - j
next if l > sum
return false if (j == n) or (l == sum)
temp << j
}

# handwriting a merge sort didn't help :-/
partials = partials.concat(temp).sort.uniq
}

return true
end

def all_weird(n)
weird = []
# odd numbers are not weird (unproven but true for all n < 10^17)
2.step(n, 2) {|i| weird << i if weird?(i) }
weird
end

require 'benchmark'

Benchmark.bm(10) {|x|
[1000,10000,20000].each {|n|
x.report("#{n}") {p all_weird(n)}
}
}

martin

 

[Ryan Leavengood]

Yes, this is quite nice. I rewrote it a bit so that it does not need
the nested ifs. What do you think?

def sum_in_subset?(div =3D self.divisors)
return false if self < 0
return false if div.empty?
return true if div.include?(self)

f, remaining =3D div[0], div[1..-1]
(self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining)
end

I don't really like multiple returns, which is why I wrote it like
that. But the above is still pretty nice, and certainly more succinct.
Here you can also see how similar this is to Rob Leslie's method of
finding the sums of the subsets. He posted before me though and
deserves credit as well for a nice and fast solution. His solution is
in the original quiz thread.

Ryan

 

[Dave Burt]

I have a solution for the "effectively useless" basket. It's a naive
algorithm, and I haven't yet received a number above 70 from it.

The advantages are that it's straightforward idiomatic Ruby, and core of the
algorithm is expressed about as tersely as Martin's definition. And I like
my ArraySubsetList class.

class Fixnum
def divisors
(1..self).select {|i| self % i == 0 }
end
end
module Enumerable
def sum
inject(0) {|m, o| m + o }
end
end
class Array
def subsets
ArraySubsetList.new(self)
end
end
class ArraySubsetList
def initialize(array)
@array = array
end
def [](index)
return nil unless (0...size) === index
ret = []
@array.size.times {|i| ret << @array if index == 1 }
ret
end
def each
size.times {|bits| yield self[bits] }
end
include Enumerable
def size
1 << @array.size
end
alias length size
end
def wierd_numbers_up_to(max)
ret = []
for n in 1..max
# 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.
divs = n.divisors
divs.delete i
if divs.sum > i &&
divs.subsets.select {|subset| subset.sum == i }.empty?
ret << i
yield i if block_given?
end
end
ret
end
if $0 == __FILE__
if ARGV.size == 1 && (ARGV[0].to_i rescue 0) > 0
wierd_numbers_up_to(ARGV[0].to_i) {|n| puts n }
else
puts "usage: #$0 n\n Find all weird numbers less than n"
end
end

Cheers,
Dave

 

[Kenneth Collins]

Wow, I got a lot from looking at the other solutions. Thanks especially
to Ed, Ryan, Jannis and Christian. I see that the single biggest
performance gain comes from using a recursive sum_in_subset? method such
as that found in Ed's solution. I've borrowed from his code for this
fairly simple and straightforward resubmission. It doesn't perform as
well as the faster solutions, but it's much, much faster than my first
submission.

#!/usr/bin/env ruby
#
# Ruby Quiz Weird Numbers solution.
# Uses recursive sum_in_subset? approach borrowed from
# other solutions.
#

class Integer

def weird?
divisors = self.divisor_list
abundancy = divisors.inject { |total,x| total += x } - self
return false unless abundancy > 0
smalldivisors = divisors.reverse.select { |j| j <= abundancy }
return false if sum_in_subset?(smalldivisors, abundancy)
return true
end

def sum_in_subset?(list, target)
return false if target < 0
return true if list.include?(target)
return false if list.length == 1
first = list.first
rest = list[1..-1]
sum_in_subset?(rest, target-first) or sum_in_subset?(rest, target)
end

def divisor_list
list = []
(1..Math.sqrt(self).to_i).each do |x|
if self % x == 0
list << x
list << (self / x) unless x == 1 or (self / x) == x
end
end
return list.sort
end

end

####################

unless ARGV.length == 1
puts "Usage: #{$0} <max_value>"
end
max_value = ARGV.shift.to_i
(1..max_value).each { |n| puts n if n.weird? }

 

[Adam Shelly]

Here's mine.
I started out with very straightforward programming, but ended up
making it muddier as I optimized. I also implemented a bunch of
functions that I figured I could probably find alread written if I
looked, but I figured they were good exercises : Integer#factors,
Integer#divisors, Array#all_combinations....

I thought it was pretty fast, especially compared to my initial
implementation. Then I timed Ryan's on my machine... Oh well. I
enjoyed the challenge.

-Adam

---
class Integer
def weird?
(d =3D divisors).pop #remove self (which is always last)
d.sum > self &&
!d.quick_find_subset_with_sum(self) && #weed out most
!d.find_subset_with_sum(self) #confirm the rest
end

def divisors
factors.all_combinations.uniq.inject([]){|result,combo|
result << combo.product
}.sort.uniq
end

def factors
value, candidate =3D self, 3
factors =3D [1]
while value % 2 =3D=3D 0
factors << 2
value /=3D 2
end
while candidate <=3D Math.sqrt(value)
while value % candidate =3D=3D 0
factors << candidate
value /=3D candidate
end
candidate +=3D 2
end
factors << value if value !=3D 1
factors
end
end


class Array
def product
inject(1){|p,v| p*v}
end
def sum
inject(0){|s,v| s+v}
end
def all_combinations
ComboIndexGenerator.new(self.size).inject([]) {|result, index_set|
result << values_at(*index_set)
}
end

#this was my first attempt, which was straightforward,
# but slow as heck for large sets
def slow_find_subset_with_sum n
return nil if sum < n
all_combinations.each {|set|
return set if set.sum =3D=3D n
}
nil
end

#this is my second attempt which is fast but misses some subsets.
#but it is useful for quickly rejecting many non-weird numbers.
def quick_find_subset_with_sum n
a =3D self.sort.reverse
sum,set =3D 0,[]
a.each {|e|
if (sum+e <=3D n)
sum+=3De
set<<e
end
return set if sum =3D=3D n
}
nil
end

#this one works pretty quickly...
#it never tests subsets which are less than the sum,
#and keeps track of sets it has already calculated
def find_subset_with_sum n
possibilities, seen =3D [self],{}
until possibilities.empty?
candidate =3D possibilities.pop
diff =3D candidate.sum - n
return candidate if diff =3D=3D 0
break if diff < 0
candidate.each_with_index{|e,i|
break if e > diff
new_cand =3D (candidate.dup)
new_cand.delete_at(i)
return new_cand if e =3D=3D diff
possibilities << new_cand if !seen[new_cand]
seen[new_cand]=3Dtrue
}
end
nil
end
end


#this class generates an all the possible combinations of n items
#it returns an array with the next combination every time you call #next
class ComboIndexGenerator
include Enumerable
def initialize nitems
@n =3D nitems
@max =3D 2**@n
@val=3D0
end
def to_a
return nil if @val=3D=3D@max
(0..@n).inject([]){|a,bit| a<<bit if @val[bit]=3D=3D1; a}
end
def next
@val+=3D1 if @val<@max
to_a
end
def each &b
yield to_a
while (n=3Dself.next)
yield n
end
end
end


if $0 =3D=3D __FILE__

if ARGV.length < 1
puts "Usage: #$0 <upper limit>"
exit(1)
end

puts "Weird numbers up to and including #{ARGV[0]}:"
70.upto(ARGV[0].to_i) do |i|
puts i if i.weird?
end
end

 

[Brian Schröder]

Here is my solution, I don't think it is as fast as the others, but it
does never calculate a list of divisors. It scales quite badly

max time
----------------
1000 0m0.714s
2000 0m2.756s
3000 0m6.351s
4000 0m13.404s
5000 0m16.806s
6000 0m27.031s
7000 0m33.482s
8000 0m44.111s
9000 0m54.781s
10000 1m6.179s

bschroed@black:~/svn/projekte/weird-numbers$ cat weird-numbers-be.rb
#!/usr/bin/ruby

# Break early version, checking if a number is weird
def weird_number(n)
d =3D r =3D s =3D nil
sum =3D 0
subset_sums =3D Hash.new
subset_sums[0] =3D true
for d in 1...n
next unless n % d =3D=3D 0
# Calculate sum of all divisors
sum +=3D d
# Calculate sums for all subsets
subset_sums.keys.each do | s |
return false if s + d =3D=3D n
subset_sums[s + d] =3D true
end
end
sum > n
end

def weird_numbers(range)
range.select { | n | weird_number(n) }
end

# Argument parsing
raise "Input exactly one number" unless ARGV.length =3D=3D 1

max =3D ARGV[0].to_i

# Call it
puts weird_numbers(1..max)

cheers,

Brian

 

[Zed Lopez]

I was impressed when I started going through 1..1000 in under 15
seconds, so this is much slower than others report. I'm just going to
tell myself you all have much faster computers, and go to bed.

require 'set'

class Subsets
def initialize(set, start)
@set = set.to_a.uniq.sort
@num_elements = start - 1
@map = {}
@set.each_with_index {|k, v| @map[k] = v+1}
end

# returns each subset, in turn. Returns nil when there are no more
def succ
if @combo == nil or @combo == @set[-@num_elements..-1]
return nil if (@num_elements +=1) > @set.length
@combo = @set[0,@num_elements]
else
index = (1..@num_elements).find {|i| @combo[-i] < @set[-i]}
@combo[-index, index] = @set[@map[@combo[-index]], index]
end
@combo
end

def find
while(x = succ)
break if yield x
end
x
end
end

class Integer

def proper_divisors
return [] if self < 2
div = Set.new [1]
2.upto(Math.sqrt(Float.induced_from(self)).to_i) {|i|
quotient, modulus = self.divmod(i)
div.merge([i,quotient]) if modulus.zero?
}
div.to_a.sort
end

def abundant?
self > 11 and [0].concat(proper_divisors).inject {|sum,n| sum += n}

self

end

def semiperfect?
return nil if self < 6
subsets = Subsets.new(proper_divisors, 2)
subsets.find {|subset| [0].concat(subset).inject {|sum,n| sum += n}
== self }
end

def weird?
self > 69 and abundant? and not semiperfect?
end
end

n = gets.strip
exit if n =~ /\D/ or n !~ /[^0]/
p (1..n.to_i).find_all {|i| i.weird? }