I'm working on a function in Python that visualizes two marked disks of size i and o. 1 <= i, o <= 2^48. They are marked with numbers from zero through their size i.e. 0, 1, 2, ...i+1. Starting on their Zeroes, every unit of time, d(i) rotates clockwise and d(o) rotates counterclockwise until their number matches (not including t=0). Therefore it can look like this where i=5 and o=5. Consider the question mark pointing to the current value on the wheel:
[1 2 3 4 5 **0**] < ? > [**0** 1 2 3 4 5] t = 0
[0 1 2 3 4 **5**] < ? > [**1** 2 3 4 5 0] t = 1
[5 0 1 2 3 **4**] < ? > [**2** 3 4 5 0 1] t = 2
[4 5 0 1 2 **3**] < ? > [**3** 4 5 0 1 2] t = 3 <<< Therefore my answer is t=3.
Note that since i rotates clockwise the number being pointed to decreases. The opposite is true for o.
Up until now I've been simulating this rotation with modulo arithmetic in Python by brute-forcing t=0 through t=i*o. (Sorry if my Math syntax isn't up to snuff)
The problem I'm having is that the lower bound isn't tight enough, so for example if the problem isn't solved until turn t=9000 I can't compute thousands of unnecessary turns. I want to know how to algebraically find a better lower bound that is < t*o.
If I call the lower bound lb (so currently lb=0), I've tried lb = abs(i-o) but found that it was too tight and omitted earlier successful turns.
Some samples of data is below. Data in the i column is of course == i. The same goes for o. Winning t is the lowest t>0 where the values match. How can I find the relationship between i,o and t? Perhaps not a direct relationship, but some way that allows me to establish lb without skipping a win condition.
So after $t$ steps, disk $d(i)$ shows $t\bmod {i+1}$ and $d(o)$ shows $-t\bmod {o+1}$. Upon a match these are equal, i.e., there is an integer $a$, $0\le a\le \min\{i,o\}$, and integers $r\ge 0$, $s>0$ such that $t=a+r(i+1)$ and $-t=a-s(o+1)$. Eliminating $t$, $$ 2a=s(o+1)-r(i+1).$$ Similarly, $2t=s(o+1)+r(i+1)$, so we want to minimize $s$ and $r$. Consider the case $o\ge i$ (the case $i\ge o$ working similarly by symmetry). Then using division with remainder, we can write $o+1=q(i+1)+b$ with $0\le b\le i$. If $b$ is even, then $$s=1, r=q, a=\frac b2, t=\frac{o+1+q(i+1)}2=o+1-\frac b2$$ is a solution and clearly minimal. If on the other hand, $b$ is odd, then $$s=2, r=2q, a=b, t=o+1+q(i+1)=2(o+1)-b$$ is a solution and again is minimal because $s=1$ could not work.
In summary, $$t =c\cdot\left(2\max\{o+1,i+1\}-(\max\{i+1,o+1\}\bmod\min\{i+1,o+1\})\right)$$ where $$c=\begin{cases}1&\max\{i+1,o+1\}\bmod\min\{i+1,o+1\}\text{ is odd}\\ \frac12&\max\{i+1,o+1\}\bmod\min\{i+1,o+1\}\text{ is even} \end{cases} $$