# What is the smallest x such that [x^n] has the same parity as n?

A previous MO question asked for information about a number $x$ such that $[x^n]$ has the same parity as $n$ for all positive $n$. Answers to this post included two values of x which meet the requirements. From Noam Elkies: the largest root of $x^3-3x^2-x+1$, giving $x=3.2143...$. From Max Alekseyev: $(3+\sqrt{17})/2$, giving $x= 3.56155...$.

What is the smallest such positive number? Failing this, what are the first few digits of the smallest such positive number?

This question was suggested to me by Moshe Newman

• Numerically, you should be able to get the first few digits by computing the intersection of the nth roots of intervals of the right parity, establishing that such a number is either less than sqrt 3 or larger than sqrt 10. After enough initial computation, you may be able to use dynamics of the functions x^(1+1/n) to prove existence in the smallest of the finitely many remaining intervals. Gerhard "Might Do It By Hand" Paseman, 2016.04.05. – Gerhard Paseman Apr 5 '16 at 16:05
• For example there is such an x>3 between the fourth roots of 100 and 101. Since each multiplication lands the current interval into an interval over three times longer, you are guaranteed a full interval of the right parity. So I assert that one such x has 3.16 < x < 3.17, and getting more precision by hand is merely tedious, not hard. Having an x with x^2 less than 3 is more challenging, but likely one exists. Gerhard "Likely Is Not A Proof" Paseman, 2016.04.05. – Gerhard Paseman Apr 5 '16 at 18:35
• wrote a brood force computer program in octave. It seems that there is no such number below three which satisfies the condition for all n=1,...,17. function []=parity(n) a=1; m=1; i=1; nstep=1; while i<n && nstep<10000 nstep=nstep+1; fxi=floor(a^(i/m)); fxii=fxi-i; if fxii~=2*floor(fxii/2) a=fxi+1; m=i i=1; else i=i+1; end end a^(1/m) – user35593 Apr 6 '16 at 17:44
• The smallest number seems to be around 3.1639. Then the condition is fullfilled for all n=1,...,28 however I couldn't go further because then you run into problems because of the machine epsilon. – user35593 Apr 6 '16 at 17:46
• By Gerhards argument we can say that there is such a number between 100801956^(1/16) and 100801957^(1/16). The first number fullfills the condition for all n=1,...,18 – user35593 Apr 6 '16 at 18:22

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{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{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, 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]];


As explained in the comments the smallest solution (if it exists) must be between $\sqrt{100801956}$ and $\sqrt{100801957}$. The first few digits are $3.16385673$.

• There is no guarantee that this greedy approach (by fitting $n$-th powers into the smallest integer interval of required parity) will produce a solution. In fact, it would be stuck at 67-th power, meaning that there is a need to use backtracking rather than greedy approach. However, it still is not clear when and where to stop to guaranteed any fixed precision. – Max Alekseyev Apr 7 '16 at 20:26
• To get the smallest such real may require backtracking. However the smallest such real is at least 3.16. If you have a candidate interval [x,y) with y^n-x^n =L and 3.16 L > 1+2L, you are guaranteed a solution in that interval, so some intelligent searching (as well as iterating the process for intervals shorter than L) may lead to getting real close to the smallest candidate, or at least improve precision. Gerhard "Faking It Can Work Sometimes" Paseman, 2016.04.07. – Gerhard Paseman Apr 7 '16 at 20:53