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

[Albert Chan]

(01-25-2020 11:50 PM)Albert Chan Wrote:  Here is what each "bit" contribute to the mod value, for P(999):

>>> for i in range(21): print i, pow(10,i,999)
...
0 1
1 10
2 100
3 1
4 10
5 100
6 1
7 10
8 100
...

We have the same "bit" contribution pattern for N = 333, 111
p(111) = (10^1*3-1)/9 = 111
p(333) = (10^3*3-1)/9 = 111111111
p(999) = (10^9*3-1)/9 = 111111111111111111111111111
We can pull this pattern out as special case, and reduce the combinatorial search.

I got an OK from Gerald for posting this fast p(n) Python code.
For my old Pentium 3, time for p(n = 0 to 9999) in 21 seconds (4 seconds for my laptop)

Code:

hd = [  0,   1,  10,  11, 100, 101, 110, 111,
     1000,1001,1010,1011,1100,1101,1110,1111]

def p(n, oddp=oddp, k=1):
    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 oddp(n) * k

oddp(n) search in chunks for 3 'hex digits' (12 decimal digits) at a time.
Since returned p is odd, we only need to check 16×16×8 = 2048 cases / 3 'hex digits'

Code:

def oddp(n, t=0, td=0, mod=0):  # assumed n%10 = 1,3,7,9
    h1 = [ -hd[i] % n for i in range(1,16,2)]
    h2 = [10000*x % n for x in hd]
    h3 = [10000*x % n for x in h2]
    bad = {}
    while 1:
        for m3 in h3:           # mods of 3rd 'hex digit'
            m4 = m3 + mod       # adjust for p(n) trillions
            for m2 in h2:       # mods of 2nd 'hex digit'
                if (m4+m2)%n not in h1: continue
                p = ( hd[h1.index((m4+m2)%n)*2+1]
                    + 10000*(hd[h2.index(m2)]
                    + 10000*(hd[h3.index(m3)])))
                if td: p += td
                return p        # note: p is odd
        bad[mod] = 1
        while 1:
            t += 1
            td = int(bin(t)[2:]) * 10**12
            mod = int(td % n)
            if mod not in bad: break

>>> p(12345)                 # = oddp(12345 // 5) * 10
11000111010L

>>> p(123456)               # = oddp(123456 >> 6) * 10**6
1110110100111000000L