# Maximum Pairwise GCD of an even subsequence

I am trying to solve a particular problem, where I have been given an array of integers and an integer X and I need to choose a subsequence of the array whose pairwise gcd is maximum given that the size of the subsequence must not exceed 2*X.

So for example, my array is [5, 7, 10, 8, 3, 4] and X is 2: the answer would be 9 since GCD(5, 10) + GCD(8, 4) = 9

The only approach I've been able to come up with was: At each step I'll find the maximum pairwise GCD of the numbers and then remove the 2 numbers from the array. Will keep adding it to a sum(which I have to output), under the constraints that I dont take in more than 2*X numbers.

• Please edit the question to add a reference to that "particular problem". – Apass.Jack Jul 28 at 15:16
• It looks like that particular problem is part of live contest. If you created or discovered the problem on yourself, please introduce the background a bit. – Apass.Jack Jul 28 at 15:50
• What does the even in the title refer to? – greybeard Jul 28 at 18:11
• Something that irritates me: reading pairwise GCD, I picture all pairs. Tracing the example, I see pairs and fail to see subsequence. – greybeard Jul 28 at 19:54
• A simple example for which OP's algorithm fails could be $[40, 56, 5,7]$ and $X=2$. $g(40,56)+g(5,7)=8+1=9<g(40,5)+g(56,7)=12$ – Apass.Jack Jul 28 at 20:35