# Two functions that can't be applied in different order to arrive at same result

Here's my puzzle:

Write two unary functions f, g and provide an input x so that only the combination f(g(x)) will yield the result y but no other combination of them does - even if applied multiple times in any order.

The functions should use standard arithmetic operations, the numbers should be small integers, too keep it simple (so that the solution y = f(g(x)) is obvious to everyone). If that is not possible, feel free to use more advanced operations or rational numbers.

I am still trying to solve it myself. I just made it up, I don't think it's a well-known problem.

I have tried some simple additions and multiplications, but it proved unexpectedly hard. Maybe I just don't know the right mathematical tool or can't see the pattern. I thought about prime numbers, but they don't really seem to help here. Some (counter)examples:

• 1, *3, *5 - but also 1 *5 *3 = 15
• 0, +3, *5 - but also 0 *5 +3 *5 = 15
• 1, +3, *5 - but also 1 *5 +3 +3 +3 +3 +3 = 20
• 1, *5, +2 - but also 1 +2 +2 +2 = 7
• 1, +3, /2 - but also 1 +3 +3 +3 /2 +3 /2 /2 = 2
• 2, +3, ^2 - but also 2 ^2 ^2 +3 +3 +3 = 25

1: If you're curious, I am trying to write a test for a computer program that implements function composition.

• If you are allowed to apply some index $j$ in how the functions are composed, you could use $f(x) = k^j\cdot x$ -- assuming that $k^j$ is greater than any input $x$. For binary $x$, we can use $f(x) = 2^j\cdot x$ to get a unique representation. Jun 27, 2016 at 6:56
• @CarlLöndahl: no indices. You don't know how often, at which point in the sequence, or whether at all the function is used. Notice you can also choose x, it doesn't need to work on any input. Jun 27, 2016 at 6:59
• If you use $f(x)=x+1$, $g(x)=\frac{1}{x+1}$, with the starting value of $1$, then every positive rational number is the result of exactly one sequence of $f$ and $g$.
– f''
Jun 27, 2016 at 12:41
• @f'' Please post that as an answer! Jun 27, 2016 at 15:58

How about the following for a single operator version:

Let $f(x)=x/2$, let $g(x)=x-3$, and let $x=13$, with $y=5$.

If we perform $f(g(x))$, we get $y$. If we perform $f$ before $g$, we will get a non-integer (and applying $f$ or $g$ after this will not help). If we perform $g$ more than once, then the resulting value is too low to apply $f$ to reach $y$. We cannot apply $g$ by itself any number of times to reach $y$. Once we reach $y$, using either function will make the result too low to return to $y$ (since both functions are strictly decreasing).

• The reverse, 5, *2 and +3 seems to be even simpler Jun 27, 2016 at 8:21
• @Bergi I originally avoided functions of the form *n and +m given the number of counterexamples that contained them; it seems I came full circle. I suppose the strictly increasing version is simpler, although the strictly decreasing version was easier to see the proof in my head before writing down. Jun 27, 2016 at 8:36
• Wouldn't $f(g(g(16))$ generate $5$? I guess that doesn't use $13$ as input.
– Yakk
Jun 27, 2016 at 14:06

OK, I figured out one solution. Binary, as mentioned by Carl Löndahl in the comments, should've been obvious. It hit me though when I looked at a string concatenation.

Start with 1, use λx → x⋅2+0 and λx → x⋅2+1 as functions. Or bitshift and xor, if you want.

I'm still wondering though whether there is a solution using a single operator per function.

$f(n) = p^n, g(n) = q^n$ such that $\gcd(p, q) = 1, p, q \in \mathbb Z^+.$

This works for all positive $n$. Mind you, the numbers you get will be pretty big. An integer power of $p$ cannot be equal to an integer power of $q$, so there is no $h(n) \in \{\textrm{compositions of }f, g\}$ such that $(f\circ h)(n) = (g \circ h)(n)$.

• p, q > 1 :-) Feb 4, 2018 at 16:46
• Right, I seem to have backspaced that portion... Feb 4, 2018 at 16:48