For applicative order the answer $$k=4$$ is easy to find. For normal order evaluation we have $$k'=m_{k-1}+\sum_{1}^k m_i$$, where $$m_k=m_{k-1}+m_{k-2}+1$$, $$m_0=m_{-1}=0$$. We calculate $$m_1=1$$, $$m_2=2$$, $$m_3=4$$, $$m_4=7$$, and get the final result $$k'=18$$.