# Using Functions to Reach Every Positive Integer

Consider the functions $f(x)=2x+1$ and $g(x)=3x+1$, as well as their inverses f'(x) and g'(x). Starting with the number 1, is it possible to reach every positive integer through some finite sequence of these $4$ functions?

For example, we could have the following sequence:

$$1\,\,\overbrace {\longrightarrow}^{f(x)} \,\, 3\,\,\overbrace {\longrightarrow}^{f(x)} \,\,7\,\,\overbrace {\longrightarrow}^{g'(x)} \,\,2\,\,\overbrace {\longrightarrow}^{f(x)} \, \,5$$

Edit: I've tried a few things like taking base 6 and simply bashing a lot, and it seems like that it is possible, though I have no idea how to rigorously prove that.

• What happens if you apply f'(x) or g'(x) to a number that doesn't invert? – Q the Platypus Mar 10 '17 at 1:53
• Are you only allowed to apply $f'$ and $g'$ when the result is a natural? If $n$ is the smallest number that cannot be reached, we must have $n \equiv 2 \pmod 6$, as we can apply $f'$ to $1,3,5 \pmod 6, g'$ to $4 \pmod 6$ and $g'f$ to $0 \pmod 6$ and get a smaller number. I haven't found a way to make $8$. – Ross Millikan Mar 10 '17 at 1:53
• Yes; you can only use the inverses when the output will be a positive integer. Thank you editors! – user386867 Mar 10 '17 at 1:55
• 1, 4, 13, 27, 55, 18, 37, 12, 25, 8 is one way to reach 8 I believe. – user386867 Mar 10 '17 at 2:00
• @A.Smith Sorry for asking here: why did you cancel your recent question about triangles (math.stackexchange.com/questions/2180126/…)? It looked interesting to me. – Aretino Mar 15 '17 at 21:36

Following on Ross Millikan's comment, if $t=6k+2$, then $f'\circ g'\circ g'\circ f\circ f\circ g$ takes $t$ to $4k+1$, so by induction there can be no minimum and hence all can be reached.
EDIT: The idea behind, of course, is that if $6k+2$ were the smallest number that could not be reached, then we could reach $4k+1$. But the reverse composition, ie, $f\circ g\circ g\circ f'\circ f'\circ g'$, takes $4k+1$ to $6k+2$, contradicting the assumption that it could not be reached.
If $n$ is the smallest number that cannot be reached, we must have $n\equiv2\pmod6$, as we can apply $f′$ to $1,3,5\pmod6$, $g′$ to $4\pmod6$ and $g′f$ to $0\pmod6$ and get a smaller number.
• Could this solution be stated by simply showing that each residue modulo 6 can be turned into a smaller number via the correct sequence of functions (i.e. just stating the 6 cases)? Or is it necessary to include the clause "If $n$ is the smallest number that cannot be reached, we must have $n\equiv2\pmod6$"? – user386867 Mar 10 '17 at 3:10