algorithm - 找出不小于 N 的最小正则数

Question

Regular numbers are numbers that evenly divide powers of 60. As an example, 60² = 3600 = 48 × 75, so both 48 and 75 are divisors of a power of 60. Thus, they are also regular numbers.

这是 rounding up to the next power of two 的扩展.

我有一个整数值 N，它可能包含较大的质因数，我想将它四舍五入为仅由较小的质因数(2、3 和 5)组成的数字

例子:

• f(18) == 18 == 2<sup>1</sup> * 3<sup>2</sup>
• f(19) == 20 == 2<sup>2</sup> * 5<sup>1</sup>
• f(257) == 270 == 2<sup>1</sup> * 3<sup>3</sup> * 5<sup>1</sup>

找到满足此要求的最小数的有效方法是什么？

涉及的值可能很大，所以我想避免枚举所有从 1 开始的常规数字或维护所有可能值的数组。

Answer 1

一个可以产生任意薄的一个slice of the Hamming sequence通过直接枚举三元组 (i,j,k) 使得 N = 2 ^i * 3^j * 5^k.

该算法从 log2(N) = i+j*log2(3)+k*log2(5) 开始；枚举所有可能的 k 并针对每个所有可能的 j 找到顶部的 i 并因此找到三元组 (k,j ,i) 如果在给定的“宽度”内低于给定的高对数最高值(当 width < 1 时，最多可以有一个这样的 i) 然后按它们的对数对它们进行排序。

WP says n ~ (log N)^3，即运行时间 ~ (log N)^2。这里我们不关心找到的三元组在序列中的确切位置，所以所有的计数计算都是从the original code开始的。可以扔掉:

slice hi w = sortBy (compare `on` fst) b where       -- hi>log2(N) is a top value
  lb5=logBase 2 5 ; lb3=logBase 2 3                  -- w<1 (NB!) is log2(width)
  b  = concat                                        -- the slice
      [ [ (r,(i,j,k)) | frac < w ]                   -- store it, if inside width
        | k <- [ 0 .. floor ( hi   /lb5) ],  let p = fromIntegral k*lb5,
          j <- [ 0 .. floor ((hi-p)/lb3) ],  let q = fromIntegral j*lb3 + p,
          let (i,frac)=properFraction(hi-q) ;    r = hi - frac ]   -- r = i + q
                    -- properFraction 12.7 == (12, 0.7)

-- update: in pseudocode:
def slice(hi, w):
    lb5, lb3 = logBase(2, 5), logBase(2, 3)  -- logs base 2 of 5 and 3
    for k from 0 step 1 to floor(hi/lb5) inclusive:
        p = k*lb5
        for j from 0 step 1 to floor((hi-p)/lb3) inclusive:
           q = j*lb3 + p
           i = floor(hi-q)
           frac = hi-q-i                     -- frac < 1 , always
           r = hi - frac                     -- r == i + q
           if frac < w:
              place (r,(i,j,k)) into the output array
   sort the output array's entries by their "r" component
        in ascending order, and return thus sorted array

枚举切片中的三元组后，排序和搜索就成了一件简单的事情，实际上花费了 O(1) 时间(对于任意薄切片)找到 N 以上的第一个三元组。好吧，实际上，对于恒定宽度(对数)，切片中的数字数量((i,j,k) 中“上层”的成员 - 日志下方的空间(N) plane) 又是 m ~ n^2/3 ~ (log N)^2 并且排序需要 m log m 时间(以便搜索，即使是线性的，也需要 ~ m<​​ 运行时间)。但是根据一些经验观察，对于更大的 N，宽度可以做得更小；无论如何，三元组枚举的常数因子远高于后续排序。

即使宽度恒定(对数)，它也运行得非常快，计算汉明序列中的第 1,000,000 个值 instantly和 the billionth在 0.05 秒内。

“顶级三元组”的最初想法归功于 Louis Klauder，如 my post on a DDJ blogs discussion 中所引用回到 2008 年。

更新:如 GordonBGood 所述在 the comments ，不需要整个波段，而只需要高于和低于目标的一两个值。该算法很容易修改为该效果。在继续执行该算法之前， 还应测试输入是否为汉明数本身，以避免 double 舍入问题。比较事先已知不同的汉明数的对数没有舍入问题(虽然序列中的going up to a trillionth entry在对数值中使用了大约14位有效数字，只剩下1-2位备用，所以情况可能事实上在那里变得不确定；但对于十亿分之一，我们只需要 11 位有效数字)。

update2: 事实证明，对数的 double 将其限制为低于约 20,000 到 40,000 十进制数字的数字(即 10 万亿分之一到 100 万亿分之一的汉明数)。如果对于如此大的数字确实需要这样做，则可以将算法切换回使用整数值本身而不是它们的对数，这会更慢。