HP 49G: Minimum Multiplier M of Integer N such that M*N Consists Only of 1's & 0's

[Albert Chan]

(01-27-2020 04:11 PM)Albert Chan Wrote:  For my old Pentium 3, time for p(n = 0 to 9999) in 21 seconds (4 seconds for my laptop)

To take advantage of Python's O(1) dictionary lookup, here is p(n) dict() based version.
Timings for p(n = 0 to 9999) reduced to Pentium3 = 8.1 s., Laptop = 1.5 s. (≈ 2.5X speed)

Code:

hd = [0,1,10,11,100,101,110,111]
hd = hd + [1000+x for x in hd]
hd = hd + [10000+x for x in hd]
hd = hd + [100000+x for x in hd]

def bdec(x):
    if x<64: return hd[x]
    return hd[x&63] + bdec(x>>6) * 1000000

def oddp(n, t=0, td=0, mod=0):
    m = n >> 1                  # assumed n is odd
    while m % 5: m += n         # loop upto 4 times
    m = m//5                    # = -1/10 (mod n)
    h1 = dict(((m-x)%n, x) for x in reversed(hd))
    m = 1000000%n
    h2 = [m*x%n for x in hd]
    bad = {}
    while 1:                    # assumed n%10 = 1,3,7,9
        for m2 in h2:
            if (m2+mod)%n not in h1: continue
            m = h1[(m2+mod)%n] + 1000000*hd[h2.index(m2)]
            if td: m += td
            return 10*m+1
        bad[mod] = 1
        while 1:
            t += 1
            td = bdec(t) * 10**12
            mod = int(td % n)
            if mod not in bad: break

def p(n, oddp=oddp, k=1):       # 2nd arg can use minmulzo
    if n<2: return n
    while n%5==0: k *= 10; n //= 10-5*(n&1)
    while n&1==0: k *= 10; n >>= 1
    x = str(n)                  # n%10 = 1,3,7,9
    if x[0] in '139' and x.count(x[0]) == len(x):
        return 10**((ord(x[0])-48)*len(x)) // 9 * k
    return k * oddp(n)

Update: new algorithm, odd p = 10m+1, solve for m ≡ -1/10 (mod n), return 10m+1
Timings for p(n = 0 to 9999) improved to Pentium3 = 4.8 s., Laptop = 0.9 s.