A computer receives a series of binary digits (1s and 0s) representing a large number. Devise an algorithm that can decide after each bit if the number accumulated so far is divisible by 5. You cannot simply divide by 5 because you do not have infinite storage to store the incoming bit stream.

- The first bit received is the least significant bit, and each following bit represents the next larger power of 2 in the large number.
- The first bit received is the most significant bit, and each following be represents the next lower power of 2 in the large number.
- Can either of these situations be easily extended to decide divisibility by other values (i.e. 10, 13, 100)?

Source: 1. Emanuel Manasci, citing a past interview question. 2&3. Original Extensions.

Solutions were received from Jim Gillogly, Dan Chirica, Kirk Bresniker, Joseph DeVincentis, Al Zimmermann. Basically two different solutions were proposed. The different variations are shown below.

First is an algorithmic approach, to verify the proper remainder as each bit is received. Jim Gillogly's summary is similar to many others':

Part 1: Algorithm: Accumulate current value of N mod 5, noting that 2^n mod 5 cycles through 1, 2, 4, 3 in a repeating sequence. We can count 1, 2, 4, 3, 1, ... with (2 * n) mod 5. 1. Initialize next = 1, mod = 0 2. b = Incoming bit If (b == 1) mod = (mod + next) % 5 next = (2 * next) % 5 if (mod == 0) print "Divisible by 5." else print "Not divisible by 5." go to 2 Part 2: This is easier: as we add a low bit we double the accumulated remainder (mod 5). 1. Initialize mod = 0 2. b = incoming bit mod = (mod * 2) % 5 if (b == 1) mod = (mod + 1) % 5 if (mod == 0) print "Divisible by 5." else print "Not divisible by 5." goto 2 Part 3: Yes. In each case above we can replace 5 with the target divisor (10, 13, 100, etc.) and the algorithm still works. It can also be extended to different bases -- for example, one could use this algorithm to do trial division in a factoring program a word at a time, in which case the simpler form of Part 2 would suggest doing it from the top.

Dan Chirica suggested keeping track of groups of bits. This approach was a new idea to me. I'm not sure if this method is completely foolproof, but it's worth contemplating:

I think you can keep count of groups of four and add them because 1111 divisible by 5 example 205 1100 1101 12 +13 = 25 dovisible 715 10 1100 1011 2 + 12 + 11 = 25 8155 1 1111 1101 1011 1 + 15 + 13 +11 30 divisible and so on in second case, with the most significant bit received first, you can apply the same rule, but complete with zeros, up to multiply of four: you have to keep an accumulator of 4 bits: example 70 1000 110 put one zero to the last group of three 1000 + 1100 = 8 + 12 = 20 divisible by 5 45 1011 01 1011 + 0100 = 11 + 4 = 15

Mail to Ken