# How to turn number into sum of unique primes?

I have to find algorithm which find prime number less than $n$ which is sum of the largest amount of unique primes, for example for $n=81$, the answer is $79 = 3 + 5 + 7 + 11 + 13 + 17 + 23$. I have read about partitions and Goldbach's conjecture but it seems unhelpful.

• Sounds like an exercise in dynamic programming. – Henning Makholm Dec 17 '17 at 14:36
• If it's a programming exercise would be nice to know any constraints on $n$. – kingW3 Dec 18 '17 at 21:52
• @kingW3 It is a programming exercise. $n$ is natural without constraints but I was not told to make it work fast so I may assume that $n$ is not big. – Maciej Pankanin Dec 18 '17 at 22:03

Some thoughts

After the first split of $n$ into two or three unique primes, the problem becomes splitting larger primes into a list of smaller primes which is the problem I discuss below.

The minimum number of unique primes a larger prime can be split into is $2$ smaller primes, where $2$ is one of those unique primes e.g. $31=29+2$. If $2$ is not used the minimum number of primes a larger prime can be split into is $3$ primes e.g.

$$31=(23+5+3)=(19+7+5)=(17+11+3)=(13+11+7)$$

user477343 was playing with this idea here

We can now look at how to generate new primes by making the split into $3$ other primes and so on. The split into $2$ primes using $2$ can only be used once.

e.g. the smaller primes above split as follows

$$29=(19+7+3)=(17+7+5)=(13+11+5)$$ $$23=(13+7+3)=(11+7+5)$$ $$19=(17+2)=(11+5+3)$$ $$13=(11+2)$$ $$7=(5+2)$$

In the example of $31$ I first split this into 2 primes because that gives the largest available prime, that is $31=29+2$

I then use the split $29=(19+7+3)$ giving

$$31=19+7+3+2$$

The question is:

Is this "greedy prime" algorithm (taking the largest primes you can get from any recursive split into 2 or mainly 3 primes) always going to get you to a sum with the largest number of unique primes?

[Which includes the constraint to always decompose the largest prime in the new list first (the new list being generated immediately after a previous split).]

• I think it's not. For 19 it will give 19 = 17 + 2 and stop but it should give 11+5+3. – Maciej Pankanin Dec 18 '17 at 21:26
• @Maciej Pankanin: Sorry I missed that split for 19. I will add it for completeness. In the example used the algorithm is not even saved by leaving the two prime split to the end. Have you had any ideas yourself? – James Arathoon Dec 18 '17 at 21:44
• @Maciej Pankanin: The only small tiny little hope left for this algorithm is to check both paths for the most primes: the 2 prime spit at the beginning, as well as the two prime split at the end. – James Arathoon Dec 18 '17 at 21:54