1
$\begingroup$

Here's a puzzle of mine that I created around 2 hours ago:

Let $f(x):=x^2$ and $g(x):=x-4$. Starting with x=0, what is the least amount of times you need to apply the functions $f$ and $g$ so that at some point, the output is $1024$?

Restrictions

Negative numbers less than $-8$ are not allowed.

I wanted to try my hand at getting the most efficient solution to this, so here is my most efficient attempt so far (my second attempt, first attempt used up a total of 60 functions):

Total functions: 14$$f(g(g(g(g(g(g(g(g(f(g(g(f(g(0))))))))))))))$$

  1. Apply $g(x)$ and then $f(x)$ to get $16$ (total of $2$ functions right now)
  2. Apply $g(x)$ twice to get $8$ and then apply $f(x)$ to get $64$ (total of $5$ functions right now)
  3. Apply $g(x)$ a total of $8$ times to get $32$ and then apply $f(x)$ to get $1024$ (total of $14$ functions)

However, my question is: Is this truly the most efficient solution to my puzzle, or can YOU find a solution that is more efficient?

unsure if I need more tags or not or if tags need to be changed/removed

Of course I know the most efficient solution, I'm just seeing if you can find it :)

$\endgroup$

1 Answer 1

4
$\begingroup$

Let's see what an optimal path would look like. For starters,

Our number will always be a multiple of $4$. If the result of the last $f$ is greater than $1024$, it's at least $36^2=1296$, and we'll save many, many applications by reducing the argument of the last $f$ to $32$ instead of reducing its output to $1024$. (It can't be $-32$, because that's forbidden.)
The result of the f prior to that has to be the square of another multiple of $4$. $16$ is too small, so the same argument tells us that the second-last $f$ must output $64$. Your path used $f(8)$, but $f(-8)$ is allowed, and this is where the reduction lies.
$f(g^8) fgg(0) = 1024$ in $12$ applications.

$\endgroup$
1
  • $\begingroup$ Yes that is correct. I'll accept your answer in a few minutes when I can $\endgroup$
    – CrSb0001
    Commented Nov 15, 2023 at 0:31

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.