i'm trying to assume that n=m-1 we know if $m-1$ odd then $\left\lfloor \frac{2^m}{3}\right\rfloor = \frac{2^m-1}{3}$ and if $m-1$ even then $\left\lfloor\frac{2^m}{3}\right\rfloor =\frac{2^m-2}{3}$. Let's try induction.. We want to claim : for HHHHH...HH (m-1 coins) there are $\left\lfloor\frac{2^m}{3}\right\rfloor$ move to TTTT......TT(m-1 coins) can we do, or it;s equivalent for HHH...HT(m-1 coins) there are $\left\lfloor\frac{2^m}{3}\right\rfloor -1$ move. Let for $m-1=2$ then HH HT TT there are $\left\lfloor\frac{2^3}{3}\right\rfloor =2$ move. for HT to TT there are $\left\lfloor\frac{2^3}{3}\right\rfloor -1=1$ move, which its true. let for $m-1=3$ then HHH HTH HTT THH (use HH to TT from before there are 2 moves) TTT there are $\left\lfloor\frac{2^4}{3}\right\rfloor =5$ move, and for HHT to TTT there are $\left\lfloor\frac{2^4}{3}\right\rfloor -1=4$ move, which its true. Now assume $m=k-1$ is true. Then we need to prove that $m=k$ is true. case 1. for $k-1$ even then there are HHHH...HH (k coins), we need to prove there are $\left\lfloor\frac{2^{k+1}}{3}\right\rfloor=\frac{2^{k+1}-1}{3}$ move to turn it to be TTTT...T(k coins). We know that from HHH...H (k coins) $k-1$ coins from the right use the configuration for $k-1$ coins ($\left\lfloor\frac{2^k}{3}\right\rfloor$ move) HTTTTT...T then flip all $k$ coins from the left to the right ($1$ move) THHHH...H and then use again $k-1$ configuration ($\left\lfloor\frac{2^k}{3}\right\rfloor$ move), it's become TTTTT...T there are $2\left\lfloor\frac{2^k}{3}\right\rfloor+1=\left\lfloor\frac{2^{k+1}}{3}\right\rfloor$ since $k-1$ is even. case 2. for $k-1$ odd then there are HHH...HH (k coins), we need to prove there are $\left\lfloor\frac{2^{k+1}}{3}\right\rfloor=\frac{2^{k+1}-2}{3}$ move to turn it to be TTTT...TT(k coins). HHH....H turn last $k-1$ coins from right become (there are $\left\lfloor\frac{2^k}{3}\right\rfloor$ move) HTTT...T, then turn $k-1$ coins from left become (there are $1$ move) THHH...HT. there are HHH...HT(k-1 coins), turn it to be TTTT...T by using $k-1$ again, which is $\left\lfloor\frac{2^k}{3}\right\rfloor -1$ move.. the total is $\left\lfloor\frac{2^k}{3}\right\rfloor+1+\left\lfloor\frac{2^k}{3}\right\rfloor-1=\left\lfloor\frac{2^{k+1}}{3}\right\rfloor$ since $k-1$ is odd. hence, problem claimed by mathematical induction. Edit : a lot typo sorry my English really bad

I think it takes up to $ \lfloor\frac {2^m}{3}\rfloor $ moves. But I can’t prove it…

I'll prove that it's always possible. Represent each state of the coins by the binary number of converting heads to $1$s, tails to $0$s. Like $THTT=(0100)_2=4$ and $HTTH=(1001)_2=9$. Let $f(x)$ denote the maximum moves that the state $x=(x_{n-1}x_{n-2}\cdots x_0)_2$ can be carried out, and $g(x):=x_0+x_1+\cdots+x_{n-1}$. Let $w_i:=\begin{cases}\frac{2^{i+1}+1}3\text{, if }2|i\\\frac{2^{i+1}-1}3\text{, otherwise}\end{cases}$ Claim: $f(x)\geq\sum_{i=0}^{n-1}x_iw_i$ Induction on $x$ to prove the claim. For $x=0, 1$, $f(0)\geq0, f(1)\geq1$ is trivial. Suppose for all $x<k$, the claim holds. For $x=k$, select $i$ such that $k_i=1$ and $k_0=\cdots=k_{i-1}=0$ and let $j=i\pmod2$. We can flip the $l$-th coin counted from the right for $j\leq l\leq i$, and the state become $k-2^j$. Since $j=0$ or $1$, the base case $x=0, 1$ is enough. $\Rightarrow f(k)\geq f(k-2^j)+1$. For $j=0$ (that is, $2|i$), $w_i=\frac{2^{i+1}+1}3=\frac{2^i+2^{i-1}+\cdots+2^1}3+1=\frac{2^i-1}3+\frac{2^{i-1}+1}3+\frac{2^{i-2}-1}3+\cdots+\frac{2^1+1}3+1=w_j+\cdots+w_{i-1}+1$. For $j=1$ (that is, $2\nmid i$), $w_i=\frac{2^{i+1}-1}3=\frac{2^i+2^{i-1}+\cdots+2^2}3+1=\frac{2^i+1}3+\frac{2^{i-1}-1}3+\frac{2^{i-2}+1}3+\cdots+\frac{2^2-1}3+1=w_j+\cdots+w_{i-1}+1$. $\therefore$ there is a formula $w_i=w_j+\cdots+w_{i-1}+1$-----(1). $\Rightarrow f(k)\geq f(k-2^j)+1\overset{\text{induction hypothesis}}\geq\sum_{l=0}^{n-1}(k-2^j)_lw_l+1=\sum_{l=i+1}^{n-1}k_lw_l+\sum_{l=j}^{i-1}w_l+1\overset{\text{(1)}}=\sum_{l=i}^{n-1}k_lw_l=\sum_{l=0}^{n-1}k_lw_l$, the claim holds. Therefore by induction, the claim holds for all $x$. Since for all $i$, there is $w_{i+1}\geq w_i$. $\therefore f(x)\geq\sum_{i=0}^{n-1}x_iw_i\geq\sum_{i=0}^{g(x)-1}w_i\overset{\text{(1)}}=\begin{cases}w_{g(x)}-1\text{, if }2|g(x)\\w_{g(x)}\text{, otherwise}\end{cases}=\lfloor\frac{2^{g(x)+1}}3\rfloor$, and this finishes the proof.