Minimum function optimization puzzle #3: 3 functions

Question

_{Previous puzzle}

---

Take this puzzle of mine I created recently:

Let $f(x)=x+1$, $g(x)=x^2-1$, $h(x)=2x-4$. Starting with $x=0$ and applying these functions as needed, what is the minimum amount of times that you will need to apply $f$, $g$ and $h$ to get the number $524261$?

My attempt:

Total: 122889 functions

1. Apply $h$ once to get $-4$ (total: 1 function)
2. Apply $g$ thrice to get $50175$ (total: 4 functions)
3. Apply $h$ thrice to get $401372$ (total: 7 functions)
4. Since there is nothing we can do now other than apply $f$, we apply it a total of $122889$ times to get $524261$ (total: 122896 functions)

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

Hint (if and only if you are struggling):

The first two steps are correct (in order also!) however apply $g$ 2 less times.

_{Don't worry I know the answer :D also sorry for the lack of efficiency in my attempt that I showed, but at least it wasn't peak inefficiency with $\infty$ total functions}

Answer 1

The minimum number of steps is

Eleven

With the sequence

h g f g f g f h h h f
:
h(0) = -4
g(-4) = 15
f(15) = 16
g(16) = 255
f(255) = 256
g(256) = 65535
f(65535) = 65536
h(65536) = 131068
h(131068) = 262132
h(262132) = 524260
f(524260) = 524261
----------------------
Alternative:
g(0) = -1
h(-1) = -6
h(-6) = -16
g(-16) = 255
(continue as above)

My approach: work backwards from the goal.

The final step must be

524260 + 1, as the other functions cannot produce the target directly.

Apply the inverse of h(x) repeatedly and look for values that are near a square.

We soon see 66536 = 256^2, which we can easily obtain by alternating g(x) and f(x) on h(0) = -4

Thus the goal is achieved with surprisingly little effort.

Answer 2

A short program in R confirms @DanielMathias answer.

11 operations, with exactly two possible sequences: ghhgfgfhhhf and hgfgfgfhhhf

You can try the code here.

The code in text: (not showing correctly because of characters '<' and '>')

library(dplyr)
library(purrr)
library(magrittr)

goal % 
    add_row(v=g(v),op1=paste0(op1,"g"),n=n+1) %>% 
    add_row(v=h(v),op1=paste0(op1,"h"),n=n+1)
}
add_dep % 
    bind_rows(new_rows)%>% 
    group_by(v) %>% 
    filter(n==min(n)) %>% 
    ungroup
  dep
}

# Go backward
add_func_dest % 
    add_row(v=k(v),op2=paste0("g",op2),p=p+1) %>% 
    add_row(v=l(v),op2=paste0("h",op2),p=p+1)
  ans %>% filter(!is.na(v))   
}

add_dest % 
    bind_rows(new_rows) %>% 
    group_by(v) %>% 
    filter(p==min(p)) %>% 
    ungroup
  dest
}

# Main resolution
turn %  add_dep()
  } else{
    dest %%  add_dest()
  }
  inter % mutate(op=paste0(op1,op2),nb_op=n+p) %>% select(nb_op,op)

And the result :

A tibble: 2 x 2
nb_op op
1    11 ghhgfgfhhhf
2    11 hgfgfgfhhhf