9 digits

/* Compile with:
 * gcc -o lofasz -lgmp -O3 lofasz.c
 *
 * Run with:
 * time ./lofasz 40
 */

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

#define MAX_BASE 50

struct number_s {
    mpz_t number;
    char used[MAX_BASE];
    struct number_s *next;
};
typedef struct number_s number_t;


inline number_t* new_number () {
    number_t *n = (number_t *) calloc(1, sizeof(number_t));
    if (n) {
        mpz_init(n->number);
    }

    return n;
}

inline void copy_used (number_t *to, number_t *from) {
    if (from && to) {
        memcpy(to->used, from->used, MAX_BASE);
    }
}

inline void destroy_number (number_t *n) {
    if (n) {
        mpz_clear(n->number);
        free(n);
    }
    n = NULL;
}

int main(int argc, char* argv[]) {
    unsigned long int max_base, base, last, middle, cnt, o, d, l;
    number_t *head, *head2, *cur, *cur2;
    mpz_t new_num, new_num_base;
    unsigned char eligible_digits[MAX_BASE * MAX_BASE];

    mpz_init(new_num);
    mpz_init(new_num_base);

    printf("#base\ttries\tresults\n");

    if (argc > 1) {
        int errno = 0;
        max_base = (unsigned long int) strtol(argv[1], NULL, 10);
        if (errno != 0) {
            max_base = 36;
        }
        if (max_base > MAX_BASE - 1) {
            max_base = MAX_BASE - 1;
        }
    }
    else {
        max_base = 36;
    }

    for (base = 2; base <= max_base; base +=2) {
        cnt = 0;
        last = base - 1;
        middle = base / 2;

        /* pre-compute table of eligible digits for this base */
        for (l = 1; l <= middle; l++) {
            if (base % l == 0) {
                for (o = 1; o <= last; o++) {
                    for (d = 1; d <= last; d++) {
                        if (d % l == 0 || o % l == 0) {
                            eligible_digits[o*MAX_BASE + d] = (d % l == 0 && o % l == 0) ? 1 : 0;
                        }
                    }
                }
            }
        }

        /* initial list with the digits */
        head = head2 = NULL;
        for (d = last; d >= 1; d--) {
            if (eligible_digits[1*MAX_BASE + d]) {
                cur = new_number();
                mpz_set_ui (cur->number, d);
                cur->used[d] = 1;
                cur->next = head;
                head = cur;
            }
        }

        for (o = 2; o <= last; o++) {
            cur = head;
            head2 = cur2 = NULL;
            while (cur) {
                mpz_mul_ui(new_num_base, cur->number, base);
                for (d = 1; d <= last; d++) {
                    if (!cur->used[d] && (eligible_digits[o*MAX_BASE + d])) {
                        cnt++;
                        mpz_add_ui(new_num, new_num_base, d);

                        #ifdef DEBUG
                        printf("%ld (%ld) ", cnt, o);
                        mpz_out_str(stdout, base, cur->number);
                        printf(" + %ld = ", d);
                        mpz_out_str(stdout, base, new_num);
                        printf(" [");
                        for (l = 0; l <= last; l++) {
                            printf("%c", cur->used[l] ? '*' : ' ');
                        }
                        printf("] ");
                        #endif
                        if (mpz_divisible_ui_p(new_num, o)) {
                            #ifdef DEBUG
                            printf("+");
                            #endif
                            number_t *temp = new_number();
                            mpz_set(temp->number, new_num);
                            copy_used(temp, cur);
                            temp->used[d] = 1;
                            if (head2) {
                                cur2->next  = temp;
                                cur2        = temp;
                            }
                            else {
                                head2 = cur2 = temp;
                            }
                        }
                        #ifdef DEBUG
                        printf("\n");
                        #endif
                    }
                }
                cur = cur->next;
            }

            while (head) {
                number_t *next = head->next;
                destroy_number(head);
                head = next;
            }
            head = head2;
        }

        printf("%ld\t%ld\t", base, cnt);
        cur = head;
        while (cur) {
            mpz_out_str(stdout, base, cur->number);
            printf(" ");
            cur = cur->next;
        }
        printf("\n");
        while (head) {
            number_t *next = head->next;
            destroy_number(head);
            head = next;
        }
        memset(eligible_digits, 0, MAX_BASE*MAX_BASE);
    }
    mpz_clear(new_num);
    mpz_clear(new_num_base);
    return 0;
}