过滤A010784序列的最快方法

OEIS的A010784序列是仅包含具有不同数字的数字的序列。这是一个有限的数量。

我一直在尝试做的是在这个序列中找到几个具有特定属性的数字。
例如:6是10级的不同数字。

6 × 1 = 6
6 × 3 = 18
6 × 4 = 24
6 × 5 = 30
6 × 6 = 36
6 × 7 = 42
6 × 8 = 48
6 × 9 = 54
6 × 10 = 60
6 × 11 = 66(两个6;这不是两个不同的数字。)

现在我正在尝试几个数量级的最高可用数。
假设所有从1到20的订单。

我现在所做的是从最大可能的不同数，即9,876,543,210和最大的唯一数1，循环到一个非常小的数字。
这种方法感觉非常低效。至少对我来说是这样。

我很确定我错过了一些关于分解的东西，这些东西应该能让事情变得更快。

def unique_num(num):
    # Check whether number is unique.
    return Boolean
def unique_num_magnitude(num):
    # Check of which magnitude the unique number is
    return Integer
# Dictionary with the current highest values
# for each magnitude.
values = {1: 987654321...}
# Set limits
upper_limit = 9876543210
lower_limit = 1
for 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

肯定有更好的办法。你应该从下往上构建数字，例如，如果一个数字a1…ak(这是k位数字)的大小不是N，因此对于任何乘数2，一个数字在结果的前k位中出现两次。N也不是任何数字b1。bm a1…正义与发展党。这提供了一个更快的递归枚举过程，因为它减少了指数级的搜索空间。细节留给OP.

再解释:

假设存在一个过程

 magnitude(number_str)

计算以10为基数表示的数字number_str的大小，如果number_str包含至少一个双位数出现，则返回0，如果number_str的每个数字都不相同，但将该数字乘以2，则返回1，等等。

这个过程可以用另一个

来实现

 unique_digits(number_str)

如果number_str中的所有数字都是唯一的，则返回true，否则返回false。

现在magnitude可以实现为

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

现在可以将magnitude过程更改为nocarry_magnitude，从而巧妙地更改检查:

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

此过程检查循环中乘积的最右边数字(最低阶数字)中多次出现的数字，其数量与原始输入中的数字数量相同。需要一个limit参数来确保过程终止，否则过程可能会在无限循环中运行。显然，对于任意字符串s，

 magnitude(s) <= nocarry_magnitude(s, M) for large M

例如，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

我在上面的简短描述中所写的是，如果

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

则对于任何通过后置s获得的字符串(用下面的x + s表示)，它保持

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

第一个不等式来自上面的断言，第二个不等式从nocarry_magnitude的定义中很明显。请注意，magnitude(x + s) <= magnitude(s)一般来说是非定理，如

所示

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

是由进位引起的。nocarry_magnitude忽略进位，这就是为什么字符串的后缀总是和它的任何扩展一样大(向左，即高阶数字)。

现在你可以编写一个明显更快的递归过程，如下所示用于搜索大小至少为M的数:

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

这是一个完整的Python实现(搜索数量级为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
    i = 0
    while (unique_digits(str(k))):
        k = k + n
        i = i + 1
    return i
def nocarry_magnitude(s, limit):
    l = len(s)
    assert l > 0
    n = int(s)
    assert n > 0
    k = n
    i = 0
    while (unique_digits(str(k)[-l:])):
        k = k + n
        i = i + 1
        if (i >= limit):
            break
    return i
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,
            i = int(s)
            k = i
            n = 1
            while (n <= M):
                print k,
                k = k + i
                n = n + 1
            print
    for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
              '10', '20', '30', '40', '50', '60', '70', '80', '90']:
        search(d + s)
search("")

这是一个不到一秒的运行;这找到了答案'27'，它似乎是提供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

这不是一个排列问题吗?对于给定的星等M，你做10cM。

例如，2的数量级，从0到9中选择2个数字有多少种方法?(实际上，应该是1中的1…从0到9再加1…9，其中第二位数字与第一位数字不匹配)

你当然不需要把它们都检查一遍。只需要设置一个集合并选择一个，然后再选择另一个。更好的是，从头开始创建它们。首先做所有以1开头的(10,12,13,14等)然后做所有以2开头的，以此类推

你有两个问题:

1)迭代A010784序列。

出现使用itertools。排列生成连续的可能数。

2)计算一个数的大小。

你可以用这段代码来确定一个数字是否只有唯一的数字:

def unique_num(x):
    return len(str(x)) == len(set(str(x))

如果你只是在寻找最高的数字，你可以剪掉一些分支。从6 x 11 = 66你也知道11的震级最多是5级。一旦你知道了一个大于等于5的数字，你就可以跳过11了

相关内容

最新更新

热门标签：