# How to find out if there 7 prime subtractors of a number

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

• Exactly $7$ prime numbers, or adding $\le 7$ prime numbers? Mar 30, 2017 at 14:51
• @DietrichBurde exactly 7 Mar 30, 2017 at 14:51
• Then any $n<14$ is impossible. Mar 30, 2017 at 14:52
• @DietrichBurde i agree Mar 30, 2017 at 14:52
• Seven same prime numbers or they can be distinct? Mar 30, 2017 at 14:58

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$.

• The strong Goldbach conjecture is unproved! Mar 30, 2017 at 14:59
• @ConnorHarris You are right, no need to use strong Goldbach. Mar 30, 2017 at 15:00
• @MayankM. it definitely does,i am waiting for stackexchange to let me accept this heuristic answer Mar 30, 2017 at 15:00

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$.

• Any odd $n$ is the sum of three primes! Mar 30, 2017 at 14:58
• @DietrichBurde ooh, you're right. Fixed. Mar 30, 2017 at 15:00

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.

• Number can be up to 10^15,so brute force won't work Mar 30, 2017 at 15:05
• 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? Mar 30, 2017 at 15:07
• I need decomposition Mar 30, 2017 at 15:12
• 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. Mar 30, 2017 at 15:18