2

While testing for a program, I found that 

0 xor 1 xor 2 xor ... xor 1000000 = 1000000

and it is true for the numbers in this form except for 10:

1 1 true
10 11 false
100 100 true
1000 1000 true
10000 10000 true
100000 100000 true
1000000 1000000 true
10000000 10000000 true
100000000 100000000 true
1000000000 1000000000 true

(the true means it follows the rule and false means it doesn't).

Is there any theorem that is related to this? And what is so special about the number 10?

The program in Ruby if you are interested to try out:

n = 1
10.times do
   r = (0..n).inject(:^)
   puts "#{n} #{r} #{n == r}" 
   n *= 10
end
nonopolarity
  • 495
  • 1
    Hint: The xor of $4k, 4k+1, 4k+2, 4k+3$ is zero. Only 1 and 10 are not multiples of four. – Brian Moehring Aug 19 '19 at 02:16
  • @BrianMoehring Interesting.. does a^b mean bitwise xor between the decimal integers a and b after converting them to binary? – AgentS Aug 19 '19 at 03:26
  • 1
    @ganeshie8 yes... and xor has the property that 0 xor with anything (0 or 1) leaves it alone, and 1 xor with anything flips the bit – nonopolarity Aug 19 '19 at 03:49
  • 1
    @ganeshie8 Yes. The caret (^) is one of the common symbols for the bitwise-exclusive-or operator. I didn't know it was in Ruby as well, but looking it up was not too hard. – Brian Moehring Aug 19 '19 at 03:49
  • Ahh gotcha.. thank you both :D – AgentS Aug 19 '19 at 03:56

1 Answers1

2

You have noticed what I would consider an incidental pattern. The actual underlying pattern comes from the fact that for any non-negative integer $k,$ $$(4k) \oplus (4k+1) \oplus (4k+2) \oplus (4k+3) = 0$$ (here, I use $\oplus$ for the bitwise xor operator, which is the more common notation outside programming languages)

For any non-negative integer $n,$ we may find unique non-negative $q,r$ such that $r < 4$ and $n = 4q+r.$ Using the above identity as a guide, we then write the bitwise xor of all the numbers from $0$ to $n$ as $$\bigoplus_{i=0}^n i = \bigoplus_{k=0}^{q-1}\left((4k)\oplus(4k+1)\oplus(4k+2)\oplus(4k+3)\right) \oplus \bigoplus_{k=0}^{r-1}(4q+k) \oplus n = \bigoplus_{k=0}^{r-1}(4q+k) \oplus n$$ which implies $$n = \bigoplus_{i=0}^n i \iff \bigoplus_{k=0}^{r-1} (4q+k) = 0$$ From here, we can see that this is true if and only if either $r=1,q=0$ or $r=0.$ In terms of $n,$ this becomes $$n = \bigoplus_{i=0}^n i \iff n=1 \text{ or } n \text{ is a multiple of } 4$$

Going back to your observation, $n=10$ is the only one that is neither equal to $1$ nor a multiple of $4.$

Brian Moehring
  • 21,088
  • Neat! Brian XD I'm messing with something related on my scratch paper and your proof above just came in handy! for $m>1$ is below true? $$\bigoplus\limits_{i=0}^{2^m-1} (2^mk+i) = 0$$

    $m=2$ case gives

    $$4k\oplus (4k+1)\oplus (4k+2)\oplus (4k+3)=0$$

     – AgentS Aug 19 '19 at 05:18
  • 1
    @ganeshie8 Yes, that will be true. I didn't prove my statement (for $m=2$) but the proof of both is a corollary of the property that for non-negative $a,b,c,d,n,$ with $b,d < 2^n,$ we have $$(a\cdot 2^n + b) \oplus (c\cdot 2^n+d) = (a\oplus c)\cdot 2^n + (b\oplus d)$$ (along with $x \oplus x = 0),$ which basically just says we can compute the bitwise xor "block-wise" – Brian Moehring Aug 19 '19 at 06:48
  • You've put it in such elegant way. basically just shifting left and then xoring the lsb s... – AgentS Aug 19 '19 at 06:54
  • Wish I could upvote your answer 100 times :D – AgentS Aug 19 '19 at 06:57