2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Количество повторяющихся чисел последовательности
Сообщение12.09.2019, 16:23 


21/11/14
12
Здравствуйте.

Допустим, есть набор числовых последовательностей, получающихся друг из друга по следующему правилу:
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


Спасибо.

 Профиль  
                  
 
 Re: Количество повторяющихся чисел последовательности
Сообщение12.09.2019, 22:47 
Заслуженный участник


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

Я сокращу 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$, второе будет куда как хитрее упростить. На вашем месте я бы вооружился «Конкретной математикой» (Кнут, Грэхем, Паташник) и подобными книгами, где рассматриваются всякие способы манипуляций с суммами и прочими выражениями

 Профиль  
                  
 
 Re: Количество повторяющихся чисел последовательности
Сообщение13.09.2019, 11:44 


21/11/14
12
@arseniiv спасибо!

 Профиль  
                  
 
 Re: Количество повторяющихся чисел последовательности
Сообщение16.09.2019, 01:28 


16/09/19
1
Выражение для подсчёта уже $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*}$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group