Very interesting problem. $P(a,b): f^{2f(b)}(2a)=f(f(a+b))+a+b$. Claim 1: $f$ is injective. Proof: Suppose $f(a)=f(b)$, $a>b$, let $c=a-b$. $P(x,a),P(x,b): f(f(a+x))+a+x=f(f(b+x))+b+x\implies f(f(x+c))=f(f(x))-c$ for all $x>b$. Easy to see with induction that $f(f(x+nc))=f(f(x))-nc$, and by fixing $x$ and taking a sufficiently large $n$ we arrive at a contradiction. Claim 2: Suppose $2m<2n$. Then, there exists $t>0$ such that $f^t(2m)=2n$ Proof: Take $k>a,b$ and $f(k-a)>f(k-b)$. Then, $P(a,k-a),P(b,k-b): f^{2f(k-a)}(2a)=f^{2f(k-b)}(2b)\implies f^{2f(k-a)-2f(k-b)}(2a)=2b$. This means that all the even numbers can be connected by $f$s. Note that an even number cannot be part of a cycle (i.e. $f^x(2a)=2a$) because of the above sentence. Now, suppose on the contrary that $2m>2n$ and $f^t(2n)=2m$ for some $t>0$. Then, since $f^{2f(k-n)-2f(k-m)}(2n)=2m$, thus $2f(k-n)-2f(k-m)>0$. (Else $2n,2m$ are part of a cycle). Let $m-n=c$. Then, $f(k)>f(k+c)$ for all $k>m$. This means $f(k) \ge f(k+c)+1$. Easy to show by induction that $f(k)\ge f(k+cn)+n$. Fixing $k$ and taking a sufficiently large $n$ we arrive at a contradiction. Thus, the claim is true. Claim 3: $f$ is strictly increasing. Proof: From claim 2, we get that $f(k-a)>f(k-b)$ for any $k>b>a$. Taking $b=a+1, k=2a+1$, we have $f(a+1)>f(a)$ Claim 4: $f(a)=a+1$ From the previous claim, $f(a+1)\ge f(a)+1$. If $f(1)=1$, then $P(1,1): 2=0$, contradiction. Hence we must have (by induction, say) that $f(a)\ge a+1$. $P(a,a): f^{2f(a)}(2a)=f(f(2a))+2a$. By above, $f(f(2a))+2a=f^{2f(a)}(2a)\ge f(f(2a))+2f(a)-2\ge f(f(2a))+2a$. Hence, equality must hold and $f(a)=a+1$ for all $a$, which obviously works.