Short logic

1. $$$(a_1,\dots,a_k) \gt (a_1,\dots,a_{k+1})$$$ $$$\Leftrightarrow$$$ $$$(a_1,\dots,a_k)=d\ge2$$$ and $$$a_{k+1}\not\equiv0\pmod d$$$.
2. $$$f(a)=0$$$ $$$\Leftrightarrow$$$ $$$a_1=(a_1,a_2)=\cdots=(a_1,\dots,a_n)$$$ $$$\Leftrightarrow$$$ $$$a_1=(a_1,\dots,a_n)$$$.
3. For a multiset $$$S$$$ and $$$d\ge2$$$ let

• If $$$\operatorname{cnt}_d(S)=|S|$$$, then $$$d$$$ divides everything ⇒ you cannot create a drop with this $$$d$$$.
• Any permutation satisfies $$$f \le \max_{d\ge2,\ \operatorname{cnt}_d \lt |S|}\operatorname{cnt}_d$$$.

1. Achievability is clear (place all elements divisible by $$$d$$$ first, then any non-divisible one) ⇒

5. Why only prime powers $$$p^{\alpha_p+1}$$$ are enough

Let $$$G=\gcd(S)=\prod_{p} p^{\alpha_p}$$$ (take only primes $$$p$$$ actually occurring in $$$G$$$; for all others $$$\alpha_p=0$$$). Then:

• Any “useful” divisor $$$d$$$ that can create a drop does not divide the whole set, hence for at least one prime $$$p\mid d$$$ its exponent $$$e_p$$$ is strictly larger than the common exponent in $$$G$$$: $$$e_p\ge \alpha_p+1$$$.
• The set $$${x:\ d\mid x}$$$ is contained in $$${x:\ p^{e_p}\mid x}$$$ for any such $$$p$$$. Therefore

So composite divisors do not improve the maximum: it suffices to look at one prime power lifted exactly “one level” above the common exponent. * Converse (achievability): take $$$p$$$ with maximal $$$\operatorname{cnt}_{p^{\alpha_p+1}}(S)=c$$$. By definition $$$\alpha_p=\min v_p(x)$$$, so there exists an element with $$$v_p=\alpha_p$$$ ⇒ $$$c \lt |S|$$$. Place all $$$c$$$ numbers divisible by $$$p^{\alpha_p+1}$$$ first, then a number with $$$v_p=\alpha_p$$$. At position $$$k=c$$$ the prefix $$$\gcd$$$ drops in the $$$p$$$-adic exponent ⇒ a drop occurs.

Final (exact equality):

Remark: if $$$\gcd(S)=1$$$, then $$$\alpha_p=0$$$ for all $$$p$$$, and the formula gives $$$g(S)=\max_p \operatorname{cnt}_{p}(S)$$$ — the maximum number of elements divisible by a single prime.

Restatement

For the prefix $$$P_i=[a_1,\dots,a_i]$$$, let $$$G_i=\gcd(P_i)=\prod_p p^{\alpha_p(i)}$$$. Then

— i.e., “how many numbers in the prefix have, for some prime $$$p$$$, an exponent at least one higher than the common minimal exponent $$$\alpha_p(i)$$$ of $$$p$$$ in $G_i$”.

Examples

• $$$S={6,12,18}$$$. $$$\gcd=6=2^1\cdot 3^1$$$. $$$\operatorname{cnt}_{2^{2}}=1$$$ (only 12), $$$\operatorname{cnt}_{3^{2}}=1$$$ (only 18) ⇒ $$$g=1$$$. A permutation: $$$(12,6,18)$$$.

• $$$S={8,4,2}$$$. $$$\gcd=2$$$ ⇒ $$$\alpha_2=1$$$. $$$\operatorname{cnt}_{2^{2}}=2$$$ (8,4) ⇒ $$$g=2$$$. A permutation: $$$(8,4,2)$$$.

• $$$\gcd(S)=1$$$: e.g., $$$S={2,3,6,5}$$$. Max over primes: for 2 — two (2,6), for 3 — two (3,6), for 5 — one ⇒ $$$g=2$$$. Place $$$(2,6,3,5)$$$.