3
$\begingroup$

Definitions. Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and mutually co-prime. Then find the maximum sum the set $S$ can have.

Example. Let $n=10$, then the maximum sum $S$ can have is $30$ corresponding to $S=\{1,5,7,8,9\}$.

What I tried. I tried to implement the following greedy algorithm.

  1. First I divide primes $\le n$ into $3$ lists: $list_1$ containing primes $\le \lfloor \sqrt{n} \rfloor$, $\; list_2$ containing primes in range $\big( \lfloor \sqrt(n) \rfloor,\lfloor \frac{n}{2} \rfloor \big )$ and finally $list_3$ containing prime in the range $\big[\lfloor \frac{n}{2} \rfloor+1,n \big ]$.
  2. Next I define a function $largest(a,b,n)$, which returns the largest number of the form $a*b^{r}$ less than equal to $n$.
  3. If there exist two numbers $l_1 \in list_1$ and $l_2 \in list_2$ such that $diff = largest(l_2,l_1,n)-( largest(1,l_1,n) + l_2 ) > 0$, I chose the pair $(l_1,l_2)$ such that $diff$ is maximised. I delete $l_1$ from $list_1$, $l_2$ from $list_2$ and append $largest(l_2,l_1,n)$ in $list_2$ and repeat step $3$. If no such pair $(l_1,l_2)$ exists such that $diff>0$, I go to step $4$.
  4. I don't change anything in $list_3$.
  5. In the end $ \{1\} \cup \{ l_1^r \; | \;l_1 \; \in list_1 \text{ and } largest(1,l_1,n)=r \} \cup list_2 \cup list_3$ is my desired set $S$ and I report the sum of it's elements.

Running example of my algorithm. If $n=30$,

#list_1 = {2,3,5}
#list_2 = {7,11,13}
#list_3 = {17,19,23,29}

#The first time step 3 is evaluated I get l_1 = 2 and l_2 = 7 ..
#.. as  diff = ( 28 - ( 16 + 7 ) ) = 5 > 0 and diff is maximised
# so I delete 2 from list_1 and 7 from list_2 and append 28 in list_2

#When step 3 is evaluated again no such pair (l_1,l_2) is found

#So our desired list becomes S={1,27,25,11,13,28,17,19,23,29} with sum 193.    



But my algorithm only seems to give correct for few simple cases only. Plus I am not able to prove/disprove or modify any of my assumptions .Now I am hopelessly stuck at the problem and I am not making any progress. But I still believe that some greedy algorithm is at work here.

PS: The question is from project Euler max-sum co-prime set. I would really appreciate just some hint or new direction to think.

$\endgroup$
  • $\begingroup$ think it would be nice to have some gesture on bkg/ motivation on the problem $\endgroup$ – vzn Jul 17 '16 at 14:47
  • $\begingroup$ That's Euler Problem #355, which means it is tough. They ask for the solution for N = 200,000 which makes me expect a O (n^2) solution :-) $\endgroup$ – gnasher729 Jul 17 '16 at 18:03
  • $\begingroup$ Did you notice that elements in the maximal sum subset do not have more than two unique prime factors? $\endgroup$ – Abhigyan Mehra Jul 17 '16 at 18:08
  • $\begingroup$ @AbhigyanMehra: That might be coincidence. $\endgroup$ – gnasher729 Jul 17 '16 at 18:08
  • $\begingroup$ Have you considered making a graph? $\endgroup$ – Evil Jul 18 '16 at 2:02
4
$\begingroup$

Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating.

Since the numbers are mutually co-prime, each prime number p is a factor of at most one element of S. On the other hand, if p is small enough then a number could have a factor $p^2$, $p^3$, $p^4$ and so on. We also know that every prime number p ≤ N is used (if p is not used as a factor of any number in the set then we just add p). And don't forget to include the number 1 in the set S :-)

A number x ≤ N cannot have two prime factors greater than $N^{1/2}$. Therefore the set S contains among other numbers one number $x_p$ ≤ N which is a multiple of a prime $p > N^{1/2}$. That's a good start for finding the optimal set S. We then take the primes $q ≤ N^{1/2}$, and either multiply one of the numbers $x_p$ by a power of q, or we add a new number $x_q$ which is some power of q.

In the Project Euler project with N = 200,000, there are fewer than 90 primes $q ≤ N^{1/2}$. We can take each of these primes q in turn, and either multiply one of the existing $x_p$ by a power of q, or add a new number $x_q$. We would try to do this achieving the highest possible increase in the sum. If no two q, q' achieve the highest increase in the same way, we can pick the optimal way for each.

In the example N = 30, we would start with $x_p$ = 7, 11, 13, 17, 19, 23, 29. We can use q = 2 to change 7 -> 28. q = 3 -> 27, q = 5 -> 25. The gains are 21, 27, 25. Each gain is > N/2. So an optimal solution cannot include a number created by two or more of the q's - that number would be ≤ N, but we would give up two gains > N/2, so this wouldn't be optimal. So in the simple example, we multiply 7 by $2^2$ and add $3^3$ and $5^2$.

