python - Fastest way to filter the A010784 sequence -

the a010784 sequence @ oeis sequence containing numbers distinct digits. finite amount.

what i've been trying find several numbers in sequence attributes.
e.g: 6 distinct number of magnitude 10. can found follows:

• 6 x 1 = 6
• 6 x 2 = 12
• 6 x 3 = 18
• 6 x 4 = 24
• 6 x 5 = 30
• 6 x 6 = 36
• 6 x 7 = 42
• 6 x 8 = 48
• 6 x 9 = 54
• 6 x 10 = 60
• 6 x 11 = 66 (two sixes; these aren't both distinct digits.)

now i'm trying highest numbers available several magnitudes of order.
let's orders 1 20.

what i'm doing loop highest possible distinct number, 9,876,543,210 , highest unique number of magnitude 1, down low number.
method feels extremely inefficient. @ least, me does.

i'm pretty sure i'm missing stuff factoring should able make things lot faster.

def unique_num(num):     # check whether number unique.     return boolean  def unique_num_magnitude(num):     # check of magnitude unique number     return integer  # dictionary current highest values # each magnitude. values = {1: 987654321...}  # set limits upper_limit = 9876543210 lower_limit = 1  numbers in range(upper_limit, lower_limit, -1):     unique = unique_num(num) # boolean     if (unique):         magnitude = unique_num_magnitude(num)         if (values[magnitude] < num):             values[magnitude] = num 

sure there better way. should build numbers bottom up, i.e. if number a1...ak (these k digits) not of magnitude n digit appears twice within first k digits of result multiplicand 2..n neither number b1...bm a1...ak. provides categorically faster recursive enumeration procedure because cuts exponential amount of search space away. details left exercise op.

longer explanation:

assume there procedure

 magnitude(number_str) 

that calculates magnitude number number_str represented in 10-base, procedure returns 0 if number_str contains @ least 1 double occurrence of digit, 1 if number_str has every digit distinct multiplying number 2 results in digit occurring multiple times, etc.

this procedure can implemented in terms of one

 unique_digits(number_str) 

which returns true if digits in number_str unique, otherwise false.

now magnitude can implemented as

 magnitude(number_str):    n = str_to_int(number_str)    k = n    = 0    while (unique_digits(int_to_str(k))):      k = k + n      = + 1    return 

now magnitude procedure can changed nocarry_magnitude changes check subtly:

 nocarry_magnitude(number_str, limit):    l = length(number_str)    assert (l > 0)    n = str_to_int(number_str)    k = n    = 0    while (unique_digits(right_substring(int_to_str(k), l))):      k = k + n      = + 1      if (i == limit):        break    return 

this procedure checks multiple times occurring digits in many rightmost digits (lowest-order digits) of product in loop there digits in original input. limit parameter needed make sure procedure terminates it's possible procedure runs in infinite loop otherwise. string s holds that

 magnitude(s) <= nocarry_magnitude(s, m) large m 

for instance, take number 19:

 19 * 1 = 19  19 * 2 = 38  19 * 3 = 57  19 * 4 = 76  19 * 5 = 95  19 * 6 = 114 // magnitude("19") = 5  19 * 7 = 133 // nocarry_magnitude("19", 100) = 6 

what wrote above in short description if

 nocarry_magnitude(s, x) == k     x > k 

then string that's obtained postfixing s (denote x + s below), holds that

 x : string of digits  magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)  when m >= magnitude(x + s) 

the first inequality comes claim above , second 1 obvious definition of nocarry_magnitude. note magnitude(x + s) <= magnitude(s) non-theorem in general exemplified by

 magnitude( "56")  = 1  // 56 * 2 = 112  magnitude("256")  = 12 // first duplicate occurs @ 3328 

which caused carry. nocarry_magnitude ignores carry why suffix of string has large nocarry-magnitude extension of (towards left, i.e. higher-order digits).

now can write faster recursive procedure searching numbers magnitude @ least m:

 search(str):    if (str != ""):      int n = nocarry_magnitude(str, m)      if (n < m):        return      # optimization      int k = magnitude(str)      if (k >= m):        store_answer(str)    d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',              '10', '20', '30', '40', '50', '60', '70', '80', '90']:      search(d + str)   search("") 

here's full python implementation (searching magnitude 36):

def unique_digits(s):     r = (len(list(s)) == len(set(s)))     return r  def magnitude(s):     n = int(s)     k = n     assert n > 0     = 0     while (unique_digits(str(k))):         k = k + n         = + 1     return  def nocarry_magnitude(s, limit):     l = len(s)     assert l > 0     n = int(s)     assert n > 0     k = n     = 0     while (unique_digits(str(k)[-l:])):         k = k + n         = + 1         if (i >= limit):             break     return  m = 36  def search(s):     if (not(s == "")):         n = nocarry_magnitude(s, m)         if (n < m):             return         k = magnitude(s)         if (k >= m):             print "answer: %s |" % s,             = int(s)             k =             n = 1             while (n <= m):                 print k,                 k = k +                 n = n + 1             print     d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',               '10', '20', '30', '40', '50', '60', '70', '80', '90']:         search(d + s)  search("") 

and here's run takes less 1 second; finds answer '27' seems unique number provides record magnitude 36:

answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405              432 459 486 513 540 567 594 621 648 675 702 729 756 783              810 837 864 891 918 945 972