0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The hint is not well chosen, it is given away most of the answer rather than offering smg that would help a stranded solved. $\endgroup$
    – Evargalo
    Nov 17, 2023 at 10:25

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.