Valhalla Legends Archive

I've been sitting here, studying for yet another one of my finals, and my mind drifted off to math, as it often does. I've come up with a riddle.

Given are the n'th power of 2: 2^n, and the decimal representation of an integer: X.

My riddle is: How do you check whether X is divisible by 2^n?

The restriction to make this interesting is that you can't perform any division or modulo (so you can't just calculate and check whether X / 2^n is an integer). You may use addition, subtraction, multiplication.

[Edit: Grammar]

while(X >= pow(2, n)) X = X - pow(2, n);
if(X == 0) printf("It was divisible!\n");

edit: removed X = 0 and 2**n pseudocode, to avoid complaints

Alternative:

Calculate X * 5**n and see if the number ends in n zeroes. If it does, you win.

Finally, after solving it with subtraction and multiplication, solution with addition:

for( Y = 0; Y < X; Y += pow(2, n));
 if(Y == X)
   printf("Divisible!\n");
 else
   printf("Not divisible!\n");

Your 1st and 3rd posts were an alternative modulo and weren't my point.

Your 2nd post is exactly what I meant. Good job

(Somehow, I knew it'd be you who would solve it first / at all, but oh well...)

Quote from: Yoni on May 29, 2004, 06:44 PM
Your 1st and 3rd posts were an alternative modulo and weren't my point.

Your 2nd post is exactly what I meant. Good job

(Somehow, I knew it'd be you who would solve it first / at all, but oh well...)

Actually, isn't #2 just an alternative modulo too...? I turn the question of mod2 into a question of mod10? I took the hint for that from the word "decimal" in your problem specification. Good one

Yes, it's mod 10^n, hence I said "decimal representation" to have that implicitly allowed.

Hmm, can't see how the representation you put it in makes any difference ... if the number was in binary, would shifting it right and checking whether you shift out zeroes or ones not be a way of doing a division? Seems like one to me... Also, when calculating X * 5^n, you'll most probably be turning it into binary in a calculator or computer anyway

Not necessarily

Yes, but what do you call the operation "count the zeros"?

The "cheating unless I say so" operation.

Just a little tip... You know Multiplication is the opisite of Divion... Just flip the devisor and times that.  

EX:  8 / 2 = 4

Then 8 * .5 = 4

Should help out a bit..

True, but the point was to use only integers, so you can't multiply by 0.5. Else it'd be too obvious.

I did at first say something like "oh, and you can't multiply by 0.5^n" in the first post, but that's too much of a clue so I edited it out. Consider the difference between 0.5^n and 5^n. The first is also equal to 5^n/10^n. The second leaves the zeroes intact. Yes?