Floors of powers of reals, how much do the first few determine the next?

Question

Call an integer sequence $\mathbf{x}=\left( x_1,x_2,\cdots \right)$ feasible if it is $f(r)=\left(\lfloor r \rfloor, \lfloor r^2 \rfloor, \lfloor r^3 \rfloor, \ldots, \lfloor r^n \rfloor, \ldots \right)$. for some real $r \gt 1$.

Q: if the members of $f(r)$ all have the same parity, must $r$ be an integer?

I believe(d) so (I was wrong see below.) The motivation of the question is not so much about parity as about how much an initial segment of a feasible sequence limits the next term. An affirmative answer to the question would imply that for every non-integer $r \gt 1$, there must be some $k$ so that $x_1,x_2,\cdots,x_k$ uniquely determines $x_{k+1}$.

Given only the value $x_k$ we know the approximate value of $r$ and I claim that (provided $k$ is fairly large compared to $r$) this restricts the possible values of $x_{k+1}$ to an interval of length roughly $r.$.

In more detail: Given only $x_k$ we know that $\sqrt[k]{x_k} \le r \lt \sqrt[k]{x_k+1}$ so $$(x_k)^{1+1/k}\le x_{k+1} \lt (x_k+1)^{1+1/k} \tag{ * }.$$ Suppose that $k$ is a good bit larger than $r$ and let $s=\sqrt[k]{x_k}.$ Then $\sqrt[k]{x_k+1} \approx s+\frac{1}{ks^{k-1}}$ and the bounds $( * )$are approximately $$s^{k+1} \le x_{k+1} \lt s^{k+1}+s(1+1/k)$$.

Of course $x_{k+1}$ must be an integer. Also, we can say $$\max_{j \le k} \sqrt[j]{x_j}\le r \lt \min_{j \le k}\sqrt[j]{x_j+1}.$$

---

later Thanks for the good answers. I now realize that the answer to my question turns out to be

No, $r$ need not even be algebraic. No matter how many initial terms are given, Even if one term is forced by the previous ones, choices can then be made, one term at a time, which always allow several choices for the next term.

This might require $x_1 \ge 3$ or a similar condition. I think that one can maintain freedom of choice as long as one refrains from making the greatest possible choice (unless forced to do so, in which case the next choice will not be forced.)

I will describe things in general terms here and add a graphic illustration as an answer:

In addition to $(*)$ above, showing that $x_k$ alone allows about $s(1+1/k)$ possible values for $x_{k+1}$ one has $$\lfloor s^{k-1} \rfloor \le x_{k-1} \le s^{k-1}+\frac{1-1/k}s.$$

Which means that there might be two possible values for $x_{k-1}$, but not more.

---

Here is an example with a forced term followed by a sketch of how to find such. Typically a feasible a sequence $[235,x_2,x_3,x_4,x_5]$ will allow about $235+\frac{235}{5}=282$ possible values for $x_6$ and over $75000$ possible values for both $x_6,x_7.$ However the sequence $[235, 55677, 13137758, 3100000161, 731479476931,x_6,x_7]$ has only $5$ completions: one must have $x_6=172600708777398$ and $| x_7-40727054702138152| \le 2.$ In this case $x_4 \approx 3100000000$ was the third thing I tried and I was fortunate to find out that $3100000162^{\frac54}=731479476931.00004144$. Thus the restriction $$\sqrt[5]{731479476931} \le r \lt \sqrt[4]{3100000162}$$ forced by the sequence is very strong.

Answer 1

This is related to OEIS 014217 Floor(phi^n), where phi = (1+sqrt(5))/2 is the golden ratio.

From the comments:

$$a(n) =\lfloor \phi^n \rfloor = L(n)-(1+(-1)^n)/2$$

Where $L(n)$ are Lucas numbers.

Since $L(6n)$ are well known to be even, take $r=\phi^6$ where $\phi$ is the golden ratio.

$a(6n)=\lfloor r^n \rfloor = L(6n) - 1 \equiv 1 \pmod 2 $

$r$ is not an integer.

Experimentally $\lfloor r^n \rfloor$ is odd up to $n=1000$ (just to check).

---

Since there are multiplication formulas for Lucas numbers $L( k n) = f(L(n)) $, from $x_n$ we can determine $x_{kn}$.

