[QUIZ] Weird Numbers (#57) Solution

[Hampton]

Here is my solution. Its not the most beautiful thing in the world, but
its effective.

-----------------------------------------

def weirdo_exhaustive(from, max)
puts "none found" and return 0 if max < 70
(from..max).each do |num|
if num % 2 == 0
list, sum= [], 0
(1...num).each do |div|
list << div and sum += div if num % div == 0
end
puts "==" + num.to_s if sum > num and has_sum(num, list) == false
end
end
end

def has_sum(num, array)
if array.is_a? Integer then return false end
sum = 0
array.each do |val| sum += val end
if sum === num then return true end
#this next line saves a BUNCH of checks.
if sum < num then return false end
array.each do |removeme|
copy = array.dup
copy.delete(removeme)
if copy.size > 1 and has_sum(num, copy) == true then return true
end
end
return false
end

----------------------------------------

It took a good number of optimizations that make it less pretty, but
much faster. The first time I ran it it took 4 hours to reach 1,000.
Its faster than that now, but its still somewhere around O(3^n).

SO... I thought of a way to speed up the algorithm a lot! So, with a
*few* more optimizations, here's the weirdo_fast algorithm.

-------------------------------------------------------

def weirdo_fast(max)
list = [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
83312,91388,113072,243892,254012,338572,343876,388076, #
519712,539744,555616,682592,786208,1188256,1229152,1713592, #
1901728,2081824,2189024,3963968 ]
list.each do |num|
puts num if num <= max
end
if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1],
max) end
end

-----------------------------------------------------

A little faster, eh? It will start exhaustively searching if your max
is out of its range.... but I warn you, my computer has been
calculating 3963970 for the last 24 hours. And, not the range up to it,
just that number. Remember, its 3^3963970 = 62_286_091_158_062_773_000
which takes a minute to calculate. Well, with my other optimizations,
its a tad faster than that.... a tad.

I'm interested to see if anyone else found a much better way to test
for has_sum(num, array). It seems to me like there must be a clever
mathematical trick for getting the job done. Or perhaps the only clever
way is my "fast" algorithm. But, that's not even that clever.

-Hampton Catlin.
(e-mail address removed)

 

[Simon Strandgaard]

Here is my solution. Its not the most beautiful thing in the world, but
its effective.

[snip]

I could not find any fast solution..

--
Simon Strandgaard


# Weird Numbers
# Simon Strandgaard <[email protected]>

def divisors(value)
ary =3D []
(value/2).times do |i|
div =3D i + 1
ary << div if value % div =3D=3D 0
end
ary
end

$bits =3D []
32.times do |bit|
$bits << 2 ** bit
end

def has_subset_equal_to(divs, value)
pairs =3D divs.zip($bits)
1.upto(2 ** divs.size - 1) do |i|
sum =3D 0
pairs.each{|div,b| sum+=3Ddiv if (i&b)>0 }
return true if sum =3D=3D value
end
false
end

def find_weird_numbers(range_min, range_max)
ary =3D []
range_min.upto(range_max) do |value|
divs =3D divisors(value)
sum =3D divs.inject(0){|a,b|a+b}
ary << [value, divs] if sum > value
end
res =3D []
ary.each do |value, divs|
if !has_subset_equal_to(divs, value)
puts "##{value} is a WEIRD NUMBER"
res << value
else
puts "##{value} is nothing"
end
end
p res
end

p find_weird_numbers(1, 100)

 

[James Edward Gray II]

SO... I thought of a way to speed up the algorithm a lot! So, with a
*few* more optimizations, here's the weirdo_fast algorithm.

-------------------------------------------------------

def weirdo_fast(max)
list = [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
83312,91388,113072,243892,254012,338572,343876,388076, #
519712,539744,555616,682592,786208,1188256,1229152,1713592, #
1901728,2081824,2189024,3963968 ]
list.each do |num|
puts num if num <= max
end
if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1],
max) end
end

Bingo.

I was actually thinking of screen scraping them from on of the
encyclopedias mentioned in the quiz thread, but I like this even better.

Nice job.

James Edward Gray II

 

[Hampton]

James,

I was starting to do that... I was building my HTTP object, and I
noticed how hard it was going to be to parse...... so I said screw it,
I'll make it easier.

And FASTER!

It would even run with 6k of ram!

-h.

 

[Ryan Leavengood]

