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?


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$.]

  • $\begingroup$ 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? $\endgroup$ – ARupinski Mar 30 '16 at 2:37
  • $\begingroup$ @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. $\endgroup$ – Noam D. Elkies Mar 30 '16 at 2:49
  • 5
    $\begingroup$ $x=\frac{3+\sqrt{17}}2$ works as well. $\endgroup$ – Max Alekseyev Mar 30 '16 at 4:09
  • $\begingroup$ 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. $\endgroup$ – Kevin O'Bryant Apr 17 '16 at 2:21
  • 1
    $\begingroup$ 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... $\endgroup$ – Noam D. Elkies Apr 17 '16 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.