Devise a polynomial-space algorithm that accepts three integers:
n, A and i as inputs, and finds the
n'th bit in the binary representation of Ai.
"Polynomial-space" means that there exists a constant k, such that for sufficiently large n, A and i, the algorithm can run on a machine that has only log(nAi)k bits of memory.
List of solvers:Lin Jin (23 February 21:31)
Daniel Bitin (24 February 10:40)
Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.
The solution will be published at the end of the month.
Back to main page