Timeline for A Bitwise Xor Problem
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2018 at 19:46 | comment | added | Emil Jeřábek | I can improve the bound to $a_n\le\frac83n+8\max\{p,q\}$. Numerical evidence suggests that the optimal bound along these lines should be $\frac83n+5\max\{p,q\}$. The worst case behaviour seems to be exhibited by initial data of the form $(p,q)=(2^k+1,2^k-2)$. | |
| May 23, 2018 at 12:30 | comment | added | Emil Jeřábek | @fedja All right, thank you. @ zbh2047 It’s good to know that the bounds are not far away from the truth. I believe there is still room for improvement in the dependence on $p$ and $q$, though of course this affects only the initial part of the sequence, not its asymptotic behaviour. | |
| May 23, 2018 at 11:27 | comment | added | fedja | @EmilJeřábek I'm just saying that I did it in a sloppier way than you, not that your solution was lacking in some respect or unclear :-) | |
| May 23, 2018 at 9:59 | comment | added | zbh2047 | I completely understand. This sulution is perfect! It has a really tight bound (in the following sutuation: $p=515,q=508$ and $n=3085$, $a_n$ have already been greater than $2^{13}-1$). $3085 \times 16/3=16453$, just greater than $2^{14}$, amazing! | |
| May 23, 2018 at 7:12 | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
clarify, and improve bound
|
| May 23, 2018 at 7:02 | comment | added | Emil Jeřábek | ... in which case the starting position becomes immaterial. (Then the values may become negative: we treat them as in 2's complement notation.) | |
| May 23, 2018 at 7:01 | comment | added | Emil Jeřábek | @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$, | |
| May 23, 2018 at 5:00 | vote | accept | zbh2047 | ||
| May 22, 2018 at 23:15 | comment | added | fedja | 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. | |
| May 22, 2018 at 19:44 | comment | added | Emil Jeřábek | 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$. | |
| May 22, 2018 at 17:52 | comment | added | Gerhard Paseman | 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. | |
| May 22, 2018 at 17:02 | history | answered | Emil Jeřábek | CC BY-SA 4.0 |