3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Sounds like an exercise in dynamic programming. $\endgroup$ – Henning Makholm Dec 17 '17 at 14:36
  • $\begingroup$ If it's a programming exercise would be nice to know any constraints on $n$. $\endgroup$ – kingW3 Dec 18 '17 at 21:52
  • $\begingroup$ @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. $\endgroup$ – Maciej Pankanin Dec 18 '17 at 22:03
2
$\begingroup$

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).]

$\endgroup$
  • 2
    $\begingroup$ I think it's not. For 19 it will give 19 = 17 + 2 and stop but it should give 11+5+3. $\endgroup$ – Maciej Pankanin Dec 18 '17 at 21:26
  • $\begingroup$ @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? $\endgroup$ – James Arathoon Dec 18 '17 at 21:44
  • $\begingroup$ @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. $\endgroup$ – James Arathoon Dec 18 '17 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.