Smallest $k$ such that $\phi(\phi(\phi(..._k(\phi(n)))))=1$

$\phi(2m)\leq m,$ and $\phi(n)$ is even except when $\phi(n)=1.$ So you get $k\leq 1+\log_2(n-1).$

This upper bound can be achieved when $n=2^{2^j}+1$ is a Fermat prime. There might only be finitely man such $n,$ but we can’t do much better for large $n,$ since when $n=2^m,$ $k=m=\log_2(n).$ Indeed, $\lfloor 1+\log_2(2^m-1)\rfloor =m,$ so this is a maximum again.

to check about upper bounds, we print out each time the quantity of interest sets a new record

===================================

  n  is between 2^(k-1)  and 2^k.
   diff = n - 2^(k-1)

  n:  2 k:  1 factor n  2 
  n:  3 k:  2 factor n  3  diff 1
  n:  5 k:  3 factor n  5  diff 1
  n:  11 k:  4 factor n  11  diff  3
  n:  17 k:  5 factor n  17  diff  1
  n:  41 k:  6 factor n  41  diff  9
  n:  83 k:  7 factor n  83  diff  19
  n:  137 k:  8 factor n  137  diff  9
  n:  257 k:  9 factor n  257  diff  1
  n:  641 k:  10 factor n  641  diff  129
  n:  1097 k:  11 factor n  1097  diff  73
  n:  2329 k:  12 factor n  17 137  diff  281
  n:  4369 k:  13 factor n  17 257  diff  273
  n:  10537 k:  14 factor n  41 257  diff  2345
  n:  17477 k:  15 factor n  17477  diff  1093
  n:  35209 k:  16 factor n  137 257  diff  2441
  n:  65537 k:  17 factor n  65537  diff  1
  n:  140417 k:  18 factor n  140417  diff  9345
  n:  281929 k:  19 factor n  257 1097  diff  19785
  n:  557057 k:  20 factor n  557057  diff  32769
  n:  1114129 k:  21 factor n  17 65537  diff  65553
  n:  2384897 k:  22 factor n  2384897  diff  287745
  n:  4227137 k:  23 factor n  4227137  diff  32833
  n:  8978569 k:  24 factor n  137 65537  diff  589961
  n:  16843009 k:  25 factor n  257 65537  diff  65793
  n:  35946497 k:  26 factor n  35946497  diff  2392065

=============================