6
$\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$
  • 2
    $\begingroup$ Is it not possible to brute-force that range of numbers? In particular with some clever dynamic programming? $\endgroup$ – Per Alexandersson May 21 '18 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 '18 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$ – Jeppe Stig Nielsen May 21 '18 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 '18 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$ – Per Alexandersson May 21 '18 at 13:18
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$
  • $\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$ – Gerhard Paseman May 22 '18 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$ – Emil Jeřábek May 22 '18 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 '18 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$ – Emil Jeřábek May 23 '18 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$ – Emil Jeřábek May 23 '18 at 7:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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