Dividing Binary by Five

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.

  1. The first bit received is the least significant bit, and each following bit represents the next larger power of 2 in the large number.
  2. The first bit received is the most significant bit, and each following be represents the next lower power of 2 in the large number.
  3. 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.


Solution
Mail to Ken