0

OEIS の A010784 シーケンスは、数字が異なる数字のみを含むシーケンスです。これは有限の量です。

私がやろうとしてきたのは、このシーケンスで特定の属性を持ついくつかの数字を見つけることです。
例: 6 はマグニチュード 10 の個別の数です。これは次のように見つけることができます。

  • 6×1＝6
  • 6×2＝12
  • 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 x 11 = 66 (2 つの 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
4

4 に答える 4

1

確かにもっと良い方法があります。数値を下から上に構築する必要があります。つまり、数値 a1...ak (これらは k 桁) の大きさが N でない場合、任意の被乗数 2..N の結果の最初の k 桁内に 1 つの桁が 2 回出現する場合、どちらも b1...bm a1...ak の任意の数ではありません。これにより、指数関数的な量の検索スペースが削減されるため、再帰的列挙手順が断然高速になります。詳細は演習として OP に残しました。

より長い説明:

手続きがあるとします

 magnitude(number_str)

これは、10 進法で表された数値の大きさを計算するnumber_strため、プロシージャーはnumber_str、数字の二重出現が少なくとも 1 つ含まれる場合は 0 を返し、number_strすべての数字が異なる場合は 1 を返しますが、数字を 2 倍すると数字が複数回出現する結果になります。等

この手順は、別の手順で実装できます

 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

このプロシージャは、元の入力にあった数字と同じ数のループ内の積の右端の数字 (最下位の数字) でのみ、複数回出現する数字をチェックします。プロシージャが無限ループで実行される可能性があるため、プロシージャが終了することを確認するには、制限パラメーターが必要です。明らかに、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)

最初の不等式は上記の主張に由来し、2 番目の不等式は の定義から明らかです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("")

そして、これは 1 秒もかからない実行です。これは、記録的なマグニチュード 36 を提供する一意の数であると思われる答え '27' を見つけます。

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 に答える
1

これは単なる順列の問題ではないでしょうか。与えられたマグニチュードに対して、M10cM を行いますか。

たとえば、マグニチュード 2 の場合、0..9 から 2 桁を選択する方法はいくつありますか? (実際には、2 桁目が 1 桁目と一致しない 1..9 と 0..9 のいずれかである必要があります。)

もちろん、それらすべてを実行して確認する必要はありません。セットをセットアップして 1 つを選択し、次に別のセットを選択するだけです。いっそのこと、ゼロから作成するだけです。最初に 1 で始まるすべて (10、12、13、14 など) を実行し、次に 2 で始まるすべてを実行します。

于 2011-04-30T00:59:16.667 に答える
1

2 つの問題があります。

1) A010784 シーケンスを繰り返します。

itertools.permutations を使用して、連続する可能な数を生成します。

2) 数値の大きさの計算。

次のコード スニペットを使用して、数値に一意の数字のみが含まれているかどうかを判断できます。

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