~J(n)~ siempre parece ser impar. Y de hecho, hay una buena razón para esto: El primer viaje alrededor del círculo elimina todos los números pares. Además, si ~n~ en sí mismo es un número par, llegamos a una situación similar a la que comenzamos, excepto que solo hay la mitad de personas, y su número ha cambiado.

Así que supongamos que originalmente tenemos ~2 \cdot n~ personas. Después de la primera vuelta a la redonda, borramos todos los números pares, esto es como empezar con n personas, excepto que el número de cada persona se ha duplicado y reducido en 1. Eso es, ~J(2 \cdot n) = 2 \cdot J(n) - 1~, para ~n~ par.

Pero, ¿qué pasa con el caso impar? Con ~2 \cdot n + 1~ personas, resulta que la persona número ~1~ desaparece justo después de la persona número ~2 \cdot n~, y nos quedamos de nuevo, casi tenemos la situación original con ~n~ personas, pero esta vez su los números se duplican y aumentan en ~1~. Por lo tanto ~J(2 \cdot n + 1) = 2 \cdot J(n) + 1~, para n impar. La combinación de estas ecuaciones con ~J(1) = 1~ nos da una recurrencia que define ~J(n)~ en todos los casos:

• ~J (1) = 1~;
• ~J(2 \cdot n) = 2 \cdot J(n) - 1~ si n es par
• ~J(2 \cdot n + 1) = 2 \cdot J(n) + 1~ si n es impar

Con esto podemos resolver cada caso en ~O(\log{n})~.

Bonus: Resuelva el problema en ~O(1)~.