0
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Good job on reusing the strategy! (I did not see that being possible lol) anyways yes you are correct so good job lol $\endgroup$
    – CrSb0001
    Commented Nov 16, 2023 at 0:33
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 16, 2023 at 0:36
  • $\begingroup$ that would take some practice making lower limits become obsolete but I could try to do that with my next one lol :D $\endgroup$
    – CrSb0001
    Commented Nov 16, 2023 at 1:15
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.