ProjectEuler-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 + 2x12
15 = 7 + 2x22
21 = 3 + 2x32
25 = 7 + 2x32
27 = 19 + 2x22
33 = 31 + 2x12

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<i])/2)
    if (any(round(x) == x)) {
        next
    } else {
        cat (i, "\n")
    }
}
p5rn7vb

Related Posts

  1. project euler-Problem1-50 | YGC United States Unknow Browser Unknow Os - pingback on November 9, 2011 at 3:49 pm

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>