有没有办法找到在给定范围内具有 N 个质因数的卡迈克尔数？

Question

我正在努力解决问题。我需要找到一个卡迈克尔数，它是七个素数的乘积，每个素数都在 10^7 和 10^9 之间。有什么办法可以做到吗？

我尝试使用 Chernick 公式来解决此任务：

M(米) = (6m+1)(12m+1)(18m+1)(36m+1)(72m+1)(144m) +1)(288*米+1),

条件是所有因数均为素数且 m 能被 8 整除。

我还使用了 Korselt 准则：正复合整数 n 是卡迈克尔数当且仅当 n 是无平方的，并且对于 n 的所有素因数 p，确实 (n-1) 能被 (p- 1）。 这是代码：

from gmpy2 import is_prime
from math import prod

m = 1666672
while True:
    x = [i * m + 1 for i in [6, 12, 18, 36, 72, 144, 288]]
    n = prod(x)
    if all(is_prime(i) and (n - 1) % (i - 1) == 0 and i in range(10 ** 7, 10 ** 9 + 1) for i in x):
        print(m, n)
        break
    elif x[6] > 10 ** 9:
        print('Nothing found')
        break
    m += 8

最后，我得到m = 18726360和n = 112504155402956714375844566364658214310419726067438239203656961。

n 的质因数为：112358161、224716321、337074481、674148961、1348297921、2696595841、5393191681。

但是只有前四个在要求的范围[10^7, 10^9]内，所以我的解决方案没有通过:(

Answer 1

首先：您确定

10**7

到

10**9

是每个素因数的有效约束吗？

如果你“放松”

10**7

到

10**6

，并尝试下面的代码，你可能会找到

m

的解决方案，例如，

from gmpy2 import is_prime
from math import prod

m = 16
coeff = [6, 12, 18, 36, 72, 144, 288] 
x = [i * m + 1 for i in coeff]
while max(x) <= 10**9:
    n = prod(x)
    if all(is_prime(i) and (n-1)%(i-1)==0 and i >= 10**6 for i in x):
        print(m, n)
    m += 8
    x = [i * m + 1 for i in coeff]

您将看到打印的一对

(m,n)

，如下所示

780320 24541683183872873851606952966798288052977151461406721
950560 97690399855983225539913606829511143401760823106140161
1027840 168839374357880973161579357803582198122487343227453441