Hacker News Reader

Comment by tomtomtom777 | Hacker News Reader

Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.

View on HN

Combining two consecutive integers starting with an even one yields one.

  xxxxxxx0 ^ xxxxxxx1 = 00000001

If we start at a number divisible by four and do this twice, we get one twice.

  xxxxxx00 ^ xxxxxx01 = 00000001
  xxxxxx10 ^ xxxxxx11 = 00000001

And combining the two of course yields zero and we are right back at the start.

Another interesting fact is that each time you make the xor of four consecutive numbers, beginning with an even number, the result is zero. Example in J.

  xor =: (16 + 2b0110) b.
  f =: 3 : 'xor/ y + i. 4'
  f"0 ] 2 * 1 + i. 100

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Summing a hundred millions: +/ f"0 ] 2 * i 100000000 gives zero (it takes a few seconds). So it seems the stated property holds for every even n.

Yes, because XORing two consecutive integers only differing in the least significant bit yields one.

  xxxxxxx0 ^ xxxxxxx1 = 00000001

Doing this twice with four consecutive numbers then also cancels the remaining one. That also means that you do not have to use consecutive numbers, you can use two arbitrary pairs

  2m ^ 2m + 1 ^ 2n ^ 2n + 1

and for example

  16 ^ 17 ^ 42 ^ 43

should be zero.

There are essentially two bits of information in the 'state' of this iterated algorithm: a) Are all the non-lowest bits zero, or are they the value of the latest N b) the value of the lowest bit

So the cycle of (N, 1, N+3, 0) corresponds to (A) and (B) being: (0,0), (0,1), (1,1), (1, 0) - i.e. the 4 possible combinations of these states.

If we generalize the problem to base k (they are k-1 duplicate of each number except the missing number, find missing one using base k-wise addition) then we can see the cycle is the smallest number such the base k-wise addition from 1 to the number is zero and it is power of k will form a cycle. I'm not sure if all such numbers are power of k if they exists or if there is an upper bound on them. For example in base 4 there appears to be no such cycle.

I made an arithmetical mistake in base 4, so I was wrong. I also wrote they are instead of there are.

I think the following is true: For even k the cycle is k^2 long and for odd k is k long. Why? because units' place of generalized xor from 1 to k-1 is (k^2-k)/2 and therefore zero mod k if k is odd, if k is even then if we repeat it twice we get zero. For the second digit, k times the same digit will always give zero. Thus for odd k we have a zero when n is divisible by k and for even k we have a zero when n is divisible by 2k and the smallest power of k divisible by 2k is k^2 so it must be the cycle length.

Reply on news.ycombinator.com