algorithm - 汉明数和双精度

Answer 1

根据经验，它高于大约 10 万亿分之一的海明数，或更高。

在这里使用你漂亮的 GCD 技巧对我们没有帮助，因为一些相邻的汉明数在它们之间必然没有公因数。

更新：在 ideone和其他地方在线尝试，我们得到

4T  5.81s 22.2MB  -- 16 digits used.... still good
                  --  (as evidenced by the `True` below), but really pushing it.
((True,44531.6794,7.275957614183426e-11),(16348,16503,873),"2.3509E+13405")
-- isTruly  max        min logval           nth-Hamming       approx.
--  Sorted   logval      difference          as i,j,k          value
--            in band      in band                             in decimal
10T   11.13s 26.4MB
((True,60439.6639,7.275957614183426e-11),(18187,23771,1971),"1.4182E+18194")
13T   14.44s 30.4MB    ...still good
((True,65963.6432,5.820766091346741e-11),(28648,21308,1526),"1.0845E+19857")

---- same code on tio:
10T   16.77s
35T   38.84s 
((True,91766.4800,5.820766091346741e-11),(13824,2133,32112),"2.9045E+27624")
70T   59.57s
((True,115619.1575,5.820766091346741e-11),(13125,13687,34799),"6.8310E+34804")

---- on home machine:
100T: 368.13s
((True,130216.1408,5.820766091346741e-11),(88324,876,17444),"9.2111E+39198")

140T: 466.69s
((True,145671.6480,5.820766091346741e-11),(9918,24002,42082),"3.4322E+43851")

170T: 383.26s         ---FAULTY---
((False,155411.2501,0.0),(77201,27980,14584),"2.80508E+46783")

Answer 2

我想您可以使用自适应任意精度来计算日志。

如果您选择对数基数 2，那么log2(2^i)是微不足道的。这消除了 1 个因素，并且 log2 具有比自然对数更容易计算的优点（例如https://en.wikipedia.org/wiki/Binary_logarithm给出了一个算法，还有 Shanks ......）。

对于 log2(3) 和 log2(5)，您将开发出足够的术语来区分两个操作数。我不知道它是否会导致比在大整数算术中直接对 3^j 和 5^k 取幂并计算高位更多的操作......但这些可以预先制表到所需的位数。