Problem statement
A conjecture (I rediscovered ?) related to Goldbach's one states that every integer above 2 can be written as the sum of at maximum two prime numbers and the number 1. The goal of this problem is to check this decomposition. Given a positive integer n as an input, your algorithm will return a vector of two primes, [p1, p2], plus potentially the number 1, [1, p1, p2], such that either n = p1 + p2 (case where n is an even number) or n = 1 + p1 + p2 (case where n is an odd number). This p vector will be sorted in ascending order : 1 < p1 < p2 < n. For n = 1 or n = 2 your algorithm should simply return n.
Examples (check the tests below for more)
- n = 3 => p = [1, 2] ;
- n = 7 => p = [2, 5] ;
- n = 17 => p = [1, 3, 13] ;
- n = 20 => p = [1; 19] ; % p1 may not be prime in this case
- n = 23 => p = [1, 3, 19] ;
- n = 60 => p = [1, 59] ; % p1 may not be prime in this case
- n = 1 => p = 1 ;
- n = 2 => p = 2;
Tips
Even if maybe not unique, there is always a solution. If you find a case withouit, at least you will have proven the conjecture to be false ! A simple way to start is to begin with seeking p2, the greater prime before n (even when n is prime itself. Then if the difference between n and this number is a prime number, you just have found p1. Else, add 1 and it should complete the sum.
Forbidden functions
- regexp
- str2num
- assignin
- echo
See also
Solution Stats
Problem Comments
2 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers16
Suggested Problems
More from this Author42
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Hi Nicolas, and thanks for this problem. Could you change assertion tests such that they test only the final sum, and that the numbers are either primes or 1. At the moment, my solutions to test cases 7, 8, 9 and 10 seem to be correct, but tests fail. What do you think? Below are my findings:
test 7
sum([1, 5, 11]) == 17
test 8
sum([1, 5, 17]) == 23
test 9
sum([1, 17, 19]) == 37
test 10
sum([1, 17, 29]) == 47
Ok, done. Tests successfully updated.