Here is my solution. It is pretty fast, but not quite as fast as
Rob's. For example his takes 6.797 seconds to calculate all weird
numbers up to 50000, whereas mine takes 7.375. Our solutions are quite
similar. Some of the other solutions are REALLY SLOW though. Probably
one of the biggest optimizations was using the square root of a given
number to calculate half the divisors, then use those to get the other
half. For example if 2 is a divisor of 14, then so is 14/2 =3D 7. For
big numbers this can be a massive speed-up.

Ryan

class Array
def sum
inject(0) do |result, i|
result + i
end
end
end

class Integer
def weird?
# No odd numbers are weird within reasonable limits.
return false if self % 2 =3D=3D 1
# A weird number is abundant but not semi-perfect.
divisors =3D calc_divisors
abundance =3D divisors.sum - 2 * self
# First make sure the number is abundant.
if abundance > 0
# Now see if the number is semi-perfect. If it is, it isn't weird.
# First thing see if the abundance is in the divisors.
if divisors.include?(abundance)
false
else
# Now see if any combination sums of divisors yields the abundance.
# We reject any divisors greater than the abundance and reverse the
# result to try and get sums close to the abundance sooner.
to_search =3D divisors.reject{|i| i > abundance}.reverse
sum =3D to_search.sum
if sum =3D=3D abundance
false
elsif sum < abundance
true
else
not abundance.sum_in_subset?(to_search)
end
end
else
false
end
end

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

def sum_in_subset?(a)
if self < 0
false
elsif a.include?(self)
true
else
if a.length =3D=3D 1
false
else
f =3D a.first
remaining =3D a[1..-1]
(self - f).sum_in_subset?(remaining) or sum_in_subset?(remaining)
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]}:"
70.upto(ARGV[0].to_i) do |i|
puts i if i.weird?
end
end

 

[Hampton]

Mine's *really* fast up to 3,963,968.... then it slows down just a
*tad*.

For instance, mine can do up to 50,000 in 0.0012 seconds on a 300mhz
processor.
And it can do 3 million in 0.014338 seconds.

Actually, I think I can speed up my exhausted.... {walks away to code}

 

[Ryan Leavengood]

SO... I thought of a way to speed up the algorithm a lot! So, with a
*few* more optimizations, here's the weirdo_fast algorithm.

-------------------------------------------------------

def weirdo_fast(max)
list =3D [ 70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
83312,91388,113072,243892,254012,338572,343876,388076, #
519712,539744,555616,682592,786208,1188256,1229152,1713592, #
1901728,2081824,2189024,3963968 ]
list.each do |num|
puts num if num <=3D max
end
if max > list[list.size-1] then weirdo_exhaustive(list[list.size-1],
max) end
end

Bingo.

I was actually thinking of screen scraping them from on of the
encyclopedias mentioned in the quiz thread, but I like this even better.

Nice job.

I don't know, I think this is cheating. Plus he is missing a bunch of
weird numbers in his list.

Ryan

 

[Ryan Leavengood]

Mine's *really* fast up to 3,963,968.... then it slows down just a
*tad*.

For instance, mine can do up to 50,000 in 0.0012 seconds on a 300mhz
processor.
And it can do 3 million in 0.014338 seconds.

Except your solution is missing tons and tons of valid weird numbers.

Ryan

 

[horndude77]

Here's my solution. It looks pretty close to others. Not too fast, but
it gets the job done. I think after I get a chance to look at other
solutions I can write a some of this better.

class Integer
def divisors
divs = []
1.upto(Math.sqrt(self).to_i) do |i|
divs += [i ,self/i].uniq if (self%i == 0)
end
divs.sort.reverse #reverse speeds things up a bit
end

def weird?
divs = self.divisors - [self]
return false if divs.sum < self
divs.each_combination do |comb|
return false if comb.sum == self
end
return true
end
end

class Array
def each_combination
(2**self.length).times do |comb|
curr = []
self.length.times do |index|
curr << self[index] if(comb[index] == 1)
end
yield curr
end
end

def sum
inject(0) { |sum, i| sum + i }
end
end

max = (ARGV[0] || 10000).to_i

max.times do |i|
puts i if i.weird?
end

-----HornDude77

 

[Simon Strandgaard]

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

nice and speedy.. mine is awful and slow.

 

[Jannis Harder]

