代码之家 › 专栏 › 技术社区 › Petr Petrov

python:找到一个数字序列

math python

Petr Petrov · 技术社区 · 7 年前

我需要解决任务,有一个条件: 有一个由17个连续自然数组成的序列,从 N .对于任何号码 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))

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

1 回复 | 直到 7 年前

MvG 7 年前

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

先做一些思想实验。其他每个数字都有相同的因子2。对于剩下的8或9,您需要更多的因素。例如,你可以有一个系数3,对其中一些人来说很常见。然后是另一个因素,等等,例如:

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
 3  *  *  3  *  *  3  *  *  3  *  *  3  *  *  3  *
 *  5  *  *  *  *  5  *  *  *  *  5  *  *  *  *  5
 7  *  *  *  *  *  *  7  *  *  *  *  *  *  7  *  *
 *  *  *  *  * 11  *  *  *  *  *  *  *  *  *  * 11
13  *  *  *  *  *  *  *  *  *  *  *  * 13  *  *  *

以第一个数字为特征 X 满足这些限制:

X 模式2=0
X 模式3=0
X 模式5=4
X 模式7=0
X 模式11=6
X 模式13=0
_ X 型号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

特点是

是模式2=0
是模式3=1
是模式5=0
是模式7=5
是模式11=0
是型号13=10
_ 是型号30030=7810

哪个更大,所以2184_2200是第一个满足您要求的序列:

2184=2个 ^三 3713个
2185=5___ 19___ 23
2186=21093
2187=3个 ⁷
2188=2 ^二 ___
2189=11199
2190=2___ 3___ 5___ 73
2191=7313
2192=2 ⁴ _ _ 137
2193=31743
2194=2_ _ 1097
2195=5439
2196=2个 ^二 ___ ^二 _ _ 61
2197=13岁 ^三
2198=27157
2199=3____
2200=2个 ^三 5个 ^二 11个

哪个应该在你的循环范围内。实际上,它应该足以循环到30030次,而素数的乘积则可以达到17次。所以,如果循环确实完成了,但是错过了这个序列,那么一定有错误,知道这个序列可能有助于调试它。