$L(6n)=b(n)$ is A087215 and satisfies $b(n) =18 b(n-1) - b(n-2)$, so $x_n,x_{n+1}$ determine the rest of the sequence $\lfloor r^n \rfloor$.

Answer 2

This is a somewhat different proof of Joro's claim that $\lfloor(\phi^6)^n\rfloor$ is odd for all $n$, where $\phi$ is the golden ratio. Maybe it will shed some additional light.

Let $F_n$ be the Fibonacci sequence $0,1,1,2,\ldots$. Let $c=\phi^6$ and let $d=\bar{\phi}^6$, where $\bar{\phi}$ is the $\mathbb{Q}$-conjugate of $\phi$. The equation $\phi^n=F_{n-1}+\phi F_n$ is easily verified by induction, and it implies that $$c^n=F_{6n-1}+\phi F_{6n}.$$ Taking $\mathbb{Q}$-conjugates, we obtain $$d^n=F_{6n-1}+\bar{\phi} F_{6n}.$$

Adding the two equations, $$c^n+d^n=2F_{6n-1}+F_{6n}.$$

Now it is well known that $F_n$ is a divisibility sequence, meaning that if $m\mid n$ then $F_n\mid F_m$. Since $F_6$ is even, so is $F_{6n}$. Therefore $2F_{6n-1}+F_{6n}$ is an even integer. On the other hand, $d$ is between 0 and 1, therefore $c^n=2F_{6n-1}+F_{6n}-d^n$ has floor an odd integer, as required.

Answer 3

Here's a slight generalization of the example in joro's answer. Suppose $r = r_1$ is a Pisot-Vijarayaghavan number with conjugates $r_2, r_3, ..., r_n$ (in particular we can take $r_1 = \frac{1 + \sqrt{5}}{2}, r_2 = \frac{1 - \sqrt{5}}{2}$). Then

$$g(k) = r_1^k + r_2^k + ... + r_n^k$$

satisfies a linear recurrence of length $n$, and in particular

• if $n$ is known then the first $n$ terms uniquely determine the $r_i$, and
• $g(k) \bmod 2$ is eventually periodic.

For all but finitely many $k$, the sequence $f(k) = \lfloor r_1^k \rfloor$ differs by at most $1$ from $g(k)$, with the difference depending in some a priori complicated way on the phase(s) of the second largest of the $r_i$ in absolute value. In the special case that the second largest conjugate(s) is/are real, which always happens when $n = 2$, the difference only depends on the value of $k \bmod 2$.

Answer 4

EDIT: I've edited the post to fix the estimate of the cardinality of $P$. I'd like to thank Francesco Veneziano for carefully checking the proof with me.

---

Just to set up some terminology, I will call any initial segment of a feasible sequence a partial sequence, and I will say that a partial sequence $(x_1,\dots,x_k)$ is forcing if it determines $x_{k+1}$.

Claim. Given a partial sequence $(x_1,\dots,x_k)$ one can extend it to a (of sufficiently long) forcing partial sequence, provided that $\beta := \min_{j \le k}\sqrt[j]{x_j+1} < 2$.

In fact, call $\alpha := \max_{j \le k} \sqrt[j]{x_j}$, so that the inequality given in the question reads as $$\alpha \le r < \beta.$$ Then $\alpha^n \le r^n < \beta^n$ for any $n$, and in this interval there are at least $\beta^n-\alpha^n-1$ integers. Therefore, in the interval $I = [\alpha, \beta)$ we have a set $P_n$ of at least $\beta^n-\alpha^n-1\,\,\, n$-th roots of integers. Call $\displaystyle P = \bigcup_{n=k+1}^K P_n$.

Lemma. $P$ contains $$\beta^{k+1}\frac{\beta^{K-k}-1}{\beta-1} + O(\alpha^{K+1}) + O(K\beta^{K/2}/\log K) + O(K\log K) \qquad (\dagger)$$ points.

I will prove the lemma below.

Now take the $(K+1)$-th powers, and call $Q = P_{K+1}$: $Q$ contains at most $\beta^{K+1}-\alpha^{K+1}+1$ points, some of which may be contained in $P$. We have a forcing partial sequence of length $K$ (extending the original one) if and only if two points in $P$ fall in one of the closed intervals into which $Q$ breaks up $I$.

Now the pigeonhole principle tells us that this is surely the case as soon as $|P| > |Q|+1$, where $|\cdot|$ denotes cardinality.