Here is my solution (it's optimized for statistics not for speed).
I don't use things like someone tried all odd numbers up to 10**18
because doesn't change the algorithm.. I'll use that in my speed
optimized version..

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


=begin

References:

http://en.wikipedia.org/wiki/Divisor_function
http://en.wikipedia.org/wiki/Weird_number
Eric W. Weisstein. "Weird Number." From MathWorld--A Wolfram Web
Resource. http://mathworld.wolfram.com/WeirdNumber.html
Eric W. Weisstein. "Semiperfect Number." From MathWorld--A Wolfram
Web Resource. http://mathworld.wolfram.com/SemiperfectNumber.html
Eric W. Weisstein. "Perfect Number." From MathWorld--A Wolfram Web
Resource. http://mathworld.wolfram.com/PerfectNumber.html
Eric W. Weisstein. "Divisor Function." From MathWorld--A Wolfram Web
Resource. http://mathworld.wolfram.com/DivisorFunction.html
Eric W. Weisstein. "Mersenne Prime." From MathWorld--A Wolfram Web
Resource. http://mathworld.wolfram.com/MersennePrime.html
Eric W. Weisstein. "Abundance." From MathWorld--A Wolfram Web
Resource. http://mathworld.wolfram.com/Abundance.html

=end


class Integer
$prime_factors = Hash.new # we cache prime factors...
def prime_factors position = -1
if cached = $prime_factors[self] # cached?
return cached # yes
end

if self == 1 # we have 1 we are done
return $prime_factors[self]=[] # return no factors
elsif position<0 # we havn't reached factor 5 yet
if self&1 == 0 # test factor 2
return $prime_factors[self]=[2,*(self>>1).prime_factors]
elsif self%3 == 0 # and factor 3
return $prime_factors[self]=[3,*(self/3).prime_factors]
end
end

loop do
position+=6 # increment position by 6
if position*position > self # we have a prime number return it
return $prime_factors[self]=[self]
elsif (quo,rem = divmod(position)) and rem.zero? # test 6n-1
return $prime_factors[self]=[position,*quo.prime_factors
(position-6)]
elsif (quo,rem = divmod(position+2)) and rem.zero? # and 6n+1
return $prime_factors[self]=[position+2,*quo.prime_factors
(position-6)]
end
end
end

def distinct_prime_factors # rle encode the prime factors
distinct_prime_fac = Hash.new{0} # setup the hash
prime_factors.each do |prime_factor| # fill it
distinct_prime_fac[prime_factor]+=1
end
distinct_prime_fac.to_a.sort_by{|(fac,count)|fac} # and return
it as sorted array
end


def divisors # get the divisors (not needed for divisor sum)
divs = [] # store divisors here
n = 1 # start with 1
loop do
break if n*n > self # done
if (qua,rem = divmod(n)) and rem.zero? # test for division
divs << qua # add divisors
divs << n
end
n+=1
end
divs.uniq.sort[0..-2] # we don't want self
end



def semi_perfect? deficient=false # final test
cached_abundance = abundance
return deficient if cached_abundance < 0 # deficient return the
argument
return true if cached_abundance == 0 # perfect => semi perfect too

possible_values = {0=>true} # store all possible values in a hash
divs = self.divisors # get the divisors

div_sum_left = divs.inject(0){|a,b|a+b} # get the divisor sum

pos_2 = div_sum_left - self # this is a possibility too

divs.reverse.each do |div| # for each divisor
possible_values.keys.each do |value| # and each possible value
if value+div_sum_left < self # check wether it can reach the
number with the divisors left
possible_values.delete(value) # if not delete the number
(huge speedup)
end

new_value = value+div # we create a new possible value
including the divisor

if new_value == self or new_value == pos_2 # if it is the
number it's semi perfect
return true
elsif new_value < self # if it's less than the number it
could be semi perfect
possible_values[new_value]=true # add it to the possiblities
end # if it's more than the value we can ignore it
end
div_sum_left-=div # the current divisor isn't left anymore
end
false # we found no way to compose the number using the divisors
end


def restricted_divisor_sum # uses the formular from wikipedia
distinct_prime_factors.map do |(fac,count)|
comm_sum = 1
comm_mul = 1
count.times do
comm_sum += (comm_mul*=fac)
end
comm_sum
end.inject(1){|a,b|a*b}-self
end

def perfect? # perfect numbers have the form 2**(n-1)*(2**n-1)
where n is prime (and small )
return false if self&1 == 1 # it isn't known weather there are
odd perfect numbers.. but it's irrelevant for my algorithm
doubled = self * 2 # the perfect number is a triangular number
of the form (n*(n+1))/2
doubled_root = Math.sqrt(doubled).floor # if we double it and
take the floored square root we get n
return false unless doubled == doubled_root*(doubled_root+1) #
if we don't get n it isn't perfect
doubled_root_string = (doubled_root+1).to_s(2) # from the first
line we know n+1 has to be of the form 2**n
return false unless doubled_root_string.count('1')==1 # we check
that here
return false unless
(doubled_root_string.size-1).prime_factors.size == 1 # and n ha to be
a prime
return false unless self.abundance == 0 # if it passes all the
earlier test we check it using the abundance
true # and if it passes it's perfect
end

def abundance
self.restricted_divisor_sum-self
end
end


require 'benchmark'

max_num = Integer(ARGV.shift||'1000') rescue 1000 # read a number
from the command line

new_semi_perfects = [] # store semi perfect numbers that can't be
constructed using other semi perfect numbers



STDOUT.sync = true
puts "Weird Numbers Up To #{max_num}:"


#begin_stat
perfect_count = 0
composed_semi_perfect_count = 0
new_semi_perfect_count = 0
weird_count = 0
deficient_count = 0


record_nums = (1..80).map{|n|max_num*n/80}

record_nums_left = record_nums.dup
next_record = record_nums_left.shift

recorded_times = []


init_time = [Benchmark.times,Time.now]

min_odd = 10**17


#end_stat

(1..max_num).each do |test_num| # counting loop



if test_num == next_record #stat
recorded_times << [Benchmark.times,Time.now] #stat
next_record = record_nums_left.shift #stat
end #stat

if test_num.perfect? # it's perfect
new_semi_perfects << test_num
perfect_count += 1 #stat
next
end

do_next = false
new_semi_perfects.each do |semi_per|
if test_num % semi_per == 0 # is it possible to compose the
current number using a semi-perfect number?
do_next = true # yes
composed_semi_perfect_count += 1 #stat
break
end
end
next if do_next
# no


case test_num.semi_perfect? nil # we don't care about deficient
numbers
when true # but we care about semi perfects
new_semi_perfects << test_num
new_semi_perfect_count += 1 #stat
when false # and even more about abundand non semi perfects
puts test_num
weird_count += 1 #stat
else #stat
deficient_count += 1 #stat
end

end

#end

#begin_stat

final_time = [Benchmark.times,Time.now]

digit_length = max_num.to_s.size

def form_float(num)
"%12s" % ("%im%#{7}ss" % [(num/60).floor,("%.4f" % (num %60))]).tr
(" ","0")
end

def rel(x,y)
"%#{y.to_s.size}i (%6s%%)" % [x,"%3.2f" % (x/y.to_f*100)]
end



puts "Stats"
puts "Time:"
puts "- User: "+form_float(ut = final_time.first.utime -
init_time.first.utime)
puts "- System: "+form_float(st = final_time.first.stime -
init_time.first.stime)
puts "- U+S: "+form_float(ut+st)
puts "- Real: "+form_float(final_time.last - init_time.last)
puts
puts "Numbers:"
puts "- Total "+rel(max_num,max_num)
puts "- Weird "+rel(weird_count,max_num)
puts "- Perfect "+rel(perfect_count,max_num)
puts "- Deficient "+rel(deficient_count,max_num)
puts "- Abundand "+rel(abundand_count = max_num-perfect_count-
deficient_count,max_num)
puts "- Semi-Perfect "+rel(abundand_count-weird_count,max_num)
puts " (w/o perfects)"
puts ""
puts "- Passed 1st "+rel(max_num-perfect_count,max_num)
puts " (perfect test)"
puts "- Passed 2nd "+rel(new_semi_perfect_count+weird_count
+deficient_count,max_num)
puts " (composed test)"
puts "- Passed 3rd "+rel(new_semi_perfect_count+weird_count,max_num)
puts " (deficient test)"
puts "- Uncomposed "+rel(new_semi_perfects.size,max_num)
puts " (semi-perfects that arn't a multiply of another semi-perfect)"
puts

if recorded_times.size >= 80
puts "Graphs:"
puts

process_plot = []
real_plot = []

first_ustime = init_time.first.utime+init_time.first.stime
first_realtime = init_time.last

recorded_times.each do |(process_time,realtime)|
process_plot << process_time.utime+process_time.stime -
first_ustime
real_plot << realtime - first_realtime
end



max_process = process_plot.last
step_process = max_process / 22

max_real = real_plot.last
step_real = max_real / 22



def plot(plot_data,max,step)
22.downto(0) do |k|
res = ""
res = form_float(max) if k == 22
while res.size != plot_data.size
val = plot_data[res.size]
lower_range = k*step
res << ( val >= lower_range ? (val < lower_range+step ?
'#' : ':') : ' ' )
end
puts res
end
end

puts "Y: Realtime X: Number"
plot(real_plot,max_real,step_real)
puts "%-40s%40s"% [1,max_num]
puts "Y: System+Usertime X: Number"
plot(process_plot,max_process,step_process)
puts "%-40s%40s"% [1,max_num]
puts
end
#end_stat


__END__

 

[Edward Faulkner]

--pWyiEgJYm5f9v55/
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

I've got an optimization I haven't seen anyone else use yet. My
solution is roughly 20% faster than Ryan's.

The trick is that any number of the form k*(2^m)*p where m > 1 and p
is a prime such that 2 < p < 2^(m+1) is semiperfect (according to
wikipedia). This rules out many numbers, and its cheaper than a
thorough search of subsets.

#!/usr/bin/ruby

def weird(max)
primes =3D sieve(max*2)
70.step(max,2){|n|=20
puts n if weird?(n,primes)
}
end

def weird?(n,primes)
divs =3D divisors(n)
abund =3D divs.inject(0){|a,b| a+b} - n
return false if abund <=3D 0
return false if spfilter(n,primes)
return false if divs.include? abund
smalldivs =3D divs.reverse.select{|i| i < abund}
not sum_in_subset?(smalldivs,abund)
end

def sum_in_subset?(lst,n)
#p [lst,n]
return false if n < 0
return true if lst.include? n
return false if lst.size =3D=3D 1
first =3D lst.first
rest =3D lst[1..-1]
sum_in_subset?(rest, n-first) or sum_in_subset?(rest,n)
end


def divisors(n)
result =3D []
sr =3D Math.sqrt(n).to_i
(2 .. sr).each {|d|
if n.modulo(d) =3D=3D 0
result << d
end
}
return [1] if result.empty?
hidivs =3D result.map {|d| n / d }.reverse
if hidivs[0] =3D=3D result[-1]
[1] + result + hidivs[1..-1]
else
[1] + result + hidivs
end
end


def spfilter(n,primes)
m =3D 0
save_n =3D n
while n[0]=3D=3D0
m +=3D 1
n >>=3D 1
end
return false if m =3D=3D 0
low =3D 2
high =3D 1 << (m+1)
primes.each {|p|
return false if p > high
if p > low
return true if n%p =3D=3D 0
end
}
raise "not enough primes while checking #{save_n}"
end

# Sieve of Eratosthenes
def sieve(max_prime)
candidates =3D Array.new(max_prime,true)
candidates[0] =3D candidates[1] =3D false
2.upto(Math.sqrt(max_prime)) {|i|
if candidates
(i+i).step(max_prime,i) {|j| candidates[j] =3D nil}
end
}
result =3D []
candidates.each_with_index {|prime, i| result << i if prime }
result
end


weird(ARGV[0].to_i)

regards,
Ed

--pWyiEgJYm5f9v55/
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDk0A4nhUz11p9MSARAoNYAJwL019QJvPwSZKfz07Jb8YoVQE0HQCfcnNB
uYGSx5ixnDXq4k+7FqlvWJw=
=Wzc9
-----END PGP SIGNATURE-----

--pWyiEgJYm5f9v55/--

 

[James Edward Gray II]

I don't know, I think this is cheating.

It's cheating to get correct answers quickly?

Plus he is missing a bunch of weird numbers in his list.

I haven't compared the Array in question with the posted sequences.
Perhaps it's not very complete. Let me ask you this though, since
we're talking about this: Which is easier to debug, the sequence
list or a broken calculation solution?

Didn't the solution also brute force answers when it left its list of
known numbers?

One last question: How well does your presumably fast solution do
when it goes beyond the listed sequence? Does it still find lots of
answers, quickly?

I'm really not trying to be mean here and I apologize if I'm coming
off that way.

I think what Hampton hit on is a simple cache optimization. It's
fast and very effective. I don't think we should be so quick to toss
it out as a viable approach...

James Edward Gray II

 

[Kenneth Collins]

#!/usr/bin/env ruby
#
# Ruby Quiz Weird Numbers solution.
#
# I found only two significant optimizations:
# 1. Use continuations when generating the powerset of
# divisors to sum. Evaluate each sum immediately
# and break upon determining the number is semiperfect.
# 2. Sort the divisors in descending order so that
# subsets involving the larger divisors are considered
# first.
#
# On my machine, generating results for numbers up to 5000
# took less than a minute. Generating results up to 12000
# took almost twenty minutes.
#
# This powerset implementation was inspired by a post to
# Ruby-Talk by Robert Klemme on May 14, 2004:
#
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/100258?help-en
#
#

module Enumerable

def powerset
for element_map in 0...(1 << self.length) do
subset = []
each_with_index do |element, index|
subset << element if element_map[index] == 1
end
yield subset
end
end

end

class Array

def sum
return self.inject { |total,x| total += x }
end

end

class Integer

def weird?
divs = self.divisors.reverse
return false unless divs.sum > self
divs.powerset { |subset| return false if subset.sum == self }
return true
end

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

end

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

(1..5000).each { |n| puts n if n.weird? }

 

[Hampton]

Which ones are missing?

My set is.... [
70,836,4030,5830,7192,7912,9272,10792,17272,45356,73616, #
83312,91388,113072,243892,254012,338572,343876,388076, #
519712,539744,555616,682592,786208,1188256,1229152,1713592, #
1901728,2081824,2189024,3963968 ]

 

[Ryan Leavengood]

It's cheating to get correct answers quickly?

Well something had to generate those answers in the first place, and
for that I'd take my, Rob, or Edward's solution any day.

I haven't compared the Array in question with the posted sequences.
Perhaps it's not very complete. Let me ask you this though, since
we're talking about this: Which is easier to debug, the sequence
list or a broken calculation solution?

Well I certainly debugged mine by looking at the pre-existing list,
which was useful. But the fact that his list was missing things really
caused me pause, because if someone depended on that list to be
accurate, they would be in trouble.

Didn't the solution also brute force answers when it left its list of
known numbers?

Yes but his brute-force algorithm is extremely slow, and his list is wrong.

One last question: How well does your presumably fast solution do
when it goes beyond the listed sequence? Does it still find lots of
answers, quickly?

Of the three fastest solutions so far (Edward's, Rob's and mine), all
continue to generate answers at a similar rate, consistently. For
example, to generate up to 100000, the time was 16.687, 17.281 and
18.469 seconds (in the order listed above, i.e. mine is slowest.)
Since there are 204 weird numbers between 0 and 100000, each algorithm
generates about 11-12 per second.

I'm really not trying to be mean here and I apologize if I'm coming
off that way.

Well I've probably come off as mean to Hampton, and I don't really
want to come off that way either. But it does rub me the wrong way to
have someone call their solution fast when the solution is WRONG.

I think what Hampton hit on is a simple cache optimization. It's
fast and very effective. I don't think we should be so quick to toss
it out as a viable approach...

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.

Ryan

 

[Hampton]

I did mine with a good dose of humor.

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.

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.

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!

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=A002975
As opposed to this:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006037

My mistake....

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

-hampton c.

 

[Hampton]

Ryan-

It was supposed to be a funny statement. I even used a

And of course calling my "exhaustive" (hint in the name) a *tad* slower
is absolutely, 100% absurdist.

I used the wrong AO list as mentioned in my other response. I apologize
to all those who my not paying attention to "primitive weird numbers"
and "weird numbers" hurt in the process.

This quiz is for *fun* not competition.

-hampton.

PS: For further clarification, about 50% of this message is also
supposed to be somewhat amusing.

 

[James Edward Gray II]

It's cheating to get correct answers quickly?

Well something had to generate those answers in the first place, and
for that I'd take my, Rob, or Edward's solution any day.
[snip]

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.

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

James Edward Gray II

 

[James Edward Gray II]

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.

It is a valid technique. It can probably be used to make the fastest
posted solutions even faster. You're example maybe wasn't the ideal
representation, but I think Ryan hit on a great one in his last message.

That's all I was saying. Don't overlook what can help!

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

<laughs> Seriously, I didn't mean to upset a single soul. My truest
apologies if I did.

James Edward Gray II