Functional equation $f(f(x))=2x$ on $\mathbb{Z}_{>0}$ I have this functional equation:
$$f(f(x))=2x$$
with $f: \mathbb{Z}_{>0}\rightarrow \mathbb{Z}_{>0}$. And I want to know if it is possible to list all solutions. 
I already know that $f(2x)=2f(x)$, further, if $f(1)=c$, then $f(2^kc)=2^{k+1}$ by induction and $f(2^k)=2^kc$ but that doesn't really give anything. I have attempted, but I think there is a clever step I don't see. Also, since $f \circ f$ is injective, $f$ must be injective. 
I actually suspect that there either no solutions or uncountably many, of which most aren't nice functions.  
 A: An example function satisfying this property is the function $f$ defined by 
$$
f((4k+1)2^i) = (4k+3)2^i\\
f((4k+3)2^i) = (4k+1)2^{i+1}
$$
Fundamentally, all answers are at least somewhat similar to this.  You should try to prove that for all odd $x$, $f(x)$ is either odd or twice an odd number, in which case $x = f(f(x)/2)$.  You can then describe all solutions as indexed by partitions of the odd numbers into ordered pairs $(a_1, b_1), (a_2, b_2), \ldots$, where 
$$f(a_i2^j ) = b_i2^j\\
f(b_i2^j) = a_i2^{j+1}$$ 
 This leads to an uncountable number of solutions.
A: To see that such a function exists let $f$ be defined as follows, if $n=2k$ is even, let $f(n)=2f(k)$, if $n=4k+1$, let $f(n)$ be $4k+3$, and if $n=4k+3$, let $f(n)=2(4k+1)$.
Then $f(f(2^j(4k+1)))=2^jf(f(4k+1))=2^jf(4k+3)=2^{j+1}(4k+1)$ as desired, and $f(f(2^j(4k+3)))=2^jf(f(4k+3))=2^jf(2(4k+1))=2^{j+1}(4k+3)$. Since any positive integer can be written in one of these forms for $j$ and $k$ nonnegative integers this function satisfies your property.
In general this construction can be done in the same way if $g$ is an involution in the positive odd integers. $g$ pairs up the odd integers with each other let $S$ be a set containing one element in each pair. Then define $f(2k)=2f(k)$, and otherwise $f(n)=g(n)$ if $n\in S$, and $f(n)=2g(n)$ if $n\not\in S$.
I'm sorry I don't have a complete characterization, but I thought I'd post this partial solution.
A: Here is a more general result.

Claim. Let $a\geq 1, k\geq 2$ be integers. Then there are infinitely many functions $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ such that
$$\overbrace{f(f(\dots f(n)\dots))}^{k \text{ times}}=an, \text{ for all }n\in \mathbb{Z}^{+}.$$
Furthermore all these functions are described by partitioning positive integers into disjoint tuples of $k$ distinct integers (for $a\geq 2$ none of these integers are multiples of $a$). For each such tuple $(n_1,n_2,\dots,n_k)$ then $f$ maps
$$ 
a^in_1 \mapsto a^in_2 \mapsto \dots \mapsto a^in_{k-1} \mapsto a^in_{k} \mapsto a^{i+1}n_{1}.
$$
for all $i \geq 0$.

Proof. We can see that all values $a^in_j$ with mapping above satisfy the functional equation and also these values cover all positive integers (note that $a^ic=a^jd$ with $a\not\mid c$, $a\not\mid d$ implies $i=j$, $c=d$).
To show that all $f$ are of the form above, pick any positive integer $b$ fixed and define a sequence $b_1=b$, $b_{i+1}=f(b_i)$. Then the equation implies $b_{i+k}=ab_i$, so we have a linear recurrence of degree $k$. This proves the claim for $a=1$. For $a\geq 2$ we can assume the initial value $b$ is such that there does not exist $c\neq b$ with $f(c)=b$ (otherwise choose $c$ as a starting point, cycles are impossible as the values increase after each $k$ steps). Now if any of the initial values is a multiple of $a$, then $an=f(f(\dots f(n)\dots))$ implies we can go back $k$ steps in the sequence, contradicting our assumption. So none of the initial values is a multiple of $a$ and $b_1,b_2,\dots,b_k$ satisfy conditions of the claim. Repeating this process for the remaining integers we get the partitioning from the claim. $\square$
Let's demonstrate the above and construct a generic example that works for all $a\geq 2$, $k\geq 2$. Since we want to avoid multiples of $a$, we can define $f(n)=af(n/a)$ when $a\mid n$ and for rest of the values we either set $f(n)=n+a$, or, if we are at the end of tuple of $k$ elements, we need to loop back. This will create blocks of size $ka$ where remainders mod $a$ are within the same loop (up to a power of $a$) of length $k$. If we put this into a function description we eventually get
$$
f(n)=\begin{cases}
af(\frac{n}{a}) & a \mid n \\
a(\lfloor \frac{n}{ka} \rfloor ka+n\bmod a) & \lfloor \frac{n}{a}\rfloor = \lfloor \frac{n}{ka} \rfloor k+k-1\\
n+a & \text{else}
\end{cases}
$$
Your problem is an instance of $a=2,k=2$, so plugging it into the above and spliting the cases based on $n \bmod 4$, we find a solution
$$
f(n)=\begin{cases}
2f(\frac{n}{2}) & n\equiv 0 \pmod 2 \\
2(n-2) & n\equiv 3 \pmod 4\\
n+2 & n\equiv 1 \pmod {4}
\end{cases}
$$
This is by the way A002516.
