在Mathematica中查找大质数

Question

我对Mathematica很陌生，我试图找到只能使用数字0,1,2和3写入的大素数，而且这些数字中的一半以上必须是0 。例如100003就符合要求。

我正在考虑如果使用Prime [n]函数，如果“If”语句，但我想知道是否有更有效的方法来解决这个问题。提前致谢。

Answer 1

对于一个很好的答案问在http://mathematica.stackexchange.com

这个问题对于各种各样的答案，阅读...

功能

myTestQ[num_Integer] := 
    And[DigitCount[num][[10]] > Plus @@ DigitCount[num][[1 ;; 3]], PrimeQ[num]] 

回报True当它传递了一个整数（ i）具有比1s，2s和3s更多的0数字，并且（ii）是质数。 And按次序评估其参数和短路，因此应避免测试数字计数不正确的数字的素数。

在实践中，您的计算时间将由素性测试支配;生成并丢弃大量具有错误数字计数的整数是足够便宜的，您可以忽略程序中该部分的低效率。

现在测试一个由只有0,1,2,3数字组成的整数范围。只有这些数字的整数都是整数，即以4为底的所有整数。所以，让我们产生那些：

IntegerString[Range[lo, hi, 2], 4] 

这将产生代表全部来自lo个基的4个整数，以2步hi个（你不会有兴趣在任何偶数串）。例如

IntegerString[Range[1, 13, 2], 4] 

产生

{"1", "3", "11", "13", "21", "23", "31"} 

即，第一，第三，第五，...，第13基-4-字符串形式的数字。当然，你需要将它们作为整数来测试它们，我们将使用ToExpression。

醪它一起和你喜欢的东西

Select[ToExpression[IntegerString[Range[lo, hi, 2], 4]], myTestQ] 

，不管你喜欢更换lo和hi，但要确保lo是奇数。

Answer 2

你可以去钓鱼。首先生成所需模式的大整数，然后测试它们的素数。我没有数学，但这里是Python中的快速和肮脏的实施：

import random 

def rand_candidate(n): 
    #assumes n > 4 
    while True: 
     s = [random.choice(['1','2','3'])] 
     for i in range(n-2): 
      s.append(random.choice(['0','0','0','1','2','3'])) 
     s.append(random.choice(['1','3'])) 
     if s.count('0') > n/2: return int(''.join(s)) 

以前的功能选择非零领先的数字开头，则选取方式，也就是偏向于中间位0，然后选取最后一位使其成为奇数，检查整体结果是否具有必需的零个数。

对于素数测试，我很懒，只是用了一个费马测试。对于RSA的PGP实现，使用了以下测试（并且可能仍被使用）。它将合成数字证明为主要的概率非常低。在数学，你当然会诉诸于更复杂的测试：

def prob_prime(n): 
    tests = [2,3,5,7] 
    return all(n % p != 0 and pow(p,n-1,n) == 1 for p in tests) 

把它们放在一起：

def go_fishing(n): 
    while True: 
     p = rand_candidate(n) 
     if prob_prime(p): return p 

典型输出：

>>> go_fishing(20) 
23002001032200000101 
>>> go_fishing(100) 
1100200103020002000000000020232222230321210000103030031022000000200001001300020010012122020101020113 

计算机代数系统导出（这是我做的在我的机器上）证明上述两者都是主要的。