# Maximizing GCD of a variable set of numbers

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?

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

• 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 Commented May 26 at 1:34
• 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).. Commented May 26 at 1:42
• 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. Commented May 26 at 1:45
• @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. Commented May 26 at 1:47
• 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 Commented May 26 at 2:10

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

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.

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