I have a number and i want to find out if i can get that number by adding 7 prime numbers.How can i find that out?
Example
Number:14
Answer:2 2 2 2 2 2 2
Asked
Active
Viewed 41 times
1
Murad
- 361
- 2
- 13
-
Exactly $7$ prime numbers, or adding $\le 7$ prime numbers? – Dietrich Burde Mar 30 '17 at 14:51
-
@DietrichBurde exactly 7 – Murad Mar 30 '17 at 14:51
-
Then any $n<14$ is impossible. – Dietrich Burde Mar 30 '17 at 14:52
-
@DietrichBurde i agree – Murad Mar 30 '17 at 14:52
-
Seven same prime numbers or they can be distinct? – Mayank M. Mar 30 '17 at 14:58
-
@MayankM. can be different – Murad Mar 30 '17 at 14:58
-
If it was required that the primes be distinct, this would be a hell of a lot more interesting question, in my opinion. – Mr. Brooks Mar 30 '17 at 22:23
3 Answers
1
This is a consequence of the weak Goldbach conjecture, proved in 2013, that any odd $n \geq 7$ is the sum of three primes. Then any $n \geq 15$ is the sum of seven primes, namely the three primes that add up to $n-8$ and $2+2+2+2$ (if $n$ is odd), or the three primes that add up to $n-9$ and $2+2+2+3$ (if $n$ is even). The case $14 = 7 \times 2$ can be handled separately, so we have the result for $n \geq 14$.
Connor Harris
- 7,070
1
By the weak Goldbach conjecture, every odd number greater than $5$ can be expressed as the sum of three primes. So we have $n=p+q+r$. Now consider $N=n-2-2-2-2$ for $n\ge 9$. Then $N=2+2+2+2+p+q+r$ is the sum of $7$ primes. So every odd number $N\ge 14$ is the sum of seven primes. For the even case, use $N=n-2-2-2-3$.
Dietrich Burde
- 130,978
-
-
-
-
@MayankM. it definitely does,i am waiting for stackexchange to let me accept this heuristic answer – Murad Mar 30 '17 at 15:00
1
For n sufficiently large $n>=100$ probably less you can substract $2$ and $3$ conveniently to form odd number. Then applying the Weak Golbach Conjecture (which as far as I remember it was proved recently) it is always possible to decompose an odd number into the sum of three prime numbers.
When n is small you can do a brute force algorithm to find every decomposition and check whether it is valid or not.
Marcelo Fornet
- 315
-
-
Brute force on the first 100 numbers, the rest you know for sure can be decomposed. Are you interested in finding the decomposition? Or only in know if it can or can't be done? – Marcelo Fornet Mar 30 '17 at 15:07
-
-
You can try a greedy approach for this problem. Since you need to decompose it in 7 prime numbers, you can find one big prime less than n. And test if you can decompose $n-p$ into $6$ prime numbers. To find $p$ I recommend to iterate backward from n checking if that number is prime in $\sqrt n$ It will work fast since prime numbers are "well" distributed along natural numbers. – Marcelo Fornet Mar 30 '17 at 15:18