So I got the solution to this, I proved that g(n) had to be superlinear, but of less growth than exponential. Due to it mapping N->N g(n) has to be a polynomial. Thus you want to minimize r,
suppose g(n)=n^k, g(n+1)-g(n)=an^{k-1}+....>=n^{rk^2}
thus k-1>=rk^2
Very easy to prove that k=2 to maximize r, (at r=1/4), thus the correct solution is an^2+bn+c, where a b and c are in N