Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
If the sequence $(\lfloor r^n\rfloor)_{n\ge 1}$ starts with $1,3,5,10,18,32$, then $32^\frac16 \le r < 18^\frac15$, and we have that $57 < 32^\frac76 < 18^\frac75 < 58$, so $57$ is the next element, regardless of $r$. –  Marco Golla Jan 6 at 15:01
    
I believe that there was a Putnam problem that answered this question, but I don't have a good way to search through all previous exams. –  Richard Stanley Jan 7 at 1:33
1  
In fact, also $r \sim 109.19432559052055$ gives an even larger example. –  Marco Golla Jan 9 at 15:00
1  
Take the sequence generated by that $r$, and consider its first 8 elements. According to octave, this sequence is forcing. I think octave is accurate enough for this computation (the 9-th element has 18 digits). –  Marco Golla Jan 9 at 23:38
1  
Ok, I can't resist adding these two: $(1,2,2)$ is forcing (notice that this is the shortest possible forcing sequence); $(1,2,3,4,7,11)$ forces the next two elements! In fact, this possibility follows from my answer (to which I will add a comment now). –  Marco Golla Jan 10 at 15:14
show 2 more comments

5 Answers

up vote 14 down vote accepted

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

share|improve this answer
1  
It's a little hard to tell which parts of this answer are a claimed fact, and which parts are a suggestion. Could you edit to make it a little clearer, perhaps? –  James Cranch Jan 6 at 13:59
    
Thanks for the edit! The first part now makes perfect sense. :-) I don't understand the claim in the second part (below the horizontal line) though. –  James Cranch Jan 6 at 14:20
    
@JamesCranch thanks for the horizontal rule, maybe the edit fixed it. –  joro Jan 6 at 14:55
1  
@SJR Indeed, but the additional term $(1+(-1)^n)/2$ depends on the parity of $n$. –  joro Jan 6 at 15:04
    
Nice answer. There are simple formulas for expressing $x_{kn}$ in terms of $x_n$ for this specific $r\approx 17.944$ However given only that $x_1,x_2,\cdots,x_k$ comes from some $r$ there turn out to be roughly $18+\frac{18}{k}$ options for $x_{k+1}.$ –  Aaron Meyerowitz Jan 8 at 1:50
show 1 more comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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?

share|improve this answer
    
In fact, the same argument shows that, for any fixed $\ell$, any initial sequence with $\alpha<\sqrt[\ell]{2}$ can be extended it to a sequence that forces the next $\ell$ entries. This is because the new $Q$ will have at most $\frac{1-\beta^\ell}{1-\beta}\cdot \beta^{K+1} + o(\beta^{K+1})$ elements, and for sufficiently small $\beta$s this is dominated by the size of $P$. –  Marco Golla Jan 10 at 15:20
add comment

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. enter image description hereenter image description here

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.

share|improve this answer
    
Are you sure one can't be lucky by accident? floor(low)=floor(high) will be an answer if it happens. –  joro Jan 8 at 14:41
    
We have a sequence of half open intervals $r \in [\sqrt[k]{x_k},\sqrt[k]{x_k+1})$ but we will never have exactly $\sqrt[p]{x_p}=\sqrt[q]{x_q+1}$ as that would place $r$ in an empty intersection. –  Aaron Meyerowitz Jan 8 at 16:04
    
(781-197-6)*1+197*2+6*3=781+197*1+6*2=990, which differs by 1 from 991. Why the discrepancy? (This cannot be explained by unaccounted sequences with more than 3 choices.) What software did you use for (a) counting the sequences and (b) generating and displaying the graphs? –  Victor Protsak Jan 8 at 17:23
    
Also, this is not a tree: for example, (3,9,31) and (3,10,31) are both possible. This is clear from the graph and can be easily explained by the fact that $\sqrt{10}^3$ is strictly between 31 and 32, so if $r$ is just below $\sqrt{10}$ we get (3,9,31) and if it is just above $\sqrt{10}$ we get (3,10,31). –  Victor Protsak Jan 8 at 17:38
    
@victor. I corrected the numbers to $991=781 \cdot 1 + 196 \cdot 2 + 7 \cdot 3$ and made the previous graph into a tree. The calculations were all done in Maple. –  Aaron Meyerowitz Jan 9 at 6:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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