Sequence of numbers without repeating adjacent digits

Question

I would like to obtain a sequence of numbers that does not contains repeating subsequent digits in a certain base, given the base. I explain myself with an example: in base 10, the sequence will be 0, 1, ..., 10, 12, ... 21, 23, ... etc. Without numbers like 11, 125568, 220, etc.

Or, equivalently, I would like to tell that the number 521 in base 6 contains a repeating duplicate (521 in base 10 = 2225 in base 6).

Is there a way to iterate over a decimal number so that its representation in a given base does not contains any repeating duplicates? I mean, in base 6, the (decimal) number following 20 is 22 (because 20 is 32 and 22 is 34).

All of this, of course, without doing a conversion of the index in the given base and checking if there are repeating digits.

[edit] There's a way to tell if a decimal number (the index, so to say) has a duplicated consecutive digits in a certain base, so that I can skip it while generating the sequence?

Answer 1

Generating a range of numbers

To check whether a single number contains equal adjacent digits in a certain base, look at my initial answer further below. If you want to generate a range of numbers that don't have equal adjacent digits in a certain base, it's better to build the check into a generator instead of checking all numbers.

The following code example creates a table of the value of each digit in a certain base, and creates the number zero as an array of digits. Each subsequent call with the same base will increment the number, while skipping equal adjacent digits.

function next(base, reset) {
    // If this is the first call, or if the base has been changed, a
    // new table with the values of digits in this base is generated.
    if (base !== next.base) {
        initialize_table();
        reset = true;
    }
    // If reset flag is set, re-initialize array of digits to zeros.
    if (reset) {
        initialize_digits();
        return 0;
    }
    increment_digits();
    return calculate_value();

    // The distinct parts of the algorithm have been split into 
    // seperate functions for clarity; for speed, integrate them.
    function initialize_table() {
        // The base, digit value table and array of digits are stored
        // as static variables, to be re-used between function calls.
        next.base = base;
        next.table = [];
        // Set a maximum for the values in the table (here it's 32-bit
        // unsigned integers); this determines the size of the table.
        // No overflow checking is done; add this if required.
        for (var pos = 0, val = 1, step = 1; val < 4294967296; pos++){
            next.table[pos] = [0];
            for (var digit = 1; digit < base; digit++, val += step) {
                next.table[pos][digit] = val;
            }
            step = val;
        }
    }
    function initialize_digits() {
        next.digit = [];
        for (var pos = 0; pos < next.table.length; pos++) {
            next.digit[pos] = 0;
        }
    }
    function increment_digits() {
        // Find the lowest digit that can be incremented.
        // No overflow checking is done; add if required.
        var pos = 0;
        while (next.digit[pos] == base-1 ||
               next.digit[pos] == base-2 &&
               next.digit[pos+1] == base-1) {
            ++pos;
        }
        // Add 1, or 2 if adding 1 would equal the next digit.
        while (++next.digit[pos] == next.digit[pos+1]);
        // Set the lower digits to 0 or 1 alternatingly.
        for (pos-- ; pos >= 0; pos--) {
            next.digit[pos] = (next.digit[pos+1] == 0) ? 1 : 0;
        }
    }
    function calculate_value() {
        // Look up value for each digit in the table and add up.
        var val = 0;
        for (pos = 0; pos < next.digit.length; pos++) {
            val += next.table[pos][next.digit[pos]];
        }
        return val;
    }
}

for (var b = 9; b > 1; b--) {
    document.write(b + " &rarr; ");
    for (var i = 0; i < 25; i++)
        document.write(next(b) + " ");
    document.write("...<br>");
}

Checking a single number

The most efficient way (especially if you want to check several numbers with the same base) would be to first make a table of the values of each digit in that base, and then check the number against that, from high to low. That way you can avoid divisions and modulos, which are computationally expensive, and you can return as soon as you find two identical digits, without having to do a complete base conversion.

---

Let's say the base is 6, and the numbers are 16-bit unsigned integers with a maximum value of 65535, then the table would be:

position: 0     1     2     3     4     5     6
digit:
  0  ->   0     0     0     0     0     0     0
  1  ->   1     6    36   216  1296  7776 46656
  2  ->   2    12    72   432  2592 15552     -
  3  ->   3    18   108   648  3888 23328     -
  4  ->   4    24   144   864  5184 31104     -
  5  ->   5    30   180  1080  6480 38880     -

Let's say we're checking the number 49876; we start by checking the values of the digit at position 6:

49876 >= 46656 ? yes
-> digit at position 6 is 1

We then subtract 46656 from 49876 to get 3220, and go on to check the values of the digit at position 5:

3220 >= 38880 ? no
3220 >= 31104 ? no
3220 >= 23328 ? no
3220 >= 15552 ? no
3220 >=  7776 ? no
-> digit at position 5 is 0

This digit is different from the previous one. We subtract nothing from the number, because the digit is zero; then we move on to the values of the digit at position 4:

3220 >= 6480 ? no
3220 >= 5184 ? no
3220 >= 3888 ? no
3220 >= 2592 ? yes
-> digit at position 4 is 2

This digit is also different from the previous one. We subtract 2592 from 3220 to get 628; then we move on to the values of the digit at position 3:

628 >= 1080 ? no
628 >=  864 ? no
628 >=  648 ? no
628 >=  432 ? yes
-> digit at position 3 is 2

This is the same as the previous digit, so we know the number has two identical adjacent digits in base 6.

---

The table can be built using only addition, and it's relatively small (up to 16×16 = 256 elements for checking 64-bit integers in base-16) and it can be re-used to check multiple numbers in the same base. Checking a number is done with only comparisons and subtractions; there's absolutely no modulo, division or even multiplication going on, so it should be very fast.

If the number contains identical adjacent digits, the algorithm can return an answer before checking all digits. If there are no identical adjacent digits, all digits are checked, which is effectively a full base conversion; but at least it's done efficiently.

Answer 2

This is the simplest solution I can imagine:

 private boolean check(long t, long base) {
    long x = -1;
    long y;
    while (t > 0) {
      y = t % base;
      if (y == x) {
        return false;
      }
      x = y;
      t = t / base;
    }
    return true;
  }

Answer 3

Recursive iteration generator over digits set resulting array and backtracking digit-by-digit will give natural ordering of numbers.

Generator is class with class members:

int length;
int curVal[10];
boolean digits[10];

Here curVal contains partially ready number.

Lower index corresponds to higher digit position, and pos is 0-based index counting from high to low position.

And digits is a set (or boolean array if you prefer) to keep track on digits used.

Generator driver function prototype looks like this :

void generate(int pos)

Inside you make simple loop from 0 to 9 and if digit is not in digits set, put it in, add to curVal[pos] and call generate(pos+1). After return remove cur digit from set and curVal.

Once you fill last digit, print/enqueue number to output stream/queue/list.

Instead or in addition to curVal you can keep track of binary representation. Precalculate 10^i and add precalc[length-pos-1]*digit to binary value each time you put digit into curVal and substract if you pull it back.

Also you need to process first digit separately, as highest digit can't be 0. Naturally it can be done inside in main loop over length with proper