What is the optimal way to solve the following optimization problem You are given a function $F$, which can take one or more positive integer operands.
Let $L=\{a_1,a_2\ldots a_n\}$.

We need to compute the function $F(L)$ using the least number of transformations/steps.
Computing $F(L)$ is not the main goal. Computing it in the fastest possible way is the goal.

Following rules are allowed to be applied to this function.

--> If $L$ has only one element say $x$, then the $F(L) = x$;

--> If all elements in $L$ are even then $F(L)=2F(L')$, where $L'$ contains all elements in $L$ divided by 2.
For example $F(4,8,10)= 2*F(2,4,5)$

--> If some elements in $L$ are odd and some are even, then $F(L)=F(L')$, where $L'$ has same odd elements as L, but the even elements in $L$ are made odd by removing the factor 2.
For example $F(6,9,20)=F(3,9,5)$

--> If any of the integers in the list is 1, then $F(L)=1$;

--> If two or more integers in $a_1,a_2\ldots a_n$ are same, then we can remove the copies and keep only one of them.
For example $F(4,5,6,5)=F(4,5,6)$

--> For any pair $a_i$ and $a_j$ where($a_i&lt;a_j$), you can replace $a_j$ with $a_j-a_i$

$F(4,7,8)=F(4,(7-4),8)=F(4,3,8)$



It is easy to notice that this process terminates, because at each step, either the value one of the operands is reduced or the number of operands is reduced.

Given $L$ can there be a DP to optimize the number of operations needed to solve $F$, or is there a greedy strategy that is optimal or constant approximate of the optimal?

For example

Consider the following instance

$F(15,30,45)$

Depending on your choice, you can compute this value in several ways.

\begin{align*}
F(15,30,45)&amp; =F(15,30,45-30)=F(15,30,15)\\
&amp; =F(15,30)\\
&amp; =F(15,30-15)=F(15,15)\\
&amp; =F(15)=15
\end{align*}

which takes 4 iterations.

Another way is

\begin{align*}
F(15,30,45)&amp; =F(15,30-15,45)=F(15,15,45)\\
&amp; =F(15,45)\\
&amp; =F(15,45-15)=F(15,30)\\
&amp; =F(15,30/2)=F(15,15)\\
&amp; =F(15)=15
\end{align*}

which takes 5 iterations.

I want an algorithm which finds the optimal solution.
Yes, there is a simple way to compute $F$.

Proposition: $F(a_1,a_2\ldots a_n)=\gcd (a_1,a_2\ldots a_n)$, where $\gcd$ is the greatest common divisor.

Proof: I will leave it as an exercise. Hint, the replacement of $a_j$ by $a_j-a_i$ whenever $a_i&lt;a_j$ is very powerful.

Here is a simple and efficient algorithm to compute $F(a_1,a_2\ldots a_n)$.


Let $r = a_1$.
Iterate $i$ through $2,3, \cdots, n$, setting $r$ to $\gcd(a_i, r)$. Here $\gcd(a_i,r)$ can be computed by any of your favorite GCD algorithms such as Euclidean algorithm or binary GCD algorithm.
return $r$.