探索计算数论:半素数二进制序列的排序

在本文中,将使用以下的数学关系,展示2将描述这些关系,将其称为“pMod iMod 表”。

pBase1 = 任意小于 pBase2 的素数 pBase2 = 任意大于 pBase1 的素数 N = pBase2 模 pBase1 pMod = N - 1 iMod = (pBase1 模 N) 模 pMod

注意在展示2中,素数2和3没有被使用。这些素数{2, 3}以及iMod = 0或1的素数对会产生在本文后面将介绍的平凡余数。同时注意以下与最大公约数(GCD)的关系:

如果 GCD(N, iMod) != 1,那么素数对 {pBase1, pBase2} 不存在。

例如:N = 10, pMod = 9 那么对于 iMod = {2, 4, 5, 6, 8} 的非存在对。

展示3是“实际高低表”,通过检查实际的二进制序列生成。展示3有以下关系:

nMod = 一个大于0且小于pMod的数,代表序列中一个位置的余数增加,其中 H(高)= 1,空白(低)= 0 如果 iMod = 0 或 1,那么 ∑nMod = 0 每 iMod 如果 iMod > 1,那么 ∑nMod = iMod – 1 每 iMod ∑iMod = (pMod-2-x)/2 每 nMod ∑∑iMod = ∑∑nMod = (pMod – 1) * (pMod – 1 – x)/2

象限:

iMod = 2 -> pMod – 1(水平) nMod = 1 -> pMod – 1(垂直)

展示4从“第一象限高低表”和后续表格中可以得出以下关系:

nMod > 0 且 nMod < pMod,其中 nMod 高 = iMod – 1 其中 iMod > 1。 如果 iMod 为偶数 && nMod = INT(pMod / 2) 那么 nMod = 高 如果 nMod 为偶数 && iMod = INT(pMod / 2) 那么 nMod = 高 如果 INT((1*pMod + 0) / iMod) = nMod 那么 nMod = 高 如果 INT((2*pMod + 1) / iMod) = nMod 那么 nMod = 高 如果 INT((3*pMod + 2) / iMod) = nMod 那么 nMod = 高 等等。

从上述关系10,可以创建“计算高低表”。见展示5。

为了检查计算高低表的错误,可以执行计算和实际序列之间的序列检查。展示6检查两个序列的错误,并已手动修改以反映错误作为示例。展示7指示检测到错误相关的pMod。

一旦知道了发生错误的pMod(展示7),那么展示8就可以构建出来,以指示序列中错误发生的具体位置。

展示9展示了pMod = 29的算法扩展过程的简化版本。

展示10展示了平凡余数的算法扩展过程,其中iMod < 2。

展示11展示了非平凡余数的算法扩展过程的简化版本,其中iMod > 1。

展示12指示在生成序列的同时对序列进行排序的时间成本。问题可能是:“为什么要排序序列?”一个答案是:“它提供了一个工具来研究半素数二进制序列的解构。”

使用代码:

这个项目是作为一个概念原型构建的,因此没有更完善产品的用户友好错误检查。C#代码是为64位系统构建的。Microsoft Office 2007是一个32位环境,需要Excel-DNA编译为32位。如果想在64位的Microsoft Office版本上运行这个项目,将需要重新编译Excel-DNA为64位。BigInterger库已经被修改为任意大小的整数,并且使用了C# BigInteger类的例程来扩展支持这个项目所需的算法。还修改了BigInteger库的位移除法,以提高准确性,但计算速度有所损失。还有其他一些支持例程在BigInteger库中被修改,以扩大它们的准确性或支持这个项目。代码应该已经准备好在C#项目、Excel VBA和Excel电子表格中进行实验。要在Excel中使用,打开

BigInteger-packed.xll

在电子表格中,将有两个函数库,“BigInteger”和“Number Theory”。在VBA环境中需要对

BigInteger-packed.xll

的引用,以便一些宏构建在这个项目中使用的电子表格或在其他VBA应用程序中使用。Microsoft Access和Excel需要引用以下库:

Visual Basic For Applications Microsoft Access 12.0 Object Library OLE Automation Microsoft Office 12.0 Access database engine Object Microsoft ActiveX Data Objects 6.1 Library BigIntExcel

如果使用的是.NET 4.0或更高版本,可能想要修改这个项目代码,使用Microsoft的Numeric库。从研究来看,除法算法是准确性和速度的关键。

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485