# Euler Solution 46

### From ProgSoc Wiki

# 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: theanswer = True for prime in primes: if prime >= x: break if (x - prime) in squares: theanswer = False if theanswer: print x break