[seqfan] Re: Re Another Split & Multiply sequence from Eric A.

[Christian Sievers]

On Thu, Apr 06, 2023 at 11:05:48AM -0400, Zach DeStefano wrote:

>  For base 10, (in the window that I checked), we only see 121 of the
> 1023 unique ADCs produced. 34119 is the last number (at least up to 2^28)
> which produces a new ADC.

And that is all
(unless there is an error in my proof or computation).

We can define the function of reachable digits (rd) from some number
recursively as

  rd(n) = {n} for 0<=n<=9

(that value for 0 works best for the recursion (and seems plausible to
me), and is otherwise not important)

and for n>=10 as

  rd(n) = union over m in M of rd(m) where M is the set of values that we
                                  get from one step of split-and-multiply.

If n has k digits, then all nonzero elements in M have at least k-1
digits (and they are all smaller than n).

That means that all values of rd(n) with n having k digits
(and by induction, >k digits) is expressible as a union of values rd(m)
with m having k-1 digits (the value {0}=rd(0) also appears among them).
 
Now, by computation, the numbers with 7 digits give 30 different sets,
and all their possible unions have already been seen.

So no new set can appear after that.

Here is my Python3 code to check this:

----------------------------------------
digits = 7

def rd(n):
    res = 0
    snd = -1
    d = 10
    while d <= n:
        old_snd = snd
        snd = n % d
        if snd != old_snd:
            fst = n//d
            res |= rds[fst * snd]
        d *= 10
    return res

def closure(s):
    res = set()
    for x in s:
        res |= {x|y for y in res} | {x}
    return res
        

rds = [ 1<<n for n in range(10) ]
for n in range(10, 10**digits):
    rds.append(rd(n))


last_sets = set(rds[10**(digits-1) : 10**digits])
all_sets = set(rds)

print(len(last_sets))
print( closure(last_sets) <= all_sets )
----------------------------------------

Best
Christian