samskivert: Euler 046

10 August 2008

Problem 046:

object Euler46 extends EulerApp {
  def isgold (n :Int) = 1.to(Math.sqrt(n/2)).exists(s => isprime(n-2*s*s))
  def check (n :Int) :Int = if (isprime(n) || isgold(n)) check(n+2) else n
  println(check(3))
}

Fortunately this one is easier to disprove than Goldbach's other conjecture. If n = p + 2ss, we can simply try all values of s from 1 to the square root of n/2 and check whether n - 2ss is prime. If so, we try the next larger odd integer until we find the (surprisingly small) value that disproves the conjecture. I'm sure Euler would have disproved it more cleverly, but it also would have taken him more than 26 milliseconds.

©1999–2015 Michael Bayne