What is the optimal way to perform GCD chain operation? Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. 
This problem is solved using dynamic programming.

Similarly

GCD chain operation is defined as:- Given a set of $n$ integers, what is the most efficient way to find the gcd of all the elements?

The cost is the number of GCD(x,y) invocations done by a binary GCD algorithm.

Basic attempt at solving the problem is:-
GCD$(a_1,a_2,a_3,a_4,\ldots a_n)$

{

$k=GCD(a_1,a_2)$.

if ($k=1$)

return 1; 

else 

return $GCD(k,a_3,a_4\ldots a_n)$;

} 

In simple terms, it keeps finding the gcd of the smallest two among all the $n$ elements and then recurse, by replacing the two elements with their gcd which is at most the smallest element in the input.



Make suitable assumptions if necessary. For example you can assume that the integers are given in sorted order.

Assume GCD is computed using a binary GCD algorithm (other GCD algorithm is also fine)
aka

$GCD(a,b)= GCD(a-b,b)$

$GCD(2a,2b)=2GCD(a,b)$

and $GCD(a,2b)=GCD(a,b)$ (if $a$ is odd)

GCD(75,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 3

GCD(125,25)=GCD(100,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 4

GCD(179,25)= GCD(154,25)=GCD(77,25)=GCD(52,25)=GCD(26,25)=GCD(1,25)=1

Number of steps is 6



A heuristic strategy mentioned in the basic attempt above is not optimal for the following example

GCD(25,75,125,179,181,225) 

= GCD(GCD(25,75),125,179,181,225) (3 steps)

=GCD(GCD(25,125),179,181,225) (4 steps)

=GCD(GCD(25,179),181,225) (6 steps)

=1

This required 13 invocations of GCD(x,y) function.

But the optimal strategy would be to see that 179 and 181 have gcd 1 and therefore the solution is 1, which requires computing only 1 bivariate gcd.

GCD(179,181)=GCD(179,2)=GCD(179,1)=1

which takes 3 invocations of GCD(x,y) only

I am not sure if there exists an optimal way to do it, or maybe it is NP hard to find a solution which makes the least number of GCD(x,y) calls.
You are saying that you will perform n-1 gcd operations, unless you find k numbers with a gcd of 1 by performing k-1 gcd operations. 

Since you don't know which set of numbers has a gcd of 1, you can't pick a set with gcd 1. Your total time depends on the data you have. 

You can try to process small numbers first, because the gcd of small numbers tends to be calculated quicker than the gcd of large numbers. 

The optimal strategy will not always lead to the best outcome. I put a deck of cards on the table, face down, and ask you to pick the ace of hearts. Do you think "pick the ace of hearts" is the optimal strategy? No, it isn't a strategy that you can enforce since you don't know which one is the ace of hearts.