If $h(x)$ is the integer $n$ such that $n \leq (1+\sqrt{2})x < n+1$, show that $h$ is primitive recursive

Question

I can solve this for $n \leq \sqrt{2}x < n +1$:

$$n \leq \sqrt{2}x < n +1 \iff n^2 \leq 2x^2 < n^2 + 2n + 1$$

We're looking for

$$h(x)=\min_{n\leq 2x} \big( 2x^2 - n^2 > 0 \lor 2x^2=n^2 \big)$$

But I don't know how to do it when I can't get rid of the irrational factor. Help!

Answer 1

Hints: (A) $n \le (1 + \sqrt{2})x < n +1 $iff $n - x \le \sqrt{2}x < n - x +1$ iff $(n-x )^2 \le 2 < (n - x + 1)^2$ (provided $n \ge x \ge 0$). (B) if $n \le (1+ \sqrt{2})x$, then $n < 3x$. By (B) the search for $h(x)$ given $x$ is bounded and by (A) the test for the value $n= h(x)$ that you are searching for is prim. rec.