Beust Sequence, aka Cedric's Challenge

Here's my brute-force solution in C to Cedric's Challenge.

It constructs each number by looping each digit from 0 to 9 in as many nested loops as the number of digits we wish to consider and confirming that the resulting number has distinct digits.

One quirk of how I did this is that it requires somewhat special casing to ignoring the leading zeros. Questions of looping efficiency aside, this approach is inefficient because we actually are interested in only about 17% of the numbers. (E.g. when the maximum is 1,000,000, the sequence is 168,570 numbers long.)

But it makes testing for unique digits fairly easy: starting from the first non-zero digit, test the remaining digits for uniqueness.

#include <stdio.h>
#include <stdlib.h>

int i[11];

int firstnonzeroindex()
{
  int k;
  for (k=0;k11;k++)
    if ( i[k] != 0 )
      return k;
  return k;
}

bool distinct(int start)
{
  int j,k;
  if ( start == 10 ) return true;
  for (j=start;j10;j++)
    for (k=j+1;k11;k++)
      if (i[j] == i[k]) return false;
  return true;
}

int main(int argc, char* argv[])
{
  if ( argc  2 ) return 1;
  int max = atoi(argv[1]);

  int val, prev, total, diff, maxdiff, k;

  prev = 0;
  total = 0;
  maxdiff = 0;

  if ( max  1 ) return 1;
  for (i[0] = 0; i[0]  10; i[0]++)
    for (i[1] = 0; i[1]  10; i[1]++)
      for (i[2] = 0; i[2]  10; i[2]++)
        for (i[3] = 0; i[3]  10; i[3]++)
          for (i[4] = 0; i[4]  10; i[4]++)
            for (i[5] = 0; i[5]  10; i[5]++)
              for (i[6] = 0; i[6]  10; i[6]++)
                for (i[7] = 0; i[7]  10; i[7]++)
                  for (i[8] = 0; i[8]  10; i[8]++)
                    for (i[9] = 0; i[9]  10; i[9]++)
                      for (i[10] = 0; i[10]  10; i[10]++)
                        {
                          k = firstnonzeroindex();
                          if ( k  11 && distinct(k) )
                            {
                              val = 0;
                              for (k=0;k11;k++)
                                val = 10*val + i[k];

                              diff = val - prev;
                              if ( maxdiff  diff )
                                maxdiff = diff;

                              if ( val >= max ) 
                                {
                                  printf( "Maximum diff = %d. Total = %d.\n", maxdiff, total );
                                  return 0;
                                }

                              total++;;

                              printf( "%d\n", val);
                              prev = val;
                            }
                        }
}
changed August 31, 2008