素数和孪生素数间隔的结构
4.82/5 (17投票s)
探索素数底层的结构
引言
素数之间的间隔似乎是随机的，这一直让我感到奇怪。在思考这个问题时，我意识到解决方案是将素数视为分形，因为驱动它的数据递归。在本文中，我将用这种思路来描述素数的结构。对这种结构的检查将显示所有素数以及孪生素数的位置，并证明确实存在无限多的孪生素数。
算法
埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种寻找素数的公认算法，它通过反复标记每个素数的倍数来工作，从而标记的值不能被视为素数，因此建立了一种排除模式。
static void Sieve()
{
// Local data
uint size = 1 << 20;
bool[] notPrime = new bool[size];
// Apply sieve: for each integer greater than 1
for( int x = 2; x < size; x++ )
// If the number is prime
if( !notPrime[x] )
// Find all products
for( int n = x + x; n < size; n += x )
// Mark as not prime
notPrime[n] = true;
// Display results
System.Console.Write( "Primes: " );
// Search number line (greater than 1)
// Limit to 100 results
for( int x = 2, index = 0; x < size && index < 100; x++)
// For numbers that are prime
if( !notPrime[x] )
// Write to console
System.Console.Write( "{0}, ", x, index++ );
// Extra line for cleanliness
System.Console.WriteLine();
}
在我的算法中，筛法是还原性的；我们不为每个候选整数维护状态信息，而是简单地将该整数从潜在的数轴上移除。实现这一目标的一种朴素方法是扩展之前的算法，使下一个循环仅使用仍然可能为素数的值重新初始化。
static void ReductiveSieve()
{
// Local data
int size = 1 << 16;
int[] numberLine = Enumerable.Range( 2, size ).ToArray();
int pointer = 0;
// Apply sieve: for each integer greater than 1
while( pointer < numberLine.Length )
{
// Locals
int x = numberLine[pointer];
int index = pointer;
// Find all products
for( int n = x + x; n < size; n += x )
{
// Fast forward through number-line
if( numberLine[index] != n )
while( numberLine[++index] < n ) ;
// If the number was not already removed
if( numberLine[index] == n )
{
// Mark as not prime
numberLine[index] = 0;
}
}
// Reduce number-line
numberLine = numberLine.Where( n => n > 0 ).ToArray();
// Move number-line pointer forward
pointer++;
}
// Display first 100 results
System.Console.WriteLine( "Primes: {0}", String.Join( ", ", numberLine.Take( 100 ) ) );
}
对于算法中经过的每个素数，计算在某个数字必须被排除为非素数之前，作为潜在素数发出的值的数量。这会产生一个模式，作为查找几乎连续的潜在素数的结果。由于在连续传递之间修改了数轴（引入了递归），因此每个模式都特定于生成它的素数，并且是唯一的；然而请注意，给定正确的信息，一个模式可以用来生成下一个模式。
static void GeneratePrimePattern( int ordinal )
{
// Contract
if( ordinal < 1 )
throw new ArgumentOutOfRangeException( "ordinal" );
// Local data
int size = 1 << 18;
int[] numberLine = Enumerable.Range( 2, size ).ToArray();
int pointer = 0;
// Apply sieve: for each integer greater than 1
while( pointer < numberLine.Length )
{
// Locals
int x = numberLine[pointer];
int index = pointer;
List<int> pattern = new List<int>();
int skips = 0;
// Find all products
for( int n = x + x; n < size; n += x )
{
// Fast forward through number-line
if( numberLine[index] != n )
while( numberLine[++index] < n )
skips++;
// If the number was not already removed
if( numberLine[index] == n )
{
// Mark as not prime
numberLine[index] = 0;
// Add skip count to pattern
pattern.Add( skips );
// Reset skips
skips = 0;
}
// Otherwise we've skipped again
else skips++;
}
// Reduce number-line
numberLine = numberLine.Where( n => n > 0 ).ToArray();
// If we have a pattern we want
if( pattern.Any() && pointer == ordinal - 1 )
{
// Report pattern
int previousValue = 3; // > 2
System.Console.WriteLine( "Pattern P({0}) = {1} :: p({0}) = {2}", pointer + 1, numberLine[pointer], String.Join( ", ", pattern.TakeWhile( value => previousValue > 2 && ( previousValue = value ) > 0 ) ) );
return;
}
// Move number-line pointer forward
pointer++;
}
// Display first 100 results
System.Console.WriteLine( "Primes: {0}", String.Join( ", ", numberLine.Take( 100 ) ) );
}
* 这些代码片段在源项目中，但不是调用图的一部分；它们在 Main 中被注释掉了。
还原性筛法发出的模式有几个有趣的特性。每个模式都是重复的，并且在所有情况下都以小于等于2的数字终止。实际上，除了P(1) = 2的模式外，所有模式都是2，P(1) = 2的模式只是简单的重复1。这些模式，当不考虑它们的终止符时，长度为奇数，并且从中心数字开始对称（例如 A, B, C, B, A, 2）。此外，给定模式中所有数字的总和是下一个模式的长度。
| 目录 | 值 | 模式长度 | 模式 | Sum | Average |
| 1 | 2 | 1 | 1 | 1 | 1 |
| 2 | 3 | 1 | 2 | 2 | 2 |
| 3 | 5 | 2 | 6, 2 | 8 | 4 |
| 4 | 7 | 8 | 11, 6, 3, 6, 3, 6, 11, 2 | 48 | 6 |
| 5 | 11 | 48 | 25, 4, 9, 4, ..., 4, 9, 4, 25, 2 | 480 | 10 |
| 6 | 13 | 480 | 33, 8, 6, 10, ..., 10, 6, 8, 33, 2 | 5760 | 12 |
| 7 | 17 | 5760 | 54, 5, 12, 18, ..., 18, 12, 5, 54, 2 | 92160 | 16 |
| 8 | 19 | 92160 | 64, 12, 18, 6, ..., 6, 18, 12, 64, 2 | 1658880 | 18 |
| 9 | 23 | 1658880 | 90, 22, 6, 20, ..., 20, 6, 22, 90, 2 | 36495360 | 22 |
符号
在本文中，我将引用一个从其索引值生成素数的函数：P(x) = n
P(4) = 7
以及为每个素数生成的模式：p(x) = [...]
p(4) = 11, 6, 3, 6, 3, 6, 11, 2
当引用整个集合时，格式为P(x) = n :: [...]
P(4) = 7 :: [11, 6, 3, 6, 3, 6, 11, 2]
一个单撇号表示模式被反转：dp(x)’ 双撇号表示模式经过特殊镜像：dp(x)”
dp(4) = 4, 2, 4, 2, 4, 6, 2
dp(4)' = 2, 6, 4, 2, 4, 2, 4
dp(4)" = 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4 + 6, 2, 6
点运算符执行特殊连接，同时注意系列中重叠的数字。
dp(4)" = dp(4) . dp(4)' + [ . ]
我承认 [ . ] 符号很奇怪。我的意思是，我们必须建立 dp 和 dp’ 是如何组合的（例如，使用 [6,2,6]，这是 tail( dp(x), 2)”，但我不是要递归）。我很抱歉我不知道如何用数学方式来描述。具有讽刺意味的是，概念化这个长期存在问题的抽象方法在表达这个概念时有点碍事。另一种看待我们对称模式的方式是说：它已经是一个镜像了，让我们以一种由原始对称模式的两边形成的平滑边缘的方式来镜像这个镜像。请注意，虽然 p(4) 足够短以至于可以表达这一点，但这种模式的简单性并不意味着我描述的点运算是必需的。检查更大的模式表明，这是一种特殊的镜像运算，在附带的代码中，使用 Linq 扩展方法在 RepeatingPattern.Expand 函数中进行了演示。
获取模式
对于 P(1) = 2 :: [1]，我们应该排除偶数作为潜在素数。这意味着我们发出一个值（3），排除一个值（4），发出（5）并排除（6）。因此，P(1) 将发出所有大于2的奇数。
3, [4], 5, [6], 7, [8], 9, [10], 11, [12], 13, [14], 15, [16], 17, [18], 19, [20], 21 ...
由于我们在排除一个值之前发出了1个潜在素数，因此结果模式为[1]。
对于 P(2) = 3 :: [2]，我们遵循相同的模式，只是这一次我们在排除一个数字之前发出两个值作为潜在素数。从 n = 3 开始，我们发出 5，然后是 7，然后移除 9。发出 11，13，然后移除 15。这个过程继续，发出
5, 7, [9], 11, 13, [15], 17, 19, [21], 23, 25, [27], 29, 31, [33], 35 ...
由于我们在排除一个值之前发出了2个潜在素数，因此结果模式为[2]。
对于 P(3) = 5 :: [6, 2]，我们遵循相同的模式，但每次跳过处理后，我们将模式中的值的索引递增，用作要发出的值的数量。发出6个值，跳过1个值，发出2个值，再次跳过1个值。
7, 11, 13, 17, 19, 23, [25], 29, 31, [35], 37, 41, 43, 47, 49, 53, [55], 59, 61, [65] ...
由于我们在排除一个值之前发出了6个潜在素数，然后又发出了两个潜在素数才排除一个值，因此结果模式为[6,2]。然后模式重复。后续模式会一直生成下去，没完没了。
从模式渲染，一种朴素的方法
如果我们已经将模式存储在内存中，我们已经可以看到如何使用它来生成素数。从3（P(1)后的第一个值）开始，按顺序迭代所有自然数。将每个值作为输入传递给一个使用相应模式 [P(1) .. P(x)] 配置的过滤器集合。每个过滤器的操作将跳到下一次迭代，或将输入值发出到链中的下一个过滤器。最后一个过滤器将在输入值小于 P(x) 的平方时发出素数值。
过滤器通过跟踪它收到的输入值的计数以及模式中的索引来工作。当计数器小于当前索引处模式的值时，输入值将被发出到每个连续的过滤器。当计数器达到当前模式值时，计数器将被重置，索引将被递增，并根据模式的长度进行模运算。如果一个值没有被发出到下一个过滤器，则下一次迭代应立即开始。
分析
我开始这项研究的最终目标是找到允许按索引查找素数的公式。考虑到这一点，我们可以得出结论，为了生成一个素数，我们只需要那些种子素数值等于且小于我们要查找的值的平方根的模式。
在模式生成过程中，每个模式的第一次排除发生在模式的素数平方处。
- P(1) = 2 第一次排除是 4
- P(2) = 3 第一次排除是 9
- P(3) = 5 第一次排除是 25
在模式生成过程中，我们也可以发出对应于每个跳过数字的值。这些数字本身不是素数，因为它们被有效地标记为非素数，然而，哪种模式导致了跳过是有趣的。检查 P(4) = 7 的模式，其集合为 [11, 6, 3, 6, 3, 6, 11, 2]。因此，跳过的值分别为：[49, 77, 91, 119, 133, 161, 203, 217]。这里的所有数字都固本地被7整除；因子分解后列表为：[7, 11, 13, 17, 19, 23, 29, 31]。值得注意的是，因为模式会重复，列表在技术上会继续下去。然而，模式强制执行跳过的点对于理解我们生成的值之间的关系很有趣。
对于之前的模式 P(3) = 5 是 [6,2]，跳过的值以：[25, 35, 55, 65, 85, 95, 115, 125] 开始。因子分解我们看到 5 * [5, 7, 11, 13, 17, 19, 23, 25]。我们看到这个模式可以生成的最大素数是23。可以发出的素数数量（不包括用于生成的模式相关的值）是模式的值 [6] 的第一个值。实际上，如果我们继续我们的样本，我们将看到 [145, 155, 175, 185]，因子分解为 5 * [29, 31, 35, 37]。这意味着我们在需要拒绝一个发出值之前找到了另外2个连续素数。这个属性对于任何已建立的模式都是一致的：与跳过点相关的值直接可被一个素数序列整除，该素数序列以 P(x) = n 中的 n 开头，并包含 m 个连续素数，其中 m 是 p(x) 在特定索引处的值。
理解模式
上述分析表明，与跳过值相关的值可以直接除以一个素数。我们看到，对于我们存储的模式值，我们有一个关联的素数。我们看到，由于每个模式都以关联素数开头，因此连续模式之间存在大量重叠。
P(2) = 3 :: [3]
P(3) = 5 :: [5, 7]
P(4) = 7 :: [7, 11, 13, 17, 19, 23, 29, 31]
P(5) = 11 :: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...]
这是个好消息，因为如果我们能够推导出从模式值（也称为发出计数）获得数学方法，我们就可以使用一个模式直接输出一个素数，而无需计算其他素数。假设我们可以为任何基数素数生成模式，并且我们可以选择正确的基数素数模式来生成，那么我们很可能可以大大降低生成素数的复杂性。
让我们来考察 p(4)
P(4) = 7 :: [11, 6, 3, 6, 3, 6, 11, 2]
为每个跳过记录的值是
[49, 77, 91, 119, 133, 161, 203, 217]
知道每个模式都以 P(x)^2 开头，我们可以排除第一个值：49。然后，我们可以通过执行连续减法来减去每个值之间的距离来简化列表：77 - 49, 91 - 77 ... 由于这些也是 P(x) 的倍数，我们可以通过分解关联的素数来进一步简化，并生成 dp(x)：
[28, 14, 28, 14, 28, 42, 14] / 7 = [4, 2, 4, 2, 4, 6, 2]
出现了一个有趣的现象。模式仍然以2结尾，但2现在是合法的模式内数字。仍然存在对称性，但现在最后两个数字被排除了。这通过 dp(x)” 将如何构建来进一步加强。其余的数字显示了相同类型的模式，并且与 p(x) 的输出类似地绘制，但倒数第二个数字似乎是 p(x) 中包含的值的平均值。
对 p(5) 执行相同的转换
P(5) = 11 : [25, 4, 9, 4, 10, 14, 3, 15, 9, 4, 8, 14, 15, 4, 14, 9, 4, 14, 10, 13, 19, 10, 4, 8, 4, 10, 19, 13, 10, 14, 4, 9, 14, 4, 15, 14, 8, 4, 9, 15, 3, 14, 10, 4, 9, 4, 25, 2]
为每个跳过记录的值是
[121, 143, 187, 209, 253, 319, 341, 407, 451, 473, 517, 583, 649, 671, 737, 781, 803, 869, 913, 979, 1067, 1111, 1133, 1177, 1199, 1243, 1331, 1397, 1441, 1507, 1529, 1573, 1639, 1661, 1727, 1793, 1837, 1859, 1903, 1969, 1991, 2057, 2101, 2123, 2167, 2189, 2299, 2321]
执行连续减法和除法后，dp(5)
[2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2]
同样，除了最后两位数字外，所有数字都形成一个对称模式，p(5) 的平均值为 10，并且终止符一直保留。我认为终止符有几个作用，其中一个作用是允许剥离最后两个值。在连续运行非常大的模式时，每个 p(x) 的第一个和倒数第二个数字与集合的其余部分相比都是相对较大的值。仅比较 p(x) 的内部集合与 p(x)[i] – p(x)[i-1]，我们会发现一个惊人的相似性。
11: 6, 3, 6, 3, 6 :11
4, 2, 4, 2, 4
25: 4, 9, 4, 10, 14, 3, 15, 9, 4, 8, 14, 15, 4, 14, 9, 4, 14, 10, 13, 19, 10, 4, 8, [mirror]
2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, [mirror]
这表明这些模式共享相同的波形，尽管幅度差异很大。另一个值得注意的组成部分是，每个连续模式都包含前一个模式。
p(4) . p(4)' = [ 4, 2, 4, 2, 4, 6, 2 ] . [ 2, 6, 4, 2, 4, 2, 4 ] =
[4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2+4]
p(5) = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, [mirror]]
在构建 dp(4)” 时，模式在最后一个/第一个元素上进行镜像和合并。注意集合的对齐，您可以看到第一个模式嵌入在第二个模式的开头（因此也是结尾），除了第一个数字。跳过的部分正好是第一部分。最后两个数字被添加以产生最终的直接重叠。这似乎有点牵强；然而，相同的模式继续发生。让我们看看 dp(4) 和 dp(5) 的重叠。第一行是 dp(4)” 的重复，偏移一位，第二行是 dp(5)。在值不相同的的地方，可以通过与镜像序列中下一个数字相加来进行校正。请注意这些加法何时发生：
看到了吗？很明显，当我们将模式放在平等的基础上，通过减少它们到微分跳过计数时，我们可以预测连续模式。但是我们怎么知道加法发生在哪里呢？
让我们来考察 p(4) 的这个构造
P(4) = 7
p(4) = [11, 6, 3, 6, 3, 6, 11, 2]
dp(4) = [4, 2, 4, 2, 4, 6, 2]
将镜像序列 dp(4)’ 附加在中心值上进行重叠
m = [4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4]
序列的元部分 (6, 2) 应该以同样的方式反映
w = [6, 2, 6]
m+w 的长度是已知的
r * ( len( m ) + len( w ) ) = sum( p( 4 ) ) = 48
这意味着我们应该重复模式 3 次：mwmwmw
考察输出与目标模式 dp(5) 的偏移：
4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2+4, 6, 2, 6, 4, 2, 4+2, 4, 6, 2+6, 4, 2, 4, 2, 4, 6+2,
2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8,
6, 4, 2+4, 2, 4, 6, 2, 6, 4+2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4+6, 2,
6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2,
我们看到有地方需要将值相加。回想一下模式代表的含义（发出和跳过），这是有道理的，因为有一些位置被特定模式使不可用。我们已经将数学进行了移位，现在我们正在计算连续性，因此跳过一个值与对序列中的下一个值进行加法相同。在这种情况下，生成下一个模式时通过的连续值本身就包含在一个模式中。在 2+4 之前有 10 个值，因此 2+4 的位置是 11。在这个加法和下一个加法 4+2 之间有 5 个值，使其相对位置为 6。遵循这个趋势，您会得到以下模式
[11, 6, 3, 6, 3, 6, 11]
这表明如何从种子 p(x) 和相应的 dp(x) 来展开模式 dp(x+1)。
渲染素数
给定一个特定的 p(x)，可以通过用内存交换计算，在近 O( log N ) 的时间内生成 n 个连续素数。因为 dp(x) 包含长度为 P(x) 的连续间隔，而 P(x)^2 是由过滤器 p(x) 发出的第一个素数，当然我们知道 x，所以我们可以直接计算素数。
P( x + i ) = ( sum( first( dp( x ), i ) ) * p + p^2 ) / p
x 是我们正在使用的模式的索引 p 是关联素数/dp(x) 可以生成的最低值 i 是 dp(x) 中可用素数的所需索引
以 dp(4) 为例：
// Conceptually
dp(4) = [4, 2, 4, 2, 4, 6, 2]
p = P(n = 4) = 7
i = 2
P(6) = ( sum( [4,2] ) * 7 + 49 ) / 7
= 91 / 7
= 13
// Simplified
P(8) from dp(4) => 7 + sum( [4,2,4,2] )
= 7 + 12
= 19
不幸的是，这个运算不是线性的，但我们正在接近！不幸的是，考虑到模式很快就会变得非常长，膨胀一个模式所需的加载时间对于减少按索引生成素数所需的数学运算来说并不是一个好的权衡。
这个算法的一个巧妙实现可以从一个已知的模式开始，并就地展开它，忽略大于所需索引的值，只保留一个运行总和，这将允许以相对较小的内存占用找到正确的值，前提是模式展开的镜像性质能够被正确处理。
孪生素数
这种结构的发现也证明了存在无限多个孪生素数。前两个模式：[1]、[2] 是所有孪生素数的基础。第一个模式确保跳过每隔一个值，只产生奇数。第二个允许在再次发生跳过之前连续发出两个奇数，从而生成孪生素数候选。下一个应用的数值来自下一个模式 [6, 2]，其中 6 成为发出的值的数量，发出的值是孪生素数对。因此，6 将发出 3 对潜在的孪生素数。
为了解决哪些对是素数，我们看展开模式的算法：dp(x)。我们可以得出结论，dp(x) 中的每个 2 都是孪生素数，因为 dp(x) 代表素数之间的相对跳跃。另外，因为每个素数代表一个模式，每个 P(x) 都是孪生素数对的开始，其中 dp(x) 以 2 开头。后续模式将导致跳过（在已知边界处），但可以肯定的是，在迭代模式链时（参见基于过滤器的朴素方法），p(2) 将产生无限多的孪生素数，使得 p' - p = 2k 对于 k = 1 是无界的。我在此向阿尔方斯·德·波利尼亚克致敬，请我请他喝一杯。
因为 dp(x+1) 可以通过将 p(x) 应用于 dp(x)” 来生成，所以可以证明素数和孪生素数都非常具体地发生。素数的结构中不存在随机性。另外，通过仔细分析展开模式的机制以及排列数学，很可能会找到孪生素数之间的最大值。
1 是素数吗？
我花了一些时间思考 1 是否是素数的合法性：P(0) = 1。我认为阻止这一点的规则是语义上的。1 可以被 1 和自身整除。说：“不重复！”来排除一个特定情况有点武断。似乎 1 确实是孤独的数字。随着这个解决方案的发展，我意识到 p(0) 无法被描述（尽管我很想）。如果 p(0) == [0]，那么 p(1) 的长度必须为 0，所以这是不正确的。下一个模式的长度为一，所以 p(0) == [1]？错误。算法规定了一种跳过策略，因此不规定跳过策略的数字具有未定义的效果。因此，我终于接受了 1 应该被排除为非素数的观点。另一方面，考虑到您从 P(1) = 2 :: [1] 开始生成模式，1 是播种所有模式的数字，所以我欣慰地认为 1 被排除是因为它代表了所有素数和素数间隔模式产生的基础单元。