孪生小素因子数

liangbch

首先给出几个定义：
小素因子数：
   如果一个数的所有素因子都很小，这样的数可以叫做小素因子数。小素因子数是相对的。
k阶小素因子数：
  我们把第1个素数称为$P_1$,把第2个素数称为$P_2$,把第n个素数称为$P_n$,显然，$p_1$=2,$p_2$=3,$p_3$=5,$p_4$=7. 那么对于任意一个大于1的整数，如果他的所有素因子都小于等于$P_k$,那么我们称这个数为k阶小素因子数。
孪生k阶小素因子数：
  如果n是k阶小素因子数，n+1也是k阶小素因子数，我们称n和n+1为孪生k阶小素因子数。

  小素因子数对计算对数很有用，如果一个数x=（1+a)*n, n是k阶小素因子数，a趋于0，那么我们就能用k个素数的对数来近似表示x的对数。这时，由于a很接近于0，因此，log(1+a)的泰勒展开是收敛的很快，所以计算log(x)很容易。

  更进一步，如果我们有足够多的k阶小素因子数，我们可以构造一个分数$c/d$,c和d都是k阶小素因子数,使得$c/d$足够接近给定的数x,这样$log(x) =log((c/d)*(1+a))=log(c)-log(d)+log(1+a)$,a可以非常小。这样，log(1+a)可以快速求的，而log(c)和log(d)可以通过前k的素数的对数求的。

  以上是我将要去做的一个求中等精度的任意数的对数算法的基本思想。先不说这么多了。下面给出我的问题。如何快速构造孪生k阶小素因子数？现在有2种算法，速度快的只能构造出部分孪生k阶小素因子数，而能够构造出所有孪生k阶小素因子数的算法则速度较慢。现有的那个速度较慢的那个版本求出所有$2^64$以内的孪生16阶小素因子数大约需要1整夜。

  不知大家可否有什么方法，求出所有的孪生K阶小素因子数？

无心人

$P_16 = 53$吧？

另外，我觉得这种方法求对数很不好
非常不好
因为求对数的算法是二次收敛的
所以这么做
我觉得并不比直接求快多少

liangbch

没错，$P_16=53$.
我说的是中等精度。比如精确到几百位，几千位。如果要求计算到更高的精度，那么这个方法就没有优势了。
尽管没有实验数据，我确信在一定的精度范围内，这个算法是最快的。当然，这个算法目前仍未最终实现。
另外值得一提的是，当a很小时，计算log(1+a)也有比直接使用泰勒公式更快的算法。

无心人

翻来翻去终于找到个传统方法计算对数的公式
计算$ln x$，其中$0.5 <= x < 1$
变换公式
$ln x = ln {prod_{i=1}^R a_ix} - sum_{i = 1}^R ln a_i$
定义:
$a_0 = 1, a_i = 1 + 2^{-i}$
停止条件：
$1- prod_{i=1}^Ra_ix < 2^{-R}$
结果最大误差：$2^{- 2 R - 1}$

liangbch

在一篇名为：The logarithm constant: log 2  的文章中第7节  log 2 and the AGM 也提到对数的计算方法，应该和你在楼上提到的算法是一致的。
另外，在本站 超越函数的高精度计算 4#附件中也给出的对数的算法，这2种算法应该是不一样的。

medie2005

求孪生k阶小素因子数可以转化为一个16元的带约束的线性整数规划问题。

无心人

TO 5#
不是的
我看了
和那个网页不沾边

另外我说这个算法不是AGM的
所以速度应该慢于AGM

liangbch

话是这么说，可是很难想出一个有效的方法去得到这个线性规划的所有解。

medie2005

lattice reduction.

无心人

media2005换个头像吧