3
$\begingroup$

Is there a systematic method of selecting a set of numbers (which add up to a constant total) in such a fashion as to maximizing their collective GCD?

One example: select 5 different integers (greater than zero) that add up to 264 in such a way that they generate the maximum possible GCD.

My first thought would be to divide the total into equal parts of 5, since GCD(n,n)=n however there's obviously the remainder. But the condition of numbers having to be different does not help us!

I am not looking for brute-force methods.

Specifically: What's the greatest possible GCD of a set of $m$ numbers, $n_1,\dots,n_m$ such that $n_1+\dots+n_m=M$, and the $n_i$'s are pairwise distinct?

$\endgroup$
0

3 Answers 3

4
$\begingroup$

Input: $s$ = sum of the numbers, and $m$ = the number of numbers.

Output: the greatest possible $d$ such that $GCD(a_1,\dots,a_m)=d$ and $\sum_{i=1}^ma_i = s$.

Observe: Let $b_i = a_i / d$. Then $c:=\sum_{i=1}^mb_i = \frac{s}{d}$ is an integer greater or equal to $m$. In other words, $d|s$ and $d\le \frac{s}{m}$. You can simply pick the maximum $d$ that satisfies these, and easily construct $a_i$.

For example $(s,m)=(264,5)$ then you only need to check the factors of $264$ below $52$, i.e. $1,2,3,4,6,8,11,12,22,24,33,44$. You can simply take $d=44$, and since $264/44=6$, we have $a=44\times(1,1,1,1,2)$ working.

If, in addition, the $a_i$ are distinct, then $c\ge 1+2+\dots m=m(m+1)/2$ and therefore $d\le \frac{2s}{m(m+1)}$.

So for the example you only need to check up to $17.6$, so only $1,2,3,4,6,8,11,12$. Since $264/12=22$, we can just do something like $a=12\times (1,2,3,4,12)$.

$\endgroup$
7
  • $\begingroup$ Yes but now we have to select a set of 5 numbers from the list of 13 (ignoring your 88 there)...that's still a hefty group of 1287 $\endgroup$
    – Steve237
    Commented May 26 at 1:34
  • 1
    $\begingroup$ If the numbers have to be distinct, you only need to check up to $264/(1+2+3+4+5)$. And regardless of whether distinctness is a requirement, there's not much to check, it should be trivial to achieve the largest candidate value (the list of candidates does depend on distinctness).. $\endgroup$
    – Erick Wong
    Commented May 26 at 1:42
  • $\begingroup$ The 5 numbers have to add up to 264. So you are suggesting the max (possible) GCD is 264/15~17? But how do we get the set of 5 numbers that contributed to that. $\endgroup$
    – Steve237
    Commented May 26 at 1:45
  • 3
    $\begingroup$ @Steve237. The GCD has to divide $264$, so the max possible is $12$. If you think about the question "how do I get 5 distinct numbers divisible by 12 to add up to 264?", it's literally no harder than "how do I get 5 distinct numbers [divisible by 1] to add up to 22?". Just try it. $\endgroup$
    – Erick Wong
    Commented May 26 at 1:47
  • $\begingroup$ Yes I get it, 12(n)=264, so n=22 and we need a set of 5 distinct n's to add up to 22, which are {7,6,4,3,2} , but question is why 12? And I think max 22 would not have been possible since that would put the sum at 264/22=12=n and hence even the first 5 numbers go beyond that! 1+2+3+4+5>12 $\endgroup$
    – Steve237
    Commented May 26 at 2:10
3
$\begingroup$

You can solve the problem via dynamic programming (DP) as follows. Let value function $V(m,M,p)$ be the maximum GCD of $m$ distinct positive integers $\le p$ that sum to $M$. By conditioning on the largest selected integer $q$ and applying associativity of GCD, we obtain the following DP recursion: $$V(m,M,p) = \max_{q=1}^p \{\text{GCD}(q,V(m-1,M-q,q-1))\}.$$ The boundary condition is $$V(1,M,p) = \begin{cases} M &\text{if $1\le M\le p$},\\ -\infty &\text{otherwise}. \end{cases}$$

$\endgroup$
0
1
$\begingroup$

In your special case the sum equals 8 x 3 x 11, so the gcd has no other prime factors.

5 different numbers, all multiples of the gcd, are at least 15 x gcd, so gcd <= 264/15, so gcd <= 17. All we need is the largest divisor <= 17, which is 3x2x2 = 12. 264/12 = 22, so we take for example 12 times 1, 2, 3, 4, 12.

So you take the sum s, for n different numbers with gcd g their total is g n (n+1) / 2, g <= floor (2s / n / (n+1)). We find the largest divisor d of s which is <= 2s / n / (n+1), then multiply d by 1 to n-1, then add the remainder as the final number.

$\endgroup$
1
  • $\begingroup$ Yes exactly, i came up with the same steps after reviewing above useful comments and help! Thanks.... $\endgroup$
    – Steve237
    Commented May 27 at 20:57

You must log in to answer this question.

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