如何求和序列？

Question

我如何总结以下序列：

⌊n/1⌋ + ⌊n/2⌋ + ⌊n/3⌋ + ... + ⌊n/n⌋

这只是 C++ 上 O(n) 的解决方案：

#include <iostream>
int main()
{
   int n;
   std::cin>>n;
   unsigned long long res=0;
   for (int i=1;i<=n;i++)
   {
      res+= n/i;
   }
   std::cout<<res<<std::endl;
   return 0;
}

你知道比这更好的解决方案吗？我的意思是 O(1) 或 O(log(n))。感谢您的宝贵时间 :) 和解决方案

编辑：谢谢你所有的回答。如果有人想要解决方案 O(sqrt(n))：蟒蛇：

import math
def seq_sum(n):
 sqrtn = int(math.sqrt(n))
 return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2
n = int(input())
print(seq_sum(n))

C++:

#include <iostream>
#include <cmath>
int main()
{
   int n;
   std::cin>>n;
   int sqrtn = (int)(std::sqrt(n));
   long long res2 = 0;
   for (int i=1;i<=sqrtn;i++)
   {
      res2 +=2*(n/i);
   }
   res2 -= sqrtn*sqrtn;
   std::cout<<res2<<std::endl;
   return 0;
}

Answer 1

对于大 n，使用公式：

其中

（是超越数。）

有关详细信息，请参阅 Euler-Mascheroni constant 文章。

Answer 2

摘自 Divisor summatory function、

上的维基百科文章

其中。那应该提供时间解决方案。

编辑：整数平方根问题也可以用平方根甚至对数时间来解决 - 以防万一不明显。

Answer 3

让我们将所有数字 {1, 2, 3, ..., n} 分成两组：小于或等于 sqrt(n) 和大于 sqrt(n)。对于第一组，我们可以通过简单的迭代计算总和。对于第二组，我们可以使用以下观察：if a > sqrt(n)，than n / a < sqrt(n)。这就是为什么我们可以迭代 [n / i] = d 的值（从 1 到 sqrt(n)）并计算 [n / i] = d 的 i 的数量。可以在 O(1) 中找到一个固定的 d，使用 [n / i] = d 表示 i * d <= n and i * (d + 1) > n 的事实，它给出 [n / (d + 1)] < i <= [n / d]。

第一组和第二组在 O(sqrt(n)) 中处理，总共需要 O(sqrt(n)) 时间。

Answer 4

这是Dirichlet's divisor summatory function D(x). Using the following formula (source)

哪里

给出以下 O(sqrt(n)) psuedo-code（恰好有效 Python）：

def seq_sum(n):
  sqrtn = int(math.sqrt(n))
  return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2

备注：

Python中的//运算符是整数，即截断、除法
math.sqrt()为例。严格来说，这应该使用 exact integer square root algorithm 而不是 floating-point 数学。

Answer 5

Polymath 项目草拟了一种在时间 O(n^(1/3 + o(1)) 内计算此函数的算法，请参阅第 8-9 页的第 2.1 节：

http://arxiv.org/abs/1009.3956

该算法涉及将区域分割成足够细的区间，并估计每个区间的值，其中选择的区间足够细，以便四舍五入时估计值是准确的最接近的整数。所以你直接计算到某个范围（他们建议 100n^(1/3) 但你可以小心修改它）然后在这些薄片中完成其余部分。

有关此序列的详细信息，请参阅 the OEIS entry。

编辑：我现在看到 Kerrek SB 在评论中提到了这个算法。不过，公平地说，我在 5 年前就在 OEIS 中添加了评论，所以我不会因为发布 'his' 答案而感到难过。 :)

我还应该提到，没有 O(1) 算法是可能的，因为答案大约是 n log n，因此即使 写出来 也需要时间 > log n。

Answer 6

你可以注意到在集合 S = {⌊n/1⌋, ⌊n/2⌋, ..., ⌊ 中有 O(n^(1/2)) 个唯一值n/(n-1)⌋, ⌊n/n⌋}。因此，您可以计算 O(n^(1/2))

中的函数

此外，由于此函数是不对称的，您甚至可以使用以下公式更快地计算 x2：D(n) = Σ(x=1->u)(⌊n/x⌋) - u^2因为你 = ⌊n^(1/2)⌋

更复杂但更快：使用 Richard Sladkey 在 this paper 中描述的方法，您可以在 O(n^(1/3))

中计算函数

如何求和序列？

How to sum sequence?

c++

algorithm

math

discrete-mathematics