**Goldbach’s other conjecture**

**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×12

15 = 7 + 2×22

21 = 3 + 2×32

25 = 7 + 2×32

27 = 19 + 2×22

33 = 31 + 2×12

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?

Couldn’t think how I would program this at first. So I started solving this manually by hand on paper. Tried to find the solution for 35, then 39 and so on. While doing this I observed myself of how I am solving the problem. After doing it for 3-4 numbers I was able to find a pattern. So now, I had an idea to write a program for it.

Every odd composite number can be represented in the form :

Odd_Composite_Number = Prime_Number + (2 X (Some_Number)^2)

So basically, the logic is we start our numbers from 35, since till 33 we already know that it is not the answer as given in the question. We first need to check if a number is a composite number. How do we check that? We already have a function which checks if a number is prime. If the number is prime then we just increase the count by 2 and move on to the next number. Now if a number is odd composite then we get all the primes under that number as the prime number component can be any number lesser than the current number. Now `Some_Number`

component can be any number from 1. We just check that the complete sum doesn’t cross the current number we are checking. If it does, then we stop execution and move on to the next iteration.

get_answer_for_problem46_v2 <- function() { start_num <- 33 flag = TRUE while(flag) { start_num = start_num + 2 if(is_prime(start_num)) next else { flag = FALSE primes <- get_primes_under_n(start_num - 2) square_number = 1 for (i in primes) { for (square_number in seq(start_num)) { current_sum = i + (2 * (square_number^2)) if (current_sum > start_num) break else if (current_sum == start_num) { cat(start_num, "=", i, "+ 2 X", square_number, "^2\n") flag = TRUE break } } if(flag) break } if(!flag) cat("The answer is : ", start_num, "\n") } } }

The outer `while`

loop runs until you find an odd composite number which cannot be represented in the format given in the question i.e till the time you find an answer. If the number is a prime number, then we skip that iteration from there itself. If it is not prime, then we get all the primes under that number and run two for loops from there. First loop iterates over each prime number and the other loop for each number from 1 till the sum doesn’t exceed the current number. Certain numbers can be represented in multiple ways. For example, number 69…

69 = 19 + 2 X 5 ^2 69 = 37 + 2 X 4 ^2 69 = 61 + 2 X 2 ^2 69 = 67 + 2 X 1 ^2

We do not need to know all the possible ways, it can represent a number. Even if it can represent in one way then that is enough for us to move ahead with next statement. Added some break statements so that we can stop the loop as soon as it encounters even one representation. I received a huge performance improvement when I did that.

system.time(get_answer_for_problem46_v1()) # user system elapsed # 193.71 1.00 197.95 system.time(get_answer_for_problem46_v2()) #user system elapsed #75.73 0.27 77.06

Also the code which I have written is a bit complicated and mind you it wasn’t written in one go. Everything was folded step by step to reach till here and print the final result.