2
How to make a sequence sum?
source link: https://www.codesd.com/item/how-to-make-a-sequence-sum.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
How to make a sequence sum?
advertisements
How can I sum the following sequence:
⌊n/1⌋ + ⌊n/2⌋ + ⌊n/3⌋ + ... + ⌊n/n⌋
This is simply O(n) solution on C++:
#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;
}
Do you know any better solution than this? I mean O(1) or O(log(n)). Thank you for your time :) and solutions
Edit: Thank you for all your answers. If someone wants the solution O(sqrt(n)): Python:
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))
#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;
}
This is Dirichlet's divisor summatory function D(x). Using the following formula (source)
where
gives the following O(sqrt(n))
psuedo-code (that happens to be valid Python):
def seq_sum(n):
sqrtn = int(math.sqrt(n))
return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2
Notes:
- The
//
operator in Python is integer, that is truncating, division. math.sqrt()
is used as an illustration. Strictly speaking, this should use an exact integer square root algorithm instead of floating-point maths.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK