Optimal algorithm for finding the odd sphere with a balance scale Say we have $N$ spheres indexed as $1,2,3,\dotsc, N$ such that all of them have identical weight apart from one, and we don't know if that one is heavier or lighter. We have to determine which sphere has the odd weight using just a balance scale. We could solve this problem by weighing repeatedly, but I am interested in a solution involving weighing as few times as possible, so my question is what is the optimal algorithm for this task?

This looks like a generalization of the classic $12$ ball problem.

You should be able to modify Jack Wert's wonderful algorithm, (which was designed for the case when $N= \dfrac{3^m - 3}{2}$) to work for any $N$. I believe I had made an (incomplete) attempt when someone asked this on stackoverflow.

Note that the numbers $\dfrac{3^m - 3}{2}$ are special, in the sense that they are the turning points.

In the variant of the problem where you are also required to tell if the odd sphere is heavier or lighter, for $\dfrac{3^m -3}{2} \lt N \le \dfrac{3^{m+1}-1}{2}$, the optimal number of weighings can be shown to be $m+1$.

If you are only required to find the odd sphere and not necessarily figure out if it is heavier or lighter, the turning points are $\dfrac{3^m -3}{2} + 1$.