Comments from Sasha Semenov posted to rec.math:
December 2006

It looks like there is no elegant solution of this problem,
so we use a brute force approach.

Lets scatter the entire set of positive integers into 2^10=1024 subsets,
depending on what decimal digits its decimal representation contains.

Say the number 1121122909090 contains digits {0129}, and therefore
belongs to a subset indexed by binary number 1000000111.
The most significant bit set to 1 because 9 is here, and the least
significant digits are set to 111 because digits 2,1,0 are also in this number.

Each number belongs to exactly one subset, they do not intersect.

If n belongs to subset indexed by index1, then A(n) belongs to
one of complementary subsets index2, which can "mate" with
original subset. Two subsets can mate if their indexi have no common
ones, that is index1 (bit_wise_AND) index2 = 0

Note that if  n1  and  n2  belong to the same subset and
n1<n2,. then A(n1) < A(n2). As a consequence, taking
into account that  A(A(n)) =  n, one can conclude that
the inverse statement is also always true:

if  A(n1) and A(n2) both belong to the same subset,
then        A(n1)<A(n2)     =>     n1<n2.

Therefore the members of each subset enter into A(n)
consequentially, and without gaps. This is unlike the entire set
positive integers, which contains pockets of unused numbers
between those already used in the sequence A(n).

Which means that instead of remembering which numbers
are already in the sequence, we can fully describe
the state of sequence construction by only 1024 numbers -
one "next available" member from each of 1024 subsets.

A simple C++ program posted below produces the following
result in about 5 minutes @ 1GHz CPU.

Sequence member A(123456788):
Length: 16, number: 9099900999090090

Sequence member A(123456780):
Length: 5929, number: 99999999999999999999999999999999...

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


struct StrNumber
{
    char *repr_str;
    long  repr_len, buff_len;


};


void initSubSets();
void increment(StrNumber* n);
void findNextInSubset(short index);
void addMSDigit(StrNumber* n);
void printStrNumber(StrNumber* n);
void makeZeroStrNumber(StrNumber* n);
short getSubsetIndex(StrNumber* n);
bool firstGreaterThanSecond(StrNumber* n1, StrNumber* n2);


StrNumber subset_top[0x400]; // tops of each subset
short       *trellis[0x400]; // liast of indexes of subsets that mate
short    trellis_len[0x400]; // list length


int main(int narg, char **argv)
{


    StrNumber N, Target;
    short i;


    // set Tareget to specified aregument
    if (narg != 2)
    {
        printf("Useage:\nnsd number\nwill print A(number)\n");
        return -1;
    }
    Target.buff_len = Target.repr_len = strlen(argv[1]);
    Target.repr_str = (char *)malloc(Target.buff_len);
    for (i = 0; i<Target.repr_len; i++)
        Target.repr_str[Target.repr_len-i-1] = argv[1][i] - '0';
    printStrNumber(&Target);


    // set sequence pointer to 0
    makeZeroStrNumber(&N);


    initSubSets();
    short index, index_N, min_A_index;
    unsigned long progress_cntr = 0;
    do
    {
        increment(&N);
        index_N = getSubsetIndex(&N);
        if (index_N == 0x3FF) // if the number has all 10 digits equal
double
nothing
        {
            min_A_index = 0x3FF;
            break;
        }
        min_A_index = 0;


        // find smallest of possible candidates:
        for(i = 1; i<trellis_len[index_N]; i++)
        {
            if(firstGreaterThanSecond(
                subset_top+min_A_index,
subset_top+trellis[index_N][i]))
                    min_A_index = trellis[index_N][i];
        }
        if (!firstGreaterThanSecond(&Target, &N)) // That's our number!
            break;


        if (!(progress_cntr++ & 0xFFFFF)) //report progress
        {
            printf("\nCurrent n:\n");
            printStrNumber(&N);
            printf("Current A(n):\n");
            printStrNumber(subset_top+min_A_index);
        }


        findNextInSubset(min_A_index);
    }
    while(true);


    printf("\n\n***********\nFinal sequence index n:\n");
    printStrNumber(&N);
    printf("Sequence member A(n):\n");
    printStrNumber(subset_top+min_A_index);


}


