# Solutions for Problem 46

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

## Ruby by tomchristmas

Runtime: 3.411s (on aglaope). A *marked* improvement on the previous version! All I did was rewrite the prime generator so that it didn't re-generate all of the primes every time and 'bingo-bongo' (as Brian Stephenson would say), you've got a 15-fold improvement in execution!

```def prime_list(pl, max)
p = pl
min = pl.nitems > 0 ? pl.last : 2

min.upto(max){|x|
c = 0
prime = true

while c < p.length && prime
prime = false if (x % p[c] == 0)
c += 1
end
p << x if prime
}

return p
end

def is_composite?(num)
comp = false

2.upto(num/2){|n|
comp = true if num % n == 0
}

return comp
end

c = 1
composite_found = false
pl = []

while !composite_found
if is_composite?(c)

goldbach_found = false
pl = prime_list(pl.dup, c)

pl.each{|p|
d = Math.sqrt((c - p)/2.0)
dd = (d.floor == d.ceil) ? (c - p) : 0
if c == p + dd
goldbach_found = true
puts "#{c} = #{p} + 2 x #{d}^2"
end
}
composite_found = true if !goldbach_found
end
c += 2 if !composite_found
end

puts c
```

## Python by Althalus

Runtime: 4.1s

```import primeFunctions

limit = 10000
primes = primeFunctions.genPrimes(limit)
squares = [x*x*2 for x in range(1,100) if x*x < limit]

for x in range(3,limit,2):
if x not in primes: