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.

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