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

[Albert Chan]

(01-29-2020 07:25 AM)Gerald H Wrote:  A non-brute force algorithm would be very useful.

Sage code is non-brute force.
It generated a list of mod restricted possibilities. Time complexity = O(N log(P))

Example, for p(7), it produced a list, pfrem = [3, 0, 2, 1, 1, 2, 2].
This list, in modulo 7, meant this:
  
1??? ≡ 0
1    ≡ 1
1??  ≡ 2
1?   ≡ 3
1?   ≡ 4
1??  ≡ 5
1??  ≡ 6

? is either 0 or 1, not yet determined. We can solve for P:

P = 1??? ≡ 0 (mod 7)
??? ≡ -1000 ≡ 1 (mod 7)

From the list, 1 ≡ 1 → ??? = 001 → P(7) = 1001

The problem is above required N item list, which may be huge, and takes time to build.
The code shines if N is small, but P is big. Example:

>>> minmulzo(142857)        
1010001010001110001110101110101110111111111L

Above finished on my Pentium3 in 3.6 seconds.
Brute force, oddp(142857) would take about 10 hours.

Code:

def minmulzo(n, b=10) :
    if n<2 : return n
    pfrem = [n] * n
    pfrem[1] = 0                # p%n=1 -> p = 1
    m, i = 1, b%n
    while pfrem[0] == n:        # p%n=0 -> p < 10**n
        for r in xrange(1,n) :
            if pfrem[r] >= m: continue
            if pfrem[r+i-n] == n: pfrem[r+i-n] = m
        if pfrem[i] == n: pfrem[i] = m
        i = b*i % n
        m = m + 1
    res = r = 0
    while 1:
        m = b**pfrem[r]
        r = (r-m) % n
        res += m
        if not r: return res