ProjectEuler-Problem 46

June 21, 2011
By

(This article was first published on YGC, and kindly contributed to R-bloggers)

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 + 212
15 = 7 + 222
21 = 3 + 232
25 = 7 + 232
27 = 19 + 222
33 = 31 + 212

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?

—————-

Referring to http://learning.physics.iastate.edu/hodges/mm-1.pdf, this problem is very famous.

Using brute-force is the solution I can only think of. Surprisingly, it turns out very fast.

?View Code RSPLUS
 1 2 3 4 5 6 7 8 9 10 11 12 13 14  `require(gmp) n <- 1:10000 p <- n[as.logical(isprime(n))]   for (i in seq(3,10000,2)) { if (any(p==i)) next x <- sqrt((i-p[p