1
$\begingroup$

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

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

3 Answers 3

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ The strong Goldbach conjecture is unproved! $\endgroup$ Mar 30, 2017 at 14:59
  • $\begingroup$ @Murad This answer is I think fits your question. $\endgroup$
    – Mayank M.
    Mar 30, 2017 at 14:59
  • $\begingroup$ @ConnorHarris You are right, no need to use strong Goldbach. $\endgroup$ Mar 30, 2017 at 15:00
  • $\begingroup$ @MayankM. it definitely does,i am waiting for stackexchange to let me accept this heuristic answer $\endgroup$
    – Murad
    Mar 30, 2017 at 15:00
1
$\begingroup$

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

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

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .