Problem 46

Projekt Euler w Ruby
1

Problem 46

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

It turns out that the conjecture was false.

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

2

[code=ruby]#!/usr/bin/env ruby

p + 2*a^2 = n

$cache = { }

def prime?(n)
return false unless n >= 2
unless $cache.has_key?(n)
$cache[n] = !(2…Math.sqrt(n).floor).detect { |d| n%d == 0 }
else
$cache[n]
end
end

x = 3
until !(1…Math.sqrt(x/2).floor).detect { |a| prime?(x-2aa) } && !prime?(x)
x += 2
end
p x[/code]