找到不小于N的最小常数

Question

常数是均匀分配60的幂的数字.例如,60 ² = 3600 = 48×75,因此48和75都是60的幂的除数.因此,它们也是常规数.

这是四舍五入到下一个幂的延伸.

我有一个整数值N,它可能包含大的素因子,我想把它四舍五入到只由小素因子组成的数字(2,3和5)

例子:

• f(18) == 18 == 21 * 32
• f(19) == 20 == 22 * 51
• f(257) == 270 == 21 * 33 * 51

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

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

Answer 1

好的,希望第三次是这里的魅力.用于p的初始输入的递归分支算法,其中N是在每个线程内"构建"的数字.这里的NB 3a-c作为单独的线程启动或以其他方式异步完成(准).

1. 在p之后计算下一个最大的2的幂,称之为R. N = p.

2. N> R？退出这个帖子.p只由小素因子组成吗？你完成了.否则,请转到步骤3.

3. 在3a-c中的任何一个之后,转到步骤4.

   a)圆形p到最接近的2的倍数.这个数字可以表示为m*2.
   b)圆形p到最接近的3的倍数.这个数字可以表示为m*3.
   c)圆形p到最接近的倍数5.该数字可表示为m*5.

4. 转到步骤2,p = m.

我省略了关于跟踪N的记账,但我认为这很简单.

编辑:忘了6,谢谢ypercube.

编辑2:如果这达到30,(5,6,10,15,30)意识到这是不必要的,那就把它拿出来.

编辑3 :(我承诺的最后一个!)添加了30次幂检查,这有助于防止此算法占用所有RAM.

编辑4:根据finnw的观察,将30的幂变为2的幂.

Answer 2

通过直接枚举三元组,可以及时在第n个成员周围产生任意薄的汉明序列切片.~ n^(2/3)(i,j,k)N = 2^i * 3^j * 5^k

该算法起作用log2(N) = i+j*log2(3)+k*log2(5); 枚举所有可能的ks,并且对于每个可能的js,找到顶部i,因此三元组(k,j,i)并且如果在给定的高对数顶部值之下的给定"宽度"内,则将其保持在"带"中(当width<1 时,最多可以存在)一个这样的i),然后通过他们的对数排序.

WP说的是n ~ (log N)^3,即运行时间~ (log N)^2.这里我们不关心序列中找到的三元组的确切位置,因此原始代码中的所有计数计算都可以丢弃:

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)下方空间中"上地壳"的成员log(N))是再次,m ~ n^2/3 ~ (log N)^2并且排序需要m log m时间(因此搜索,甚至线性,需要~ m运行时间).但是N,经过一些实证观察后,对于较大的s,宽度可以做得更小; 并且,三元组枚举的常数因子远远高于随后的排序.

即使有恒定的宽度(logarthmic)它运行速度非常快,计算汉明序列的百万个值即刻和在十亿分在0.05秒.

最初的"三重乐队"的想法归功于路易斯·克劳德(Louis Klauder),正如我在2008年关于DDJ博客讨论的帖子中所引用的那样.

更新:正如GordonBGood在评论中所指出的那样,不需要整个乐队,而只需要在目标之上和之下的一两个值.该算法很容易修改为该效果.在继续算法之前,还应该测试输入是汉明数字,以避免双精度的舍入问题.有没有比较事先知道海明数的对数是不同的(尽管四舍五入问题上升到一万亿分项的顺序在对数值使用约14显著数字,只留下1-2位的空闲时间,所以实际情况可能会转向那里;但对于十亿分之一,我们只需要11位有效数字).

update2:结果是对数的双精度将其限制在低于大约20,000到40,000个十进制数字的数字(即10万亿到100万亿分之一的汉明数).如果对于如此大的数字确实需要这个,那么算法可以切换回使用Integer值本身而不是它们的对数,这将更慢.

Answer 3

这是 Python 中的解决方案，基于Will Ness 的回答，但采用了一些捷径并使用纯整数数学来避免遇到日志空间数值精度错误：

import math

def next_regular(target):
    """
    Find the next regular number greater than or equal to target.
    """
    # Check if it's already a power of 2 (or a non-integer)
    try:
        if not (target & (target-1)):
            return target
    except TypeError:
        # Convert floats/decimals for further processing
        target = int(math.ceil(target))

    if target <= 6:
        return target

    match = float('inf') # Anything found will be smaller
    p5 = 1
    while p5 < target:
        p35 = p5
        while p35 < target:
            # Ceiling integer division, avoiding conversion to float
            # (quotient = ceil(target / p35))
            # From https://stackoverflow.com/a/17511341/125507
            quotient = -(-target // p35)

            # Quickly find next power of 2 >= quotient
            # See https://stackoverflow.com/a/19164783/125507
            try:
                p2 = 2**((quotient - 1).bit_length())
            except AttributeError:
                # Fallback for Python <2.7
                p2 = 2**(len(bin(quotient - 1)) - 2)

            N = p2 * p35
            if N == target:
                return N
            elif N < match:
                match = N
            p35 *= 3
            if p35 == target:
                return p35
        if p35 < match:
            match = p35
        p5 *= 5
        if p5 == target:
            return p5
    if p5 < match:
        match = p5
    return match

In English: 遍历 5s 和 3s 的每一个组合，快速找到每对的下一个 2 的幂 >= 目标，并保持最小的结果。（如果只有一个是正确的，那么遍历所有可能的 2 倍数就是浪费时间）。如果它发现目标已经是一个常规数字，它也会提前返回，尽管这不是绝对必要的。

我已经非常彻底地测试了它，测试了从 0 到 51200000 的每个整数，并与 OEIS http://oeis.org/A051037上的列表进行了比较，以及许多与常规数字相差±1 的大数字等。现在在 SciPy 中可用为fftpack.helper.next_fast_len，以找到 FFT 的最佳大小（源代码）。

我不确定 log 方法是否更快，因为我无法让它足够可靠地工作来测试它。不过，我认为它有相似数量的操作？我不确定，但这相当快。花费 <3 秒（或使用 gmpy 需要 0.7 秒）来计算 2 ¹⁴² × 3 ⁸⁰ × 5 ⁴⁴⁴是 2 ² × 3 ⁴⁵⁴ × 5 ²⁴⁹ +1（第 100,000,000 个常规数，有 392 位数字）之上的下一个正则数