For a given n what is the smallest number greater than n, not a multiple of n, but containing n in its binary representation?

Answer within 30 sec.

(In reply to re(3): Clarification? by Charlie)

Well that's why I asked my original question, because I don't think the problem is really worded that clearly.  I said, for example, if n = 2 is the answer 101, and Ady said yes.  If he meant that the answer for n = 2 is 5 (which is 101 in binary) then there was some confusion.

The problem states:

"For a given n what is the smallest number (call it X) greater than n, not a multiple of n, but containing n in its binary representation?"

I added the parenthetical just to help keep track of what's what.

It's the "its" at the end that is ambiguous.  "Its" can't refer to X, because for most n, the binary representation of X will never contain the digits of n.  So I assumed (and I mistakenly thought Ady confirmed) that "its" refers to n, not to X.

I see that the problem probably intends for you to find something like this:

"For a given n, what is the smallest number X such that X is greater than n, X is not a multiple of n, and the binary representation of X contains the digits of the binary representation of n."

In that case, the solution (I think) is simply 2n+1.  2n will shift all the digits in bin(n) one place to the left, and then adding 1 ensures that it is not divisible by n. 

 

Posted by tomarken on 2014-04-03 12:34:22