With N = 100, we would have $x_p$ = 11, 13, 17, 19, 23, ... and q = 2, 3, 5, 7. q = 2: 11 -> 88 gains 77. q = 3: 11 -> 99 gains 88. q = 5: 19 -> 95 gains 76. q = 7: 13 -> 91 gains 78. Unfortunately we have a conflict; q = 2 and q = 3 would both use $x_{11}$. If we use 11->88 (gain 77), then q = 3: 31->93 with a gain of 62; total gain 139. If we use 11->99 (gain 88) then q = 2: 23->92 (gain 69) has a total gain of 157. So optimal for N = 100 is

S = { 1, 99, 91, 17, 95, 92, 29, 31, 37, 41, ,,, }

So here is the algorithm: Start with $x_p$ = primes > $N^{1/2}$. Find the primes $q ≤ N^{1/2}$. For each q, find the maximum gain that can be achieved using q: Either $q^k$ by adding the number $q^k$, or $p * (q^k - 1)$ by multiplying $x_p$ by $q^k$. If each optimal gain is achieved in a different way, and each gain is ≥ N/2, then we found the optimal solution.

Otherwise, we choose one set of q's that use the same $x_p$. For each of these q's: We assume that this q uses $x_p$, find the optimal solution under the restriction that no other q uses this $x_p$, and choose which q using $x_p$ gives the best total.

If there is a case where the two smallest gains add up to less than N, ask someone for a more complex solution :-)

$\endgroup$
  • $\begingroup$ Could you add a hint and hide the soln time in yellow region? $\endgroup$ – sashas Jul 18 '16 at 13:24
  • 1
    $\begingroup$ This is computer science, not puzzling. $\endgroup$ – gnasher729 Jul 18 '16 at 20:24
  • $\begingroup$ @sasha, Well, the idea behind the Euler project is to encourage/enable people to explore for themselves and discover neat mathematics on their own. The pedagogical principle behind it is to create opportunities for people to experience what it is like to discover new mathematics on their own, by patiently exploring on their own (in the context of a carefully-crafted problem that is likely to reward exploration). It's about failing, failing, failing, but keeping trying, and eventually experiencing the joy of discovering something new yourself. $\endgroup$ – D.W. Jul 18 '16 at 22:18
  • $\begingroup$ So, ultimately, it seems to me that asking for hints is a bit at odds with the goals and pedagogical principles underlying the Euler project (if I understand them correctly). (See, e.g., meta.math.stackexchange.com/a/21390/14578.) Of course you're welcome to use the Euler problems for whatever purposes you might have, and that's fine -- I'm not judging. But I don't see any reason why others should feel constrained to alter their answers in this way, given that even asking this question seems in some tension with the philosophy of the Project Euler founders. $\endgroup$ – D.W. Jul 18 '16 at 22:20
  • 2
    $\begingroup$ @sasha, great, I look forward to your discussion on meta! I'm not proposing to close this question (as I see it, it's not our job to enforce Project Euler's philosophy). I'm just saying, it's up to the answerer how they want to format their answer. $\endgroup$ – D.W. Jul 19 '16 at 8:06
2
$\begingroup$

I did not follow gnasher729 completely on how he resolved the conflicts he mentions in his answer ( will look into it now ). So as suggested by D.W. I spent more on it and finally solved it. I followed the same algorithm described in my question except for the fact, that in place of doing greedy, one has to use maximum weighted bipartite matching ( a suggestion by Evil ), while trying to pair up a prime less than $\sqrt(n)$ with a prime greater than $\sqrt(n)$. But as I did not know how to implement maximum weight bipartite matching, I looked closely and the bi-partite graph formed in this case was too easy and one could resolve the conflicts and thus solve for maximum weight manually ( by pen and paper calculator :), the bipartite graph formed had interesting patterns too ). Finally the solution rests on a conjecture I am still unable to proof ( which I assumed in my post ) : to increase the sum of set $S$ you can pair up a prime less than $\sqrt{n}$ with exactly one prime greater equal to $\sqrt{n}$.

$\endgroup$
  • $\begingroup$ it is fantastic that you have tried several schemes. You can model the whole problem as bipartite, but taking only part as subproblem is so much better. Try full gnasher729 solution - it works and is based on the same conjecture. It might look like backtracking but it is used on several numbers, so it runs very fast. I would like to encourage you about proving conjecture or posting it (probably at Math) and second - please try some heavy mod - do it for $1000000$ and $10000000$ - it still runs under 10 seconds ;). Hints only is not very bad, but since answer is full you should acknowledge it. $\endgroup$ – Evil Jul 20 '16 at 18:10
  • $\begingroup$ @Evil yes I will surely read and implement gnasher729's method. $\endgroup$ – sashas Jul 20 '16 at 18:13
  • $\begingroup$ I actually think there's a bug in it :-) It might not give an optimal solution if there are several sets of different conflicts and resolving one conflict interferes with another. On the other hand I think conflicts will be rare so this might never happen. $\endgroup$ – gnasher729 Jul 21 '16 at 7:50
  • $\begingroup$ @gnasher729 yes there were only 5 conflicts for N=200000, which I resolved manually. But the elegant way would be to use maximum weighted bipartite matching. $\endgroup$ – sashas Jul 21 '16 at 10:37
  • 1
    $\begingroup$ Yeah, 5 conflicts - and automatic resolution even the crude one is fast, hey even backtracking for several groups is still far better than bigger runtime in terms of n. $\endgroup$ – Evil Jul 21 '16 at 19:23

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.