Reply to thread

Message

[QUOTE="Brian Schröder, post: 4495192"]
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
[/QUOTE]

Verification