Number Theory and d-Self-Contained Numbers

I don't know of any easy test, but here is a Python program which can find all self-contained numbers in a given range:

mem = dict() #global dictionary for memoization

def expressible(m,digits,k):
    if (m,digits,k) in mem:
        return mem[(m,digits,k)]
    elif m == 0 and k == 0:
        mem[(m,digits,k)] = True
        return True
    elif len(digits) == 0 or k > len(digits):
        mem[(m,digits,k)] = False
        return False
    else:
        for d in set(digits):
            i = int(d)
            remaining = digits.replace(d,'',1)
            if expressible(m + i,remaining, k-1) or expressible(m - i,remaining, k-1):
                mem[(m,digits,k)] = True
                return True
        #if we reach here:
        mem[(m,digits,k)] = False
        return False

def selfContained(a,b):
    nums = []
    for n in range(a,b+1):
        digits = ''.join(sorted(str(n)))
        contained = True #until a counter-example found
        for d in set(digits):
            i = int(d)
            remaining = digits.replace(d,'',1)
            if not expressible(i,remaining,2):
                contained = False
                break
            if not contained: break
        #if we reach here and contained is still true, no counterxamples, so:
        if contained: nums.append(n)
    mem.clear()
    return nums

For example,

>>> selfContained(1,360)
[101, 110, 112, 121, 123, 132, 134, 143, 145, 154, 156, 165, 167, 176, 178, 187, 189, 198, 202, 211, 213, 220, 224, 231, 235, 242, 246, 253, 257, 264, 268, 275, 279, 286, 297, 303, 312, 314, 321, 325, 330, 336, 341, 347, 352, 358]

this list agrees with the 3-digit numbers in the OEIS sequence linked to by @RobertSoupe .

The evaluation

nums = selfContained(0,1000000)

takes about 3 seconds and returns a list of 322378 numbers, the last 10 of which are

999909, 999918, 999927, 999936, 999945, 999954, 999963, 999972, 999981, 999990

On Edit: I tweaked the code a bit to make it run faster. It can now run out to 10,000,000 in less than a minute. Doing so turns up 4,768,482 self-contained numbers in that range. The percentage is increasing. It is easy to see that the asymptotic density of self-contained numbers is 1. In fact, the proof seems almost trivial: any number in which every digit occurs at least 2 times is self-contained, and the asymptotic density of such numbers is 1. Somewhat interestingly, this proof holds for any base (and not just base 10). Doubtless the rate at which the density approaches 1 depends on the base.

On Further Edit: Out to 100,000,000 (about 9 minutes for my program) there are 63,750,290 self-contained numbers. I'm not sure if it is feasible to go out to 1 billion with the program on my machine. It would be interesting to write an optimized C version and see how far out it can be taken.

Here's an easy answer to the last question: $10127$ is $3$-self-contained ($7 = 2^3 - 1^3$, $2^3 = 1^3+1^3$, $1^3 = 1^3+0^3$, $0=1^3-1^3$), but it's not $2$-self-contained because $7 > 1^2+0^2+1^2+2^2$. Similarly I believe $10129$ and $111129$ are in $A_3 \setminus A_2$. Thus $A_2 \not\supset A_3$, so the infinite descending chain proposition is false.

I suspect that, much like the OEIS sequence that Robert Soupe points to, the structure of $A_d$ for any fixed $d$ is quite simple and can described by a finite automaton. But I hesitate to make any guesses as to how the complexity grows with $d$.