Since $\beta < 2$, in the difference $|P|-|Q|-1$, the dominant term is $\frac{2-\beta}{\beta-1}\beta^{K+1}$, hence for a sufficiently large $K$ we get a forcing sequence extending the original one. $\square$

---

Now, on to the lemma.

Proof of the lemma. Repetitions when adding the $n$-th roots of integers come from distinct prime divisors of $n$. More specifically, inclusion-exclusion tells us that there are at least $$q_n = \sum_{d|n} \mu(d)(\beta^{n/d} - \alpha^{n/d} - 1)\qquad (*)$$ points in $P_n \setminus \bigcup_{m<n} P_m$, where $\mu$ is the Moebius function.

We can trow away a lot of stuff in that sum, and get that $$q_n \ge \beta^n-\alpha^n-\sum_{p|n} \beta^{n/p} - 2^{\omega(n)},$$ where $\omega(n)$ is the number of distinct prime divisors of $n$.

We're interested in the sum $\sum_{n=k+1}^K q_n$. We'll treat the four sums in $(*)$ separately. The first and second sums give the first and second summand in $(\dagger)$ respectively, by explicitly summing up.

The third sum is more interesting: $$-\sum_{n=k+1}^K \sum_{p|n} \beta^{n/p} \ge - \sum_{n=1}^K \sum_{p|n} \beta^{n/p} = -\sum_{p\le K} \sum_{m=1}^{\lfloor K/p\rfloor} \beta^m = -\sum_{p\le K} \frac{\beta^{K/p + 1}-1}{\beta-1}.$$ Here I switched the sums and called $m = n/p$.

Now we estimate $p \ge 2$, hence $K/p \le K/2$ and get $$-\sum_{n=k+1}^K \sum_{p|n} \beta^{n/p} \ge \pi(K)\cdot \frac{\beta^{K/2 + 1}-1}{\beta-1} = O(K\beta^{K/2}/\log K),$$ where $\pi$ is the prime-counting function, and I estimated it using the prime number theorem. This takes care of the third summand in $(\dagger)$.

Finally, we estimate $-\sum 2^{\omega(n)} \ge -\sum d(n)$, where $d$ is the number-of-divisors function, and the latter is classically estimated as $O(K\log K)$ (Dirichlet?). This explains the last summand. $\square$

---

While I realise that this doesn't really answer the original question, I think that the (crude) estimates I made can be made effective, and maybe they can even be used to show that there the set of forcing sequences is not null (at least when conditioning over $\beta < 2$).

This doesn't say anything about the case $\alpha \ge 2$ (if $\alpha < 2$, one can just artificially add some terms so that the upper bound $\beta$ gets close enough to $\alpha$, and achieve $\beta < 2$ as well -- then the claim above applies): has anyone found an example with $\alpha > 2$, yet?

Answer 5

Here is an illustration of what things look like given that $x_1=\lfloor r \rfloor=3.$ I think that a larger value than $3$ would work even better. Then we know $3^k \le x_k \le 4^k-1$. So there are $781$ possible values for $x_5$ and, by my calculations, $991$ possibilities for the sequence $(x_1,x_2,x_3,x_4,x_5)$. This means that most of the time $x_5$ alone determines all the previous terms. In fact there are $196$ choices which can be arrived at in exactly two ways and only $7$ which can be arrived at in three ways. One is $x_5=569$ which can be due to any one of $$ [3,12,44,159,569],\ [3,12,44,160,569], \ [3,12,45,160,569]$$

One can imagine the successive terms $x_k$ as describing an upward path in a tree with a node labelled $x_k$ located at the point $(\sqrt[k]{x_k},k)$. There may be other nodes labelled $x_k$ at that level. For example there are three nodes labelled $569$ at level $5$. They are at $(x,5)$ for $x=\sqrt[5]{569},\sqrt[4]{160},\sqrt[3]{45}$

Here are selected portions of that graph. The first three levels and above that portions of the next two levels above $46$ and $47$ in the third level.

If the tree was extended to more levels eventually each node would have $3$ or $4$ continuations to the next level. If one takes an upward path which moves always to the right (never directly vertically) as it goes up, then it will be consistent to keep doing this in any way desired. SO there is freedom to choose the parity.

If one avoids both the leftmost and rightmost upward edge leaving each node then each term will determine all the earlier ones.