Every positive integer has infinitely many base-10 multiples that only use the digits 0 and 1. The goal of this task is to find and display the minimum multiple that has this property.

This is simple to do, but can be challenging to do efficiently.

To avoid repeating long, unwieldy phrases, the operation "minimum positive multiple of a positive integer n in base 10 that only uses the digits 0 and 1" will hereafter be referred to as "B10".

Task

Write a routine to find the B10 of a given integer.

E.G.

      n                  B10      n  × multiplier
      1                    1    ( 1  × 1         )
      2                   10    ( 2  × 5         )
      7                 1001    ( 7  x 143       )
      9            111111111    ( 9  x 12345679  )
     10                   10    ( 10 x 1         )

and so on.

Use the routine to find and display here, on this page, the B10 value for:

   1 through 10, 95 through 105, 297, 576, 594, 891, 909, 999

Optionally find B10 for:

   1998, 2079, 2251, 2277

Stretch goal; find B10 for:

   2439, 2997, 4878

There are many opportunities for optimizations, but avoid using magic numbers as much as possible. If you do use magic numbers, explain briefly why and what they do for your implementation.



See also

 OEIS:A004290 Least positive multiple of n that when written in base 10 uses only 0's and 1's.
 How to find Minimum Positive Multiple in base 10 using only 0 and 1
with javascript_semantics
function b10(integer n)
    if n=1 then return "1" end if
    integer NUM = n+1, count = 0, ten = 1, x
    sequence val = repeat(0,NUM),
             pow = repeat(0,NUM)
    --
    -- Calculate each 10^k mod n, along with all possible sums that can be
    -- made from it and the things we've seen before, until we get a 0, eg:
    --
    --  ten/val[]      (for n==7)        See pow[], for k
    --  10^0   = 1 mod 7 = 1.          Possible sums: 1
    --  10^1   = 10 mod 7 = 3.         Possible sums: 1 3 4
    --  10^2   = 10*3 = 30 mod 7 = 2.  Possible sums: 1 2 3 4 5 6
    --  10^3   = 10*2 = 20 mod 7 = 6.  STOP (6+1 = 7 mod 7 = 0)
    --
    -- ie since 10^3 mod 7 + 10^0 mod 7 == (6+1) mod 7 == 0, we know that
    -- 1001 mod 7 == 0, and we have found that w/o checking every interim
    -- value from 11 to 1000 (aside: use binary if counting that range).
    --
    -- Another example is 10^k mod 9 is 1 for all k. Hence we need to find
    -- 9 different ways to generate a 1, before we get a sum (mod 9) of 0,
    -- and hence b10(9) is 111111111, ie 10^8+10^7+..+10^0, and obviously
    -- 9 iterations is somewhat less than all interims 11..111111110.
    --
    for x=1 to n do
        val[x+1] = ten
        for j=1 to NUM do
            if pow[j] and pow[j]!=x then  -- (j seen, in a prior iteration)
                integer k = mod(j-1+ten,n)+1
                if not pow[k] then
                    pow[k] = x            -- (k was seen in this iteration)
                end if
            end if
        end for
        if not pow[ten+1] then pow[ten+1] = x end if
        ten = mod(10*ten,n)
        if pow[1] then exit end if
    end for
    if pow[1]=0 then crash("Can't do it!") end if
    --
    -- Fairly obviously (for b10(7)) we need the 10^3, then we will need 
    -- a sum of 1, which first appeared for 10^0, after which we are done. 
    -- The required answer is therefore 1001, ie 10^3 + 10^0.
    --
    string res = ""
    x = n
    while x do
        integer pm = pow[mod(x,n)+1]
        if count>pm then res &= repeat('0',count-pm) end if
        count = pm-1;
        res &= '1'
        x = mod(n+x-val[pm+1],n)
    end while
    res &= repeat('0',count)
    return res
end function
 
constant tests = tagset(10)&tagset(105,95)&{297, 576, 891, 909,
                 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878}
include mpfr.e
mpz m10 = mpz_init()
atom t0 = time()
for i=1 to length(tests) do
    integer ti = tests[i]
    string r10 = b10(ti)
    mpz_set_str(m10,r10,10)
    if mpz_fdiv_q_ui(m10,m10,ti)!=0 then r10 &= " ??" end if
    printf(1,"%4d * %-24s = %s\n",{ti,mpz_get_str(m10),r10})
end for
?elapsed(time()-t0)
