Minimum function optimization puzzle #2

Question

_{Previous puzzle}

---

Take this puzzle of mine I created about an hour ago

Take two functions, $f(x):=x^2$ and $g(x):=x-3$. Starting from $x=0$ and applying these functions as needed, what is the minimum amount of times you will need to apply the functions $f$ and $g$ to get $492804$?

Restrictions

Numbers lower than $-12$ are banned.

My attempt:

65 functions

1. Apply $g$ 4 times to get $-12$ (total of 4 functions used)
2. Apply $f$ once to get $144$ (total of 5 functions used)
3. Apply $g$ 49 times to get $27$ (total of 54 functions used)
4. Apply $f$ once to get $729$ (total of 55 functions used)
5. Apply $g$ 9 times to get $702$ (total of 64 functions used)
6. Apply $f$ once to get $492804$ (total of 65 functions used)

However, my question is: Can YOU figure out the true minimum amount of times you will need to apply the functions $f$ and $g$ to get $492804$, or is this truly the most efficient solution to the puzzle?

_{Don't worry I know the answer :D also sorry for lack of efficiency in my attempt that I showed}

Answer 1

We can reuse the strategy from the previous question.

$(x-D)^2 < x^2-D$ for all $x > (D+1)/2$, which means that applying $g$'s before an $f$ is always a more efficient way to reach a target square than applying $g$'s after an $f$, unless you apply so many that you pass the negation of your current value.

Our target, as alluded to by your solution path, is $702^2$. Once again, our number is constrained to be a multiple of 3, so the last $f$ in our path must result in $9k^2$ for some $k$. $k = 8$ yields $576$, which is too small, so $729$ is the best choice. Now we must reach $27$, and again the closest result is $36$, which we can reach from $\boxed{-6}$, allowing the composition $fg^9fgggfgg(0)$, with seventeen applications.

Answer 2

This is going to take more words than I would like.

Let's start from the end. $492804$ is a square, so it's tempting to say that the last step must be to use $f$. But we have to prove that. What if the last step is $g$? Then this means that the previous number was $492807$, which is not a square. Therefore, the only way to get it is to apply $g$ repeatedly from a larger square. The next square is $703^2=494209$, and it would take a little less than $500$ steps to get from there (note that $703$ is not divisible by $3$, so we actually need to go even further from $705^2$). Clearly, this is not an optimal solution, since we already have one that takes 65 steps. We have now proven that the last step must be $f$, and therefore we now need to get to $702$ as fast as possible. Note that $-702$ also is theoretically fine, but we can only achieve negative numbers by applying $g$ repeatedly, and it would take us $702/3=234$ steps to do so, which is not an option.

Since $702$ is not a square, we can only get to it by using $g$. The closest one is $729=27^2$, but can we say for sure that we must stop here? Yes, following the same logic as before. The only difference is that the next square $28^2=784$ is not that far (at least, not far enough to rule out immediately), but here we use the fact that we need that square have the same modulo 3 as 702, which happens to be divisible by 3. So the next square should also be divisible by 3, and therefore it is $30^2=900$, which would require $(900-702)/3=66$ steps. Again, definitely suboptimal, so we go with $729=27^2$. So, we have deduced that the final operations must be $f, g \times 9, f$ (a total of $11$ steps), and we now should get $27$ or $-27$ as fast as possible.

The story with $-27$ is short and simple: it takes $9\times g$ to get from zero. But maybe we can do better with $27$? Once again, $27$ is not a square, so we must use $g$ to get to it from one of next square numbers. The next suitable one is $6^2=36$. Once again, do we go further? This time, I won't decide right now, but I note that the next square would be $9^2=81$, and getting from there would take $(81-27)/3=18$ steps. However, I feel like experimenting with $6$, since it only takes $4$ steps to get to $27$ from here.

The tricky part to remember when going backwards is that we can also square negative numbers. So while we can get $6$ in $3$ steps $\left(0 \xrightarrow g (-3) \xrightarrow f 9 \xrightarrow g 6\right)$, we can obviously get $-6$ via $2\times g$. WIth this method, we can get to $36$ in just 3 steps. Then we go from there as described above, obtaining a solution in $11+3+3=17$ steps in total. This immediately rules out the option with going to $27$ from $81$, because just that part alone takes as many steps. This also is better than taking $9$ steps to get to $-27$, because we get there in $6$ steps. Therefore, our current solution must be optimal.