# Minimum function optimization puzzle #2

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

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.

• Good job on reusing the strategy! (I did not see that being possible lol) anyways yes you are correct so good job lol Nov 16 at 0:33
• If you want to make more of these, I'd like to see more functions at once - that would allow things like parity to come into play and make the solutions less straightforward. Aditionally, I'm curious to see at what point lower limits like the -12 become obsolete. Nov 16 at 0:36
• that would take some practice making lower limits become obsolete but I could try to do that with my next one lol :D Nov 16 at 1:15

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.

• Hold on, let me edit the missing negative numbers
– DL33
Nov 16 at 0:24
• You're almost there, but you're missing an important possibility. Nov 16 at 0:26