7
$\begingroup$

Consider a sequence $a_i$ defined by $$ \begin{align*} a_1&=p,\\ a_2&=q,\\ a_i&=a_{i-1} \oplus a_{i-2}+1, \end{align*}$$ where $\oplus$ is the bitwise xor operation. How can we give an upper bound for $a_n$ as a function of $p,q,n$?

There are lots of $p,q$ which satisfy $\mathop {\lim }\limits_{n \to \infty } {a_n} = \infty $, but it seems from experimentation that $a_n=O(n)$. I do not have any idea how to prove it, nor do I know whether it is correct.
If this problem is difficult to solve, I only need to prove that, for each $1 \le i \le n$, we have $a_i \le 2^{12}$ when $p,q,n \le 1000$.

$\endgroup$
5
  • 2
    $\begingroup$ Is it not possible to brute-force that range of numbers? In particular with some clever dynamic programming? $\endgroup$ May 21, 2018 at 9:15
  • $\begingroup$ I draw the conclusion by enumerating all of $p,q,n$, but this approch is too awful! I think It can only be used to validate a conclusion, not prove. $\endgroup$
    – zbh2047
    May 21, 2018 at 9:32
  • $\begingroup$ @zbh2047 Do you mean you already validated that $a_i\le 2^{12}$ for all $1\le i \le 1000$ and all $p,q\le 1000$, by brute force (computer program)? $\endgroup$ May 21, 2018 at 11:08
  • $\begingroup$ Yes, I do. I use the simplest way to write a program that spends $O(pqn)$ time to validate the results. $\endgroup$
    – zbh2047
    May 21, 2018 at 12:31
  • 2
    $\begingroup$ @zbh2047: That is a proof - I have a paper where we reduce the problem (this reduction is quite non-trivial), to "only" 90.000 cases, about, which we check by computer. $\endgroup$ May 21, 2018 at 13:18

1 Answer 1

6
$\begingroup$

$\def\U#1{\underline{#1}}\def\O#1{\overline{#1}}$The bound $a_n=O(n)$ is true, in fact, we have $a_n\le\max\{8p,8q,\frac{16}3n\}$. The argument is quite elementary, but a bit tedious to write down properly, hence I will only sketch it, and rely on the reader to fill in the details.

Rather than estimating $a_n$ directly, we will try to bound the position of the most significant bit of $\max_{m\le n}a_m$. Notice that $\oplus$ cannot raise this quantity, and ${}+1$ can raise it only by one bit, when it results in a power of $2$ larger than all the previously seen numbers. In this case the ${}+1$ operation involves carries all the way from the $0$th bit to the new most significant bit. Thus, the crucial thing is to investigate carries in the sequence.

For any $k\ge1$, the operations of $\oplus$ and ${}+1$ are well defined modulo $2^k$, hence we can look at the sequence $a_n\bmod2^k$. Since the sequence is uniquely reversible mod $2^k$ by $a_{n-1}=a_n\oplus(a_{n+1}-1)$, it must be periodic mod $2^k$.

When computing $a_n$, there is a carry from $(k-1)$th bit to $k$th bit iff $a_n\equiv0\pmod{2^k}$; for $k>1$, this holds iff there was a carry to the $(k-1)$th bit, and the $(k-1)$th bit of $a_n$ is $0$. Let us denote the $k$th bit of $a_n$ as $a_{n,k}\in\{0,1\}$.

Case 1: $a_n\bmod2$ (that is, $a_{n,0}$) is $\dots1111\dots$. Then there are no carries whatsoever, hence $a_n=O(1)$ and we are done.

Case 2: $a_n\bmod2$ is $\dots001001001\dots$ of period $3$. Carries from $0$th to $1$st bit happen at the positions of the $0$s in the period. (Here and below, the pattern shown is not necessarily aligned with the start of the sequence, hence strictly speaking the period is one of its cyclic shifts.)

This again splits to two subcases:

Case 2a: $a_n\bmod4$ is $\dots122320122320\dots$ of period $6$. That is, the sequence of $a_{n,1}$ is $\dots\O{\U0}\U11\U1\U10\dots$, where underlines signify carries from the $0$th bit to the $1$st bit, and overlines carries from the $1$st bit to the $2$nd bit.

Case 2b: $a_n\bmod4$ is $\dots120300120300\dots$ of period $6$; that is, the sequence of $a_{n,1}$ is $\dots0\U1\O{\U0}1\O{\U0}\O{\U0}\dots$.

