Using your Head is Permitted

February 2012 riddle

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 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.


To solution

Back to main page