Как суммировать последовательность?

Question

Как суммировать последовательность?

Как я могу суммировать следующую последовательность:

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

Это просто O (n) решение на 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;
}

Вы знаете лучшее решение, чем это? Я имею в виду O (1) или O (log (n)). Спасибо за ваше время 🙂 и решения

Редактировать:
Спасибо за все ваши ответы. Если кто-то хочет решение 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))

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;
}

13

algorithm c++discrete-mathematics math

Решение

Другие решения

Взято из статьи в Википедии о Сумматорная функция делителя,

где введите описание изображения здесь . Это должно обеспечить время решения.

РЕДАКТИРОВАТЬ: целочисленный квадратный корень проблема также может быть решена в квадратный корень или даже логарифмическое время — на случай, если это не очевидно.

7

Проект Polymath наметил алгоритм для вычисления этой функции за время O (n ^ (1/3 + o (1))), см. Раздел 2.1 на страницах 8-9:

http://arxiv.org/abs/1009.3956

Алгоритм включает разделение области на достаточно тонкие интервалы и оценки значение для каждого, где интервалы выбраны достаточно тонкими, чтобы оценка была точной при округлении до ближайшего целого числа. Таким образом, вы вычисляете до некоторого диапазона напрямую (они предлагают 100n ^ (1/3), но вы можете изменить это с некоторой осторожностью), а затем делаете все остальное в этих тонких срезах.

Увидеть запись OEIS для получения дополнительной информации об этой последовательности.

Edit: теперь я вижу, что Kerrek SB упоминает этот алгоритм в комментариях. Справедливости ради, однако, я добавил комментарий к OEIS 5 лет назад, так что я не чувствую себя плохо из-за публикации «его» ответа. 🙂

Я должен также упомянуть, что никакой алгоритм O (1) невозможен, так как ответ — около n log n и, следовательно, даже выписывая это занимает время> войти n.

5

Поделим все число {1, 2, 3, ..., n} на 2 группы: меньше или равно sqrt(n) и больше чем sqrt(n), Для первой группы мы можем вычислить сумму с помощью простой итерации. Для второй группы мы можем использовать следующее наблюдение: если a > sqrt(n), чем n / a < sqrt(n), Вот почему мы можем перебрать значение [n / i] = d (от 1 в sqrt(n)) и вычислить количество таких i тот [n / i] = d, Это можно найти в 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)) время в общей сложности.

1

Для больших nиспользуйте формулу:

введите описание изображения здесь

где введите описание изображения здесь

( введите описание изображения здесь это трансцендентное число.)

Увидеть Постоянная Эйлера-Мачерони статья для получения дополнительной информации.

0

Источник

Accepted Answer

Это Сумматорная функция делителя Дирихле D (x). Используя следующую формулу (источник)

Д (х)

где

дает следующее O(sqrt(n)) псевдо-код (который является допустимым 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() используется в качестве иллюстрации. Строго говоря, это должно использовать алгоритм целочисленного квадратного корня вместо математики с плавающей точкой.

24