In a sense, there is no smallest: the smaller root of $x^2+k x+2$ has the desired property, and this goes to $-\infty$ with $k$. I assume the problem is meant to ask for a *positive* $x$.

Here's some code (at the bottom) for Mathematica (infinite precision!) that computes the half-open set $[a_0,b_0) \cup [a_1,b_1) \cup \cdots$ of real numbers $x$ that are less than the root of $\alpha^3-3\alpha^2-\alpha+1$ and for which $\lfloor x^k \rfloor\equiv k \bmod 2$ for all integers $k$ between 1 and $n$, inclusive.

For $n=16$, the smallest $x$ is $\sqrt[16]{100801956}$, a number that appears in the answer by user35593. This lower bound on $x$ is improved, but only by a minuscule amount by taking $n=45$: we learn that $x$ is at least $\sqrt[45]{32341223721862945369971}$. This is still not large enough to provably dismiss user35593's claim.

To enrich the examples we have, I offer the following. The larger root $\alpha$ of $x^2 -(2k+1)x-2\ell$, where $1\leq \ell \leq k$, is slightly above $2k+1$, while the smaller root $\bar \alpha$ is between $-1$ and 0. Because of the recurrence satisfied by $\alpha^n+\bar\alpha^n$, the real number $\alpha$ has the desired property $\alpha^n \equiv n \bmod 2$ for all $n\geq 1$.

```
alpha = Root[1 - #1 - 3 #1^2 + #1^3 &, 3];
NewUpInt[1] = {{1, 2}, {3, alpha}};
NewUpInt[n_] := NewUpInt[n] =
Module[{int},
If[EvenQ[n],
int[{a_, b_}] :=
Table[{Max[a, (2 k + 2)^(1/n)], Min[b, (2 k + 3)^(1/n)]},
{k, Floor[(a^n - 3)/2] + 1, Ceiling[(b^n - 2)/2] - 1}],
int[{a_, b_}] :=
Table[{Max[a, (2 k + 1)^(1/n)], Min[b, (2 k + 2)^(1/n)]},
{k, Floor[(a^n - 2)/2] + 1, Ceiling[(b^n - 1)/2] - 1}]];
Flatten[Map[int, NewUpInt[n - 1]], 1]];
```

1more comment