Python：找到一系列数字

Question

我需要解决任务，有一个条件：有一个由N开头的17个连续自然数的序列。对于该序列的任何数字a，来自该序列的另一个数字b，例如GCD (a, b)> 1。找到具有这种条件的最小N.

我用这个代码

for i in range(2, 100000000):
    not_division = 0
    lst = list(range(i, i+17))
    #print(lst)
    for j in lst:
        counter = 0
        for k in lst[1:]:
            if gcd_iterative(j, k) > 1 and gcd_iterative(j, k) != k:
                counter += 1

        if counter == 0:
            not_division += 1
            #print('%s have no delimiter' % j)
    if not_division == 0:
        print('%s SUCCESS' % str(lst))

但没有序列。也许我做错了。

Answer 1

我会试着用一种不那么暴力的方法解决这个问题。

有些想法先试验。其他每个数字都有2个共同点。对于剩余的8或9，您需要更多因素。因此，例如，你可以将其中一些因子共同使用。然后是另一个因素，例如：

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
* 3 * * 3 * * 3 * * 3 * * 3 * * 3
* * * 5 * * * * 5 * * * * 5 * * *
          ^       ^   ^       ^

所以现在以更系统的方式做到这一点。考虑所有小于17的素因子。尝试这些的每个组合，并为每个组合每个可能的偏移量（但只有序列中至少出现2次的那些）。看看哪个导致每个号码至少有一个伙伴的情况。然后使用Chinese remainder theorem找到相应的序列。

实际上只有2个候选人：

 2  *  2  *  2  *  2  *  2  *  2  *  2  *  2  *  2
 3  *  *  3  *  *  3  *  *  3  *  *  3  *  *  3  *
 *  5  *  *  *  *  5  *  *  *  *  5  *  *  *  *  5
 7  *  *  *  *  *  *  7  *  *  *  *  *  *  7  *  *
 *  *  *  *  * 11  *  *  *  *  *  *  *  *  *  * 11
13  *  *  *  *  *  *  *  *  *  *  *  * 13  *  *  *

其特征在于第一个数字x满足这些约束：

• x mod 2 = 0
• x mod 3 = 0
• x mod 5 = 4
• x mod 7 = 0
• x mod 11 = 6
• x mod 13 = 0
• Mod x vs. 30030 = 2184

（使用Sage函数crt计算）和上面的镜像

 2  *  2  *  2  *  2  *  2  *  2  *  2  *  2  *  2
 *  3  *  *  3  *  *  3  *  *  3  *  *  3  *  *  3
 5  *  *  *  *  5  *  *  *  *  5  *  *  *  *  5  *
 *  *  7  *  *  *  *  *  *  7  *  *  *  *  *  *  7
11  *  *  *  *  *  *  *  *  *  * 11  *  *  *  *  *
 *  *  * 13  *  *  *  *  *  *  *  *  *  *  *  * 13

特点是

• y朝向2 = 0
• y朝向3 = 1
• y朝向5 = 0
• y朝7 = 5
• y朝向11 = 0
• y朝13 = 10
• Mod y mod 30030 = 7810

这是更大的，所以2184 ... 2200是满足您要求的第一个序列：

• 2184 = 23 × 3 × 7 × 13
• 2185 = 5 × 19 × 23
• 2186 = 2 × 1093
• 2187 = 37
• 2188 = 22 × 547
• 2189 = 11 × 199
• 2190 = 2 × 3 × 5 × 73
• 2191 = 7 × 313
• 2192 = 24 × 137
• 2193 = 3 × 17 × 43
• 2194 = 2 × 1097
• 2195 = 5 × 439
• 2196 = 22 × 32 × 61
• 2197 = 133
• 2198 = 2 × 7 × 157
• 2199 = 3 × 733
• 2200 = 23 × 52 × 11

哪个应该在你的循环范围内。实际上它应该足够循环到30030，素数的乘积高达17。所以如果你的循环真的完成了，但错过了这个序列，那么某处肯定会有一个错误，并且知道序列可能会帮助你调试那个。