IBM Ponder This #140 · December 2009

Let x be a 25-bit number, such that the product of (x & m_i) for i=1,...,10 is a nontrivial integer power (n^k, n and k are integers, n>0 and k>1); where "&" stands for the Boolean bitwise AND function and the 10 hexadecimal masks mi are {0x1f, 0x3e0, 0x7c00, 0xf8000, 0x1f00000, 0x108421, 0x210842, 0x421084, 0x842108, 0x1084210}.

Find the minimal number of mask questions needed to find x, where a mask question m is asking whether (x&m) is zero.

It can be shown that, in our case, if x is known to be in a subset whose size is at most 4, then 2 mask questions would suffice to find it.

Submit your answer as a N-2 mask questions which when asked together (e.g. asking the third question without knowing the answer to the first two), would divide the set of possible numbers x into subsets of no more than 4 numbers each. You need not specify the last two which are composed based on the previous answers.

Update 12/04: The product should be an integer power of a *prime* number. Sorry for that and thanks for all the devoted solvers who tried the misleading version.

Update 12/09: Though x is a 25-bit number, it does not necessarily start with a leading 1.

Solution

Best opened after a real attempt

To be added.