Counting in different bases

Question

If you want to count over 8 bits, in base 2, the result is like this:

0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1;
0 0 0 0 0 0 1 0;
.....
1 1 1 1 1 1 1 1;

But how can you make an algorithm that counts - for each bit - based on a different bases, ex: If the least significant bit is counted according to base 5 and the most significant one is on base 2, the result should look like:

0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1;
0 0 0 0 0 0 0 2;
0 0 0 0 0 0 0 3;
0 0 0 0 0 0 0 4;
1 0 0 0 0 0 0 0;
1 0 0 0 0 0 0 1;
1 0 0 0 0 0 0 2;
...
1 0 0 0 0 0 0 4;

Can you please give me the algorithm that generates these vectors?

Answer 1

One algorithm for this problem is the kind of "ripple-carry" addition most students typically learn in kindergarten, except slightly modified. When you add two numbers, you do so digit-by-digit: first the ones place, then the tens place, then the hundreds place, etc. If you would ever had to write down a number larger than 10 (e.g. 7+8=15), then you write it down minus-10 and "carry" the 10 over to the next place, where you add it (it becomes a 1); this might "ripple" over many places (e.g. 999+1=1000). By repeatedly adding one using this algorithm, we can count up one-by-one.

It is important to clarify what we're after: what does it mean for different places to have different bases. If you allow places to have arbitrary number ranges, and stand for arbitrary numbers, then some bad things can happen: a number can be written in more than one way, and/or some decimal numbers cannot be written. Therefore we will limit ourselves to a "sane" scheme where if a place i has a base b_i, that means the valid digits are 0,1,2,...,b_i-1 (as usual, just like in decimal), and that digits in that place represents b_i times the product of all bases on the right (b_i-1 x b_i-2 x ...). For example, if our bases were [10,10,10], the values of the digits would be [1000,100,10,1]; if our bases were [5,10,5], the values of the digits would be [250,50,5,1]

How to add 1 to a number:

Increment the least-significant digit (LSD)
Perform ripple-carry as follows:
    Set the current place to the LSD
    Repeat as long as the current place exceeds its allowed max digit:
        Set the digit at the current place to 0
        Advance the current place one to the left
        Increment the number at the new place (now on the left)

Repeat the above algorithm until you have all numbers you desire.

Python:

from itertools import *

def multibaseCount(baseFunction):
    currentDigits = [0]
    while True:
        yield currentDigits[::-1]

        # add 1
        currentDigits[0] += 1

        # ripple-carry:
        for place,digit in enumerate(currentDigits):
            if currentDigits[place]>=baseFunction(place):    # if exceeds max digit
                currentDigits[place] = 0         # mod current digit by 10
                if place==len(currentDigits)-1:  # add new digit if doesn't exist
                    currentDigits += [0]
                currentDigits[place+1] += 1      # add 1 to next digit
            else:    # doesn't exceed max digit; don't need to carry any more
                break

Demo, where place n has base n+1:

>>> for digits in islice(multibaseCount(lambda n:n+1),30):
...     print( ''.join(map(str,digits)).zfill(5) )
... 
00000
00010
00100
00110
00200
00210
01000
01010
01100
01110
01200
01210
02000
02010
02100
02110
02200
02210
03000
03010
03100
03110
03200
03210
10000
10010
10100
10110
10200
10210