# On the parity of $[x^n]$

I am trying to find a problem which appeared years ago in the American Mathematical Monthly. It went something like this: There was a Putnam Competition question which asked to show that there is a number $x$ with the property that $[x^n]$ has the same parity as $n$ for all positive integers $n$. The square brackets indicate the floor function. Demonstrate such a number.

Does anyone know when this problem and solution appeared?

• – Max Alekseyev Mar 30 '16 at 12:55
• Every element of $(-1,0)$ has this property. – Kevin O'Bryant Apr 17 '16 at 2:16
• I finally came upon the reference that I was looking for. It is Problem E 3117 in The American Mathematical Monthly for December 1985 page 735 – David S. Newman May 10 '16 at 20:03

## 1 Answer

Google turns up this "Mock Putnam Exam" from the U[niversity] of I[llinois], whose unattributed second problem asks to show that $[(\sqrt2+1)^n]$ has parity opposite to that of $n$ for each $n=1,2,3,\ldots\,$. Perhaps that's what you remember? (It should also be possible to make any infinite binary sequence arise as $\{[x^n] \bmod 2\}_{n=1}^\infty$ for some $x$ by starting from $x$ large enough and using the sequence of conditions to define a sequence of approximations converging to $x$.)

[added later: an explicit example of $[x^n] \equiv n \bmod 2$ is the largest root $3.214319743377535\!\ldots$ of the cubic $x^3 - 3x^2 - x + 1$.]

• It feels to me that one should be able to modify the construction of Mills' constant to explicitly obtain such an $x$ as the limit of a sequence something like $a_{n+1} = \sqrt[n+1]{\lfloor a_n^{n+1}\rfloor+b_n}$ (might need a little bit of tweaking; this was a back of the envelope attempt to generalize Mills' construction) where the sequence of $b_n$ is chosen according to the binary sequence one wishes to obtain per you're generalization. Is this the sort of construction you are envisioning @Noam? – ARupinski Mar 30 '16 at 2:37
• @ARupinski Yes. To get a prime between $N$ and $N+H$, we need $H$ to be some power of $N$ (it should really be a power of $\log N$ but we can't prove anything like that), which is why Mills needs double exponentials. For an integer of given parity, $H=2$ is enough, so plain $[x^n]$ probably suffices. – Noam D. Elkies Mar 30 '16 at 2:49
• $x=\frac{3+\sqrt{17}}2$ works as well. – Max Alekseyev Mar 30 '16 at 4:09
• Is the parenthetical comment supposed to be obvious? It's clear to me that we can start with any finite binary sequence, but the $x$ that satisfy the first $n$ constraints'', while nonempty for each $n$, may have empty intersection, as far as I can tell. – Kevin O'Bryant Apr 17 '16 at 2:21
• It was a guess when I wrote it (and the comment above), but meanwhile I thought about it a bit more and I think we can construct $x$ by intersecting an infinite sequence of nested intervals as long as the first interval $[x_1, x_1+1)$ has $x_1 \geq 4$ (so $4$ or $5$ will do). The $n$-th interval has the form $[x_n, (x_n^n+1)^{1/n})$ for some integer $x_n$, and that puts $x^{n+1}$ in an interval of length at least 4 so its intersection with $\{X\in{\bf R}:\lfloor X\rfloor\equiv b_{n+1} \bmod 2\}$ must contain a semiopen interval of length $1$. I should update my answer to incorporate this... – Noam D. Elkies Apr 17 '16 at 4:03