Question

Develop a test for divisibility for guessing a number between 1and $2^{\mathrm{n}}-1$by successively guessing each bit in its binary expansion.

Short answer

Note: Explained in step 1

Step-by-step solution

Step 1

We need to devise an algorithm for guessing a number between 1 and $2^{\mathrm{n}}-1$.

Let somebody choose a number between 1 and $2^{\mathrm{n}}-1$.

Then ask this person to write the number in binary notation.

You first ask the person the person if the first bit is a 1.

Then you ask the person if the second bit is a 1.

Then you ask the person if the third bit is a 1 .

And so on, until you asked this for the nth bit.

When you know the answer to these n questions, then you know the number in binary notation and thus you can then rewrite the number in decimal notation.