# The mysterious operation $\oplus$

We are given an operation $$\oplus$$ that is associative and commutative, has $$0$$ as a neutral element, and we know:

• $$1/10 \oplus 1/6 = 5/29$$
• $$1/6 \oplus 2/3 = 7/10$$
• $$1/5 \oplus 2/5 = 3/7$$
• $$1/4 \oplus 3/4 = 2/3$$
• $$3/5 \oplus 1/3 = 3/4$$
• $$5/8 \oplus 7/8 = 10/27$$
• $$1/7 \oplus 1/7 = 0$$
• $$1/6 \oplus 1/5 = 2/9$$
• $$4/5 \oplus 1/5 = 3/4$$
• $$2/3 \oplus 3/4 = 1/4$$
• $$1 \oplus 1/2 = 2$$
• $$1 \oplus 2/3 = 3$$
• $$2 \oplus 2/5 = 4$$
• $$3 \oplus 2/7 = 5$$

Question. $$4/5 \oplus 5/6 = ?$$

Bonus question: $$1 \oplus 1/3 \oplus 1/5 \oplus 1/7 \oplus 1/9 \oplus \ldots = ?$$

• Are the numbers written as X/Y fractions as defined in 'regular' mathemathics or are they just a way to denote number pairs? Will X⊕1/2 be equal to X⊕2/4? – jarnbjo May 29 at 10:30
• @jarnbjo guessing by the fact that some are just the one number, one ought to assume they are regular fractions – micsthepick May 29 at 10:48
• That's right @micsthepick – Dominic van der Zypen May 29 at 10:49
• By any chance was this question inspired by this one? – TheSimpliFire May 29 at 19:27
• No, it wasn't, @TheSimpliFire, but that question is interesting, too! – Dominic van der Zypen May 30 at 4:15

## 2 Answers

The operation $$\oplus$$ is bitwise XOR, with non-negative fractions mapped via the Stern-Brocot tree to dyadic rationals from 0 to 1.

For example, take $$2 \oplus \frac{2}{5}$$. Look at the first few layers of the Stern-Brocot tree drawn above and imagine the bottom line of number as a "ruler" divided into 32 equal sections. The horizontal position of the fraction $$2/1$$ in the tree maps to the $$3/4$$-point of the ruler, and $$2/5$$ to $$3/16$$-point. The denominators are always powers of 2, so can write them as terminating binary representations $$0.11_2$$ and $$0.0011_2$$. If we do bitwise XOR on each place value, we get $$0.1111_2$$, which is $$15/16$$.

    3/4  = 0.110000....
^   3/16 = 0.001100....
--------------------
15/16 = 0.111100....


The XOR is just adding without carrying. We look at each place value column separately, and write a 1 where the two summands are different and 0 where they are same.

Finally, we need to convert the position on the ruler back to a fraction in the tree. If we look 15/16 of the way on the ruler, we find fraction $$4/1$$ or $$4$$. So, $$2 \oplus \frac{2}{5} = 4$$.

Each successive layer of the Stern-Brocot tree is mapped to finer and finer dyadic rationals with increasingly large power-of-two denominators, like the marks on a ruler can yet finer marks placed at the halfway points.

Whereas each new mark is at a position that's the average of the two on either side, the corresponding fraction in the tree is the mediant of the two surrounding it, where the mediant of $$a/b$$ and $$c/d$$ is $$(a+b)/(c+d)$$. The rationals produced this way in the tree are all in simplified form.

We can answer the puzzle's question by computing $$4/5 \oplus 5/6$$ and get $$1/6$$

4/5 -> 15/32 = 0.111110000...
5/6 -> 31/64 = 0.111111000...
-----------------------------
1/6 ->  1/64 = 0.000001000...


Since bitwise XOR is clearly commutative and associative, so is the operation $$\oplus$$ which has just relabeled the dyadic fractions on $$\left|0,1\right)$$ as non-negative rationals in simplest form. This is also suggested by the puzzle using the symbol $$\oplus$$, which is commonly used for XOR. The identity is zero in both cases. Since any number XOR'ed with itself is zero, we too have the identity $$x \oplus x = 0$$.

For the bonus question $$1 \oplus 1/3 \oplus 1/5 \oplus 1/7 \oplus \cdots$$, we do:

1/1 -> 1/2   = 0.100000000...
1/3 -> 1/8   = 0.001000000...
1/5 -> 1/32  = 0.000010000...
1/7 -> 1/128 = 0.000000100...
...
-----------------------------
?   -> 2/3   = 0.101010101...


In the end, we're looking for a value in the tree positioned over $$2/3$$ on the ruler. This clearly can't be a rational, since those map to dyadic fractions. But, we can find a real number with the appropriate limit. To take the path to $$2/3$$ on the number line, we alternate going right and left down the Stern-Brocot tree, which takes us down the fractions:

$$\frac{1}{1}, \frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{13}{8}, \dots$$

These are of course ratios of successive Fibonacci numbers, corresponding to iterating the map $$\frac{p}{q} \to \frac{p+q}{p}$$, and their limit is the Golden Ratio $$\phi \approx 1.618$$. So, $$1 \oplus 1/3 \oplus 1/5 \oplus 1/7 \oplus \dots = \phi$$.

• I noticed how much this function was like xor, but I had absolutely no knowledge of anything that might work. – micsthepick May 30 at 10:50
• it's fitting that xnor answer's the question that involves xor :) – micsthepick May 30 at 10:51
• Damn it. I actually drew a Stern-Brocot tree yesterday while looking at this... – Gareth McCaughan May 30 at 10:52
• Wonderful answer!! – Dominic van der Zypen May 30 at 15:02

Firstly, we notice:

$$1/4 \oplus 3/4 = 2/3$$
$$2/3 \oplus 3/4 = 1/4$$

So I have interpreted this generally to allow $$x \oplus y = z \iff z \oplus y = x$$

Also we have:

$$1/4 \oplus 3/4 = 2/3$$
$$4/5 \oplus 1/5 = 3/4$$

So again, in general $$1/n \oplus (n-1)/n = (n-2)/(n-1)$$

Hence $$5/6 \oplus 1/6 = 4/5$$

And finally:

$$1/7 \oplus 1/7 = 0$$

implies $$x \oplus x = 0$$

And so to the question:

Question. $$4/5 \oplus 5/6 = ?$$

$$4/5 \oplus 5/6$$

$$= (3/4 \oplus 1/5) \oplus (4/5 \oplus 1/6)$$
$$= 3/4 \oplus (1/5 \oplus 4/5) \oplus 1/6$$
$$= 3/4 \oplus 3/4 \oplus 1/6$$
$$=0 \oplus 1/6$$
$$=1/6$$

• Isn't the answer be equal to the ROT13(gur guveq grez, nf gur svefg naq frpbaq pnapryf rnpu bgure)? – athin May 30 at 8:21
• @athin; good spot! fixed. – JonMark Perry May 30 at 8:26
• @athin; which actually is what axiom 2 says! – JonMark Perry May 30 at 8:30
• The 4/5+5/6 thing can be deduced simpler. If rot13(k cyhf l rdhnyf m vzcyvrf m + l rdhnyf k), then rot13(vs svir fvkguf cyhf bar fvkgu vf sbhe svsguf, fb svir fvkguf cyhf sbhe svsguf vf bar fvkgu (pbzzhgngvivgl)) – trolley813 May 30 at 8:34
• I tried using logic like this, but I kept either getting worse and worse expressions, or in loops :) – micsthepick May 31 at 1:05