Количество повторяющихся чисел последовательности

[vitalyisaev2]

Здравствуйте.

Допустим, есть набор числовых последовательностей, получающихся друг из друга по следующему правилу:
1. Первая последовательность состоит из единиц
2. Вторая последовательность копирует первую, но на все позиции, кратные 2, вставляет 2
3. Третья последовательность копирует вторую, но на все позиции, кратные 3, вставляет 3, и так далее:

1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 2 3 2 1 3 1 2 3 2
1 2 3 4 1 3 1 4 3 2
1 2 3 4 5 3 1 4 3 5

Наверняка эта последовательность последовательностей изучалась. Существует ли аналитическая формула для определения количества повторений числа M в i-той последовательности N-ной длины? Например:

func count(M int, i int, length int) int { //... }
count(1, 1, 10) == 10
count(1, 2, 10) == 5
count(1, 3, 10) == 3
count(5, 1, 10) == 0
count(5, 5, 10) == 2

Спасибо.

[arseniiv]

Формулу всегда можно написать, а вот формулу, использующую ограниченный набор функций/операций — зависит от набора. Сначала стоит получить хоть какую-нибудь (или какие-нибудь, если получается зайти с разных сторон).

Я сокращу count(M, i, L) до $C(i, L, M)$. По вашему определению будет формула следующая:

$$C(i, l, m) = \begin{cases} 0, & m > i, \\ \sum\limits_{j = 1}^l [m|j] \left(1 - \prod\limits_{n = m+1}^i [n|j]\right), & m \leqslant i, \end{cases}$$

($m|j$ — $m$ делит $j$, $[P] := P\mathbin?1:0$ — скобки Айверсона).

Сумму выше можно тривиально раскрыть до

$$\sum\limits_{j = 1}^l [m|j] - \sum_{j = 1}^l [m|j] \prod\limits_{n = m+1}^i [n|j].$$

Первое слагаемое тут (сколько мы изначально вписываем элементов $m$) равно $\lfloor \frac{l-m+1}m \rfloor$, второе будет куда как хитрее упростить. На вашем месте я бы вооружился «Конкретной математикой» (Кнут, Грэхем, Паташник) и подобными книгами, где рассматриваются всякие способы манипуляций с суммами и прочими выражениями

[vitalyisaev2]

@arseniiv спасибо!

[Emacs24]

Выражение для подсчёта уже $i=1$ получается совсем не простым, а что там с $i=2,3,\ldots$ один Бог знает (и то сомнительно :))

Замечание 1
описанный процесс, фактически, является решетом Эратосфена, где 1-цы стоят на "неотмеченных" местах в терминах алгоритма, а остальные числа соответсвуют вычеркнутым местам. Обратим внимание, что на M-1-ой строке:

• 1-ое значение будет 1-цей
• 2, 3, …, M-1 - ые значения не будут 1-цами
• M-тое значение будет 1 тогда и только тогда, когда M – простое

Замечание 2
Число единичек на M-1-ой строке при M элементах будет равно $U(M)=C(1,M-1,M)-C(1,M-2,M)$. Это тоже простая формула, если исходная $C(i,L,M)$ – простая.

Вывод из замечаний 1 и 2
$\begin{equation*} U(M) = \begin{cases} 1 &\text{если $M$ -- составное}\\ 2 &\text{если $M$ -- простое} \end{cases} \end{equation*}$

Упс, мы вывели простую формулу для определения простоты числа…