I claim that in Case 2a, for all $k\ge2$, the sequence $a_n$ has period $3\cdot2^{k-1}$ modulo $2^k$, and there is carry to the $k$th bit at exactly one position per period.

This is proved by induction on $k$. It holds for $k=2$. When going from $k$ to $k+1$, we see that the sequence $a_{n,k}$ is a $\oplus$-linear combination of:

  1. A solution of the homogeneous recurrence $b_n=b_{n-2}\oplus b_{n-1}$ modulo $2$. This is either $\dots00000\dots$, or (some shift of) $\dots011011011\dots$.

  2. One particular solution of $b_n=b_{n-2}\oplus b_{n-1}\oplus c_n$, where $c_n$ is the sequence of carries to the $k$th bit. By the induction hypothesis, $c_n$ is $3\cdot2^{k-1}$-periodic, and the period has the form $100\dots0$. Thus, one solution $b_n$ is given by the $3\cdot2^k$-periodic sequence consisting of $110110110\dots110$ for $3\cdot2^{k-1}$ positions, followed by $00\dots0$ for $3\cdot2^{k-1}$ positions.

Clearly, this makes $a_{n,k}$ (and thus $a_n\bmod2^{k+1}$) $3\cdot2^k$-periodic. Carries to the $(k+1)$th bit may happen only at the two positions in this period that correspond to carries to the $k$th bit; these two positions are at distance $3\cdot2^{k-1}$ apart, and they are occupied by two opposite bits: the sequence from 1. gives them the same value, whereas the sequence from 2. gives them opposite values. Thus, exactly one of them gives rise to a carry to the $(k+1)$th bit.

In Case 2b, a similar inductive argument establishes the following claim: for any $k\ge2$, $a_n\bmod2^k$ is $3\cdot2^{k-1}$-periodic, and there are exactly $3$ carries to the $k$th bit in each period. Two of these carries have the same position modulo $3$, whereas the third is at relative position $2$ modulo $3$ with respect to them.

This implies a bound on $a_n$ as follows. For a given $n$, let $k$ be the least integer such that $n<3\cdot 2^k$ and $p,q<2^{k+1}$. Thus, $2^k\le\max\{p,q,2n/3\}$. We know from above that up to $a_n$, there are at most three carries to the $(k+1)$th bit. The first of these will attain the value $2^{k+1}$, the other two may at most get to $2^{k+3}$. Thus, the most significant bit of $a_n$ is at position at most $k+3$. Actually, taking into account the relative position of the carries modulo 3, one can check that the most significant bit can only become at most $k+2$. Thus, $a_n<2^{k+3}\le\max\{16n/3,8p,8q\}$.

$\endgroup$
9
  • $\begingroup$ Which operator has precedence? Xor operator or the plus 1? Does your analysis apply to either case? Gerhard "Uses A Lot Of Parentheses" Paseman, 2018.05.22. $\endgroup$ May 22, 2018 at 17:52
  • $\begingroup$ It didn't occur to me that it is ambiguous. I'm reading the definition as $a_n=(a_{n-1}\oplus a_{n-2})+1$. $\endgroup$ May 22, 2018 at 19:44
  • $\begingroup$ This agrees with what I tried. In low bits we have some "initial conditions" that are not necessarily $00$, which makes life a bit more complicated. If you ignore silent periods of length divisible by $3$, my PC found 7 possible carry patterns starting from the first carry that can in principle establish themselves: $(1),(110),(101),(100),(101100),(110010),(100101)$ (of course some of them are just cyclic shifts of other ones). On high bits we always start with $00$, so, indeed, only $(100), (101100),(100101)$ survive and your analysis applies. I also assumed that xor is applied first. $\endgroup$
    – fedja
    May 22, 2018 at 23:15
  • $\begingroup$ @fedja I don't quite understand what you are saying. The sequence is always fully periodic modulo $2^k$, the "initial conditions" will be part of the period. Maybe my notation was unclear, but I tried to indicate with the leading $\dots$ that the periodic part that I displayed is taken from somewhere in the middle, hence it is not necessarily aligned with the beginning of the sequence. That is, the patterns given in cases 2, 2a, 2b are supposed to include arbitrary cyclic shifts. One may also imagine the sequence extended down to all integer indices $\dots a_{-2},a_{-1},a_0,a_1,a_2\dots$, $\endgroup$ May 23, 2018 at 7:01
  • $\begingroup$ ... in which case the starting position becomes immaterial. (Then the values may become negative: we treat them as in 2's complement notation.) $\endgroup$ May 23, 2018 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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