0

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

我一直在尝试做的是在这个序列中找到几个具有某些属性的数字。
例如：6 是 10 等的不同数字。这可以找到如下：

  • 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（两个六；这些不是两个不同的数字。）

现在我正在尝试几个数量级的最高数字。
假设所有订单从 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
4

4 回答 4

1

这不只是一个排列问题吗？对于给定的量级M，你做 10cM。

例如，幅度为 2，有多少种方法可以从 0..9 中选择 2 个数字？（实际上，它应该是 1..9 中的一个和 0..9 中的一个，其中第二个数字与第一个不匹配。）

你当然不需要遍历它们并检查它们。只需设置一组并选择一个，然后再选择另一个。更好的是，只需从头开始创建它们。首先执行以 1 开头的所有内容（10、12、13、14 等），然后执行以 2 开头的所有内容等。

于 2011-04-30T00:59:16.667 回答
1

你有两个问题：

1) 遍历 A010784 序列。

使用 itertools.permutations 生成连续的可能数字。

2) 计算一个数的大小。

您可以使用以下代码片段确定一个数字是否只有唯一数字：

def unique_num(x):
    return len(str(x)) == len(set(str(x))
于 2011-04-30T01:02:03.373 回答
1

当然有更好的方法。您应该自下而上构建数字，即如果数字 a1...ak（这些是 k 位）的大小不是 N，那么对于任何被乘数 2..N，一个数字在结果的前 k 位内出现两次也不是任何数字 b1...bm a1...ak。这提供了一个绝对更快的递归枚举过程，因为它减少了指数数量的搜索空间。细节留给 OP 练习。

更长的解释：

假设有一个过程

 magnitude(number_str)

计算以 10 为基数表示的数字的大小，因此如果包含至少两次出现的数字，则number_str该过程返回 0 ，如果每个数字都不同，但将数字乘以 2 会导致一个数字出现多次，则返回 1，等等number_strnumber_str

这个过程可以在另一个方面实现

 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为巧妙地更改检查的 a：

 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

此过程仅在与原始输入中的数字一样多的循环中产品的最右边数字（最低位数字）中检查多次出现的数字。需要一个限制参数来确保过程终止，否则该过程可能会在无限循环中运行。显然对于任何字符串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。请注意，幅度（x + s）<=幅度（s）通常是非定理，例如

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

这是由进位引起的。nocarry_magnitude忽略进位，这就是为什么字符串的后缀总是与它的任何扩展一样大的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
于 2011-04-30T04:13:56.097 回答
0

如果你只是在寻找最高的数字，你可以剪掉一些树枝。您6 x 11 = 66还知道 11 的大小最多为 5。一旦您知道大小 >= 5 的更高数字，您就可以跳过 11。

于 2011-04-30T01:28:04.720 回答