void initSubSets()
{
    short i, j, k;


    // Take separate care of subsets {} {0} and {0123456789}
    makeZeroStrNumber(subset_top+0);
    subset_top[0].repr_len = 0x7FFFFFFFL;
    makeZeroStrNumber(subset_top+1);
    subset_top[1].repr_len = 0x7FFFFFFEL;
    makeZeroStrNumber(subset_top+0x3FF);


    for (i = 2; i<0x3FF; i++)
    {
        printf ("\nInitializing subset 0x%x\n", i);
        trellis_len[i] = 0x400;
        for (j=0; j<10; j++)
            if ((0x1 << j) & i)
                trellis_len[i] >>=1;


        trellis[i] = (short *) malloc(trellis_len[i]*sizeof(short));
        for (j= k= 0; j<0x400; j++)
            if (!(j & i))
                trellis[i][k++] =j; // pointer to mating subset


        makeZeroStrNumber(subset_top+i);
        findNextInSubset(i);
        printf ("Trellis length: %x\n", trellis_len[i]);
        printStrNumber(subset_top+i);
    }


}


void increment(StrNumber* n)
{
    bool carryover;
    long dec_pos = 0;
    char digit;


    do
    {
        carryover = 0;
        digit = n->repr_str[dec_pos];
        if(++digit == 10)
            { digit = 0; carryover = true; }
        n->repr_str[dec_pos] = digit;
        if (carryover)
            if (++dec_pos == n->repr_len)
                addMSDigit(n);
    }
    while (carryover); // try next more significant digit


}


void findNextInSubset(short index)
{
    bool carryover;
    long dec_pos = 0;
    char digit;


    if (index == 0x0) return; // empty subset
    if (index == 0x1) return; // zeros only


    do
    {
    do
    {
        carryover = 0;
        digit = subset_top[index].repr_str[dec_pos];
        do
        {
            if(++digit == 10)
            { digit = 0; carryover = true; }
        }
        while (!(index & (0x1 << digit)));
        subset_top[index].repr_str[dec_pos] = digit;
        if (carryover)
        if (++dec_pos == subset_top[index].repr_len)
            addMSDigit(subset_top+index);
    }
    while (carryover); // try next more significant digit
    dec_pos = 0;
    }
    while (getSubsetIndex(subset_top+index) != index);


}


bool firstGreaterThanSecond(StrNumber* n1, StrNumber* n2)
{
    if (n1->repr_len != n2->repr_len)
        return n1->repr_len > n2->repr_len;


    long len = n1->repr_len;
    long i;
    for (i=len-1; i>=0; i--)
        if (n1->repr_str[i] != n2->repr_str[i])
            return n1->repr_str[i] > n2->repr_str[i];
    return false; // they are equal; should never happen


}


void addMSDigit(StrNumber* n)
{
    n->repr_len++;
    if (n->repr_len > n->buff_len)
    {
        long new_bufflen = 2* n->buff_len;
        char *new_buffer = (char *)malloc(new_bufflen);
        for (long i = 0; i<n->buff_len; i++)
            new_buffer[i] = n->repr_str[i];
        free(n->repr_str);
        n->repr_str = new_buffer;
        n->buff_len = new_bufflen;
    }
    n->repr_str[n->repr_len-1] = 0;


}


short getSubsetIndex(StrNumber* n)
{
    short result = 0;
    for (long i = 0;  i<n->repr_len;  i++)
        result |= 0x1 << n->repr_str[i];
    return result;


}


void makeZeroStrNumber(StrNumber* n)
{
    n->buff_len = 0x10;
    n->repr_str = (char *)malloc(n->buff_len);
    n->repr_len = 1;
    n->repr_str[0] = 0;


}


void printStrNumber(StrNumber* n)
{
    long print_len;
    bool truncated = n->repr_len > 0x20;
    if (truncated)
        print_len = 0x20;
    else
        print_len = n->repr_len;


    printf("Length: %d, number: ", n->repr_len);
    for (long i = 0; i < print_len; i++)
        printf("%d", n->repr_str[n->repr_len -i -1]);
    if (truncated)
        printf("...\n");
    else
        printf("\n");