Найти формулу для суммы

[Pigs]

Доброго времени суток господа

Помогите пожалуйста понять каким образом, получить формулу для следующей суммы:


$ C = const; S_n = \sum_{i=1}^{C} \sum_{j=1}^{C/i} \sum_{k=1}^{C/j} ... \sum_{o=1}^{C/...} \sum_{n=1}^{C/o} 1 $

Всего n сумм вложенных друг в друга, первый от 1 до С, второй от 1 до С / {счетчик с предыдущего} и т.д.
конец заканчивается суммированием 1.
Как Вы уже поняли нужна формула, до которой никак не могу дойти, ночь...

[Pigs]

Pigs в сообщении #853529 писал(а):

Доброго времени суток господа

Помогите пожалуйста понять каким образом, получить формулу для следующей суммы:


$ C = const; S_n = \sum_{i=1}^{C} \sum_{j=1}^{C/i} \sum_{k=1}^{C/j} ... \sum_{o=1}^{C/...} \sum_{n=1}^{C/o} 1 $

Всего n сумм вложенных друг в друга, первый от 1 до С, второй от 1 до С / {счетчик с предыдущего} и т.д.
конец заканчивается суммированием 1.
Как Вы уже поняли нужна формула, до которой никак не могу дойти, ночь...

Вот примеры:
$ S_1 = \sum_{i=1}^{C} 1 = C S_2 = \sum_{i=1}^{C} \sum_{j=1}^{C/i} 1 = C/1 + C/2 + ... C/C = C \cdot (1 + 2 + ... + C) = C^2 \cdot (C + 1) / 2 $

а для любого n пока не знаю...

[svv]

Pigs в сообщении #853586 писал(а):

$C/1 + C/2 + ... C/C = C \cdot (1 + 2 + ... + C)$

-- Чт апр 24, 2014 01:32:50 --

Pigs в сообщении #853586 писал(а):

$\sum_{i=1}^{C} \sum_{j=1}^{C/i} 1 = C/1 + C/2 + ... C/C$

Это тоже непонятно. Пусть $C=5, i=2$. Что такое $\sum_{j=1}^{C/i} 1$ ?

[Deggial]

Определение $S_n$ некорректно, т.к. $n$ является индексом внутренней суммы и не является несвязанной переменной.

[Pigs]

Блин какую фигню написал:(
Все [C/i] - округляются вниз $S_2$ вообще неправильно раскрыл.

>Определение $S_n$ некорректно, т.к. $n$ является индексом внутренней суммы и не является несвязанной переменной.

Этим лишь хотел показать, что всего n сумм вложенных друг в друга.

-- 24.04.2014, 08:23 --

Так будет правильнее
$ C = const; S_n = \sum_{i=1}^{C} \sum_{j=1}^{\lfloor C/i \rfloor} \sum_{k=1}^{\lfloor C/j \rfloor} ... \sum_{o=1}^{\lfloor C/... \rfloor} \sum_{p=1}^{\lfloor C/o \rfloor} 1 $


... - индекс с предыдущей суммы.
n - количество сумм вложенных друг в друга.
C - постоянное число, заданное изначально.

[kp9r4d]

Pigs
Там вряд ли формула в замкнутом виде будет. Из тех соображений хотя бы, что нету замкнутой формулы для частичной суммы гармонического ряда (та самая, которая $\sum\limits_{i=1}^n \frac{1}{i}$), а это ваше самое $S_2$. Вам зачем эти формулы, к слову?

[Pigs]

svv в сообщении #853625 писал(а):

Pigs в сообщении #853586 писал(а):

$C/1 + C/2 + ... C/C = C \cdot (1 + 2 + ... + C)$

-- Чт апр 24, 2014 01:32:50 --

Pigs в сообщении #853586 писал(а):

$\sum_{i=1}^{C} \sum_{j=1}^{C/i} 1 = C/1 + C/2 + ... C/C$

Это тоже непонятно. Пусть $C=5, i=2$. Что такое $\sum_{j=1}^{C/i} 1$ ?

ДААА как я мог так

$C/1 + C/2 + ... C/C = C \cdot (1 + 2 + ... + C)$ это же

$C/1 + C/2 + ... C/C = C \cdot H_C $

На второй вопрос:
Пусть $C=5, i=2$. $ \sum_{j=1}^{\lfloor 5/2 \rfloor} 1 = \sum_{j=1}^{2} 1 = 2 $

-- 24.04.2014, 08:41 --

kp9r4d в сообщении #853704 писал(а):

Pigs
Там вряд ли формула в замкнутом виде будет. Из тех соображений хотя бы, что нету замкнутой формулы для частичной суммы гармонического ряда (та самая, которая $\sum\limits_{i=1}^n \frac{1}{i}$), а это ваше самое $S_2$. Вам зачем эти формулы, к слову?

Ну мне хотя бы переделать эту формулу на меньшее число сумм как нибудь.

Общая формула нужна для того, чтобы быстро оценить всю сумму $S_n$ для заданных $C$ и $n$.

[Pigs]

Кстати это не гармонический ряд, некорректно выносить C.
То есть надо вот такие суммы считать:

$\sum\limits_{i=1}^n \lfloor \frac{n}{i} \rfloor = 2 \cdot \sum\limits_{i=1}^{\lfloor \sqrt{n} \rfloor }\lfloor \frac{n}{i} \rfloor - {\lfloor \sqrt{n}\rfloor}^2 $

[RIP]

гуглите "(обобщённая) проблема делителей Дирихле" (ошибся)

[Sonic86]

Если $S_n=\sum\limits_{k=1}^n\left[\frac{n}{k}\right]$, то $S_n=\sum\limits_{k=1}^n\tau (k)$, где $\tau(k)$ - число делителей числа $k$. Тогда $\tau(n)=S_n-S_{n-1}$. Если бы формула для быстрого вычисления $S_n$ существовала, то существовала бы быстрая формула для $\tau(n)$, а ее скорее всего нету.
Ну и вот еще есть моя дурацкая тема: topic61720.html, тут и оценка есть и отклонение от нее.

[ex-math]

RIP
Похоже, да не то же. В проблеме делителей условие суммирования $n_1\dots n_k\leqslant x$, а здесь $n_1n_2\leqslant x, \dots ,n_{k-1}n_k\leqslant x$.

[RIP]

Да, плохо присмотрелся к условию.