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[1], 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Carl Löndahl Jun 27 '16 at 6:56
  • $\begingroup$ @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. $\endgroup$ – Bergi Jun 27 '16 at 6:59
  • 2
    $\begingroup$ 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$. $\endgroup$ – f'' Jun 27 '16 at 12:41
  • $\begingroup$ @f'' Please post that as an answer! $\endgroup$ – Bergi Jun 27 '16 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).

| improve this answer | |
  • 4
    $\begingroup$ The reverse, 5, *2 and +3 seems to be even simpler $\endgroup$ – Bergi Jun 27 '16 at 8:21
  • 1
    $\begingroup$ @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. $\endgroup$ – Vaekor Jun 27 '16 at 8:36
  • $\begingroup$ Wouldn't $f(g(g(16))$ generate $5$? I guess that doesn't use $13$ as input. $\endgroup$ – Yakk Jun 27 '16 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.

| improve this answer | |

$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)$.

| improve this answer | |
  • $\begingroup$ p, q > 1 :-) $\endgroup$ – Bergi Feb 4 '18 at 16:46
  • $\begingroup$ Right, I seem to have backspaced that portion... $\endgroup$ – Martin Feb 4 '18 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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