2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Проверка что q это p-ый член посл.-ти
Сообщение01.09.2023, 22:09 
Аватара пользователя


22/11/13
02/04/25
549
Дана последовательность A243571. Она является перестановкой натуральных чисел. Задается как неправильный треугольник у которого длины строк это числа Фибоначчи. Генерируется он следующим образом:

  • первая строка содержит одну только единицу
  • вторая строка содержит одну только двойку
  • для $n\geqslant3$ $n$-ная строка состоит из некоторых чисел в порядке возрастания, а именно удвоенных чисел из предыдущей строки и удвоенных и увеличенных на единицу чисел из строки с номером $n-2$

Пусть некто сообщил нам что $p$-ый член заданной последовательности это $q$. Требуется это проверить. Проверка должна быть недорогая. К сожалению я плохо знаком с нотацией $O$ чтобы оценить сложность своего решения и выставить минимальные требования.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение02.09.2023, 00:21 


13/01/23
307
Можно по $q$ найти $p$, но не совсем быстро.

1) записываем $q$ в двоичной системе $q = \sum_{i=0}^{n-1} q_i \cdot 2^i$
2) номер строки, в которой находится $q$, это $N(q) = (n-1) + \sum_{i=0}^{n-1} q_i$
3) тогда $p = F_{N(q)+1} + r$, где $r$ — количество чисел $\tilde{q}<q$ с $N(\tilde{q})=N(q)$
4) таких $\tilde{q}$, в которых $m < n$ цифр, ровно $C_{m-1}^{N(q) - m}$
5) пусть $s(1) < s(2) < ... < s(k) < n$ — номера всех равных $1$ цифр $q$ ($q_{s(i)} = 1$) [$k = N(q) - n$, конечно]. Тогда таких $\tilde{q}$, в которых $n$ цифр, ровно $\sum_{i=1}^k C_{s(i)-1}^i$
6) выходит, $p = F_{N(q)+1} + \left(\sum_{m=1}^{n-1} C_{m-1}^{N(q)-m}\right) + \left(\sum_{i=1}^{k} C_{s(i)-1}^{i}\right)$

Можно улучшить?

-- 02.09.2023, 00:32 --

Получается время порядка $2nt$, где $t$ — наибольшее время, за которое можно вычислить $C_a^b$ при $a, b \leq n$ (вычислить $F_{N(q)+1}$ по сравнению с этим пустяки, вроде за $\operatorname{const} \cdot \ln(n)$ считается)

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение02.09.2023, 09:37 
Аватара пользователя


22/11/13
02/04/25
549
$N(q)$ это хорошее направление. Она даже есть в энциклопедии: A056792. И если отсортировать ее по возрастанию в паре с натуральными числами, то мы как раз получим A243571.

Чтобы проверить ваше решение, я написал программку на PARI/GP:
Код:
l(n, m) = logint(n, m)
wt(n) = hammingweight(n)
w1 = [1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 12, 16, 11, 13, 14, 17, 18, 20, 24, 32, 15, 19, 21, 22, 25, 26, 28, 33, 34, 36, 40, 48, 64, 23, 27, 29, 30, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 65, 66, 68, 72, 80, 96, 128, 31, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 67, 69]
b6(n) = my(A = Vecrev(binary(n)), B = 0, v1); v1 = vector(wt(n), i, 0); for(i=1, #A, if(A[i], B++; v1[B] = i)); v1
b7(n) = my(L = l(n, 2), A = wt(n), B = A + L, C = b6(n)); fibonacci(B+1) + sum(j=1, L, binomial(j-1, B-j)) + sum(j=1, A, binomial(C[j]-1, j))
b8(n) = b7(w1[n])

В конце я подставляю в вашу формулу последовательные значения A243571, следовательно она должна вернуть натуральные числа. К сожалению она возвращает что-то другое.

Проверка, что $q$ это $p$-ый член последовательности, это как бы не вопрос о нахождении $p$ если известно $q$. Последняя операция может оказаться относительно дорогой. А вот чтобы просто проверить - есть как минимум одно элегантное решение. К сожалению я не до конца понимаю как оно работает, но возможно после его публикации кто-нибудь сможет мне это объяснить.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение02.09.2023, 11:19 


23/02/12
3370
kthxbye в сообщении #1607653 писал(а):
К сожалению я плохо знаком с нотацией $O$ чтобы оценить сложность своего решения и выставить минимальные требования.
kthxbye в сообщении #1607694 писал(а):
К сожалению я не до конца понимаю как оно работает, но возможно после его публикации кто-нибудь сможет мне это объяснить.
Может лучше помещать такие темы в разделе ПРР.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение02.09.2023, 11:35 
Аватара пользователя


22/11/13
02/04/25
549
vicvolf в сообщении #1607705 писал(а):
Может лучше помещать такие темы в разделе ПРР.

Благодарю за совет! К сожалению в ПРР отвечают очень редко, а тут как-то больше активности.

На форуме иногда пишут о разнице ПРР и ОЗ, мол, дескать, пишите в ОЗ только если решение вам известно. Это как раз мой случай. Путь по которому мы приходим к решению - это уже отдельный вопрос. Его всегда можно уточнить у более подкованных в математике участников. Просто спрашивать - как-то скучновато, куда интереснее сначала ставить задачу или даже в какой-то мере бросать вызов.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение02.09.2023, 14:50 


13/01/23
307
kthxbye, над простым решением буду думать.

С вашей программой что-то не так. b7(2) = 3, в то время как

$2 = 10_2$
$N(2) = 2$
$F_{N(2)+1} = F_3 = 2$
Никаких $s(1), s(2), ..., s(k)$ нету
При $m=1$ имеем $C_{m-1}^{N(q) - m} = C_0^1 = 0$
То есть $F_{N(q)+1} + \left(\sum_{m=1}^{n-1} C_{m-1}^{N(q)-m}\right) + \left(\sum_{i=1}^{k} C_{s(i)-1}^{i}\right) = 2 + 0 + 0 \neq 3$

Сам программу написать не могу(

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение02.09.2023, 16:35 
Аватара пользователя


22/11/13
02/04/25
549
KhAl, приношу свои извинения. Благодарю за подсказку, что для $n=2$ никаких $s(1), s(2), ..., s(k)$ нету. Я стал смотреть на эту надпись а также на
KhAl в сообщении #1607668 писал(а):
5) пусть $s(1) < s(2) < ... < s(k) < n$ — номера всех равных $1$ цифр $q$ ($q_{s(i)} = 1$) [$k = N(q) - n$, конечно]. Тогда таких $\tilde{q}$, в которых $n$ цифр, ровно $\sum_{i=1}^k C_{s(i)-1}^i$

пытаясь понять, как это может быть.

В конце концов, до меня начало доходить что вы берете не все номера единиц со старшим битом включительно, а только те, что идут до него. Ведь вы явно пишите что $k = N(q) - n$, а т.к. $\left\lfloor\log_2 q\right\rfloor = n - 1$, то мы отнимаем не только $n-1$, но еще дополнительно одну единицу, что исключает использование старшего бита.

И все получилось! Должно быть вот так:
Код:
b6(n) = my(A = Vecrev(binary(n)), B = 0, v1); v1 = vector(wt(n)-1, i, 0); for(i=1, #A-1, if(A[i], B++; v1[B] = i)); v1
b7(n) = my(L = l(n, 2), A = wt(n), B = A + L, C = b6(n)); fibonacci(B+1) + sum(j=1, L, binomial(j-1, B-j)) + sum(j=1, A-1, binomial(C[j]-1, j))


Вашим методом можно не только проверять соответствие $q$ и $p$. Он позволяет сразу построить обратную перестановку A243571 (что, собственно, очевидно).

Благодарю за интересное решение. Рекомендую вам добавить обратную перестановку в энциклопедию. Могу помочь с оформлением, если что, пишите в лс. Добавил бы и сам с указанием вашего авторства и ссылкой на эту тему, но, к сожалению, все мои слоты для правок (коих 3) уже заняты, а одобрят их только где-то через месяц или два.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение02.09.2023, 17:22 


13/01/23
307
Цитата:
В конце концов, до меня начало доходить что вы берете не все номера единиц со старшим битом включительно, а только те, что идут до него
ой, это я сглупил, хотел написать $s(1) < s(2) < ... < s(k) < n-1$, имея в виду, что $q_{n-1} = 1$, но среди $s(i)$ числа $n-1$ не будет. Извините. За программу и за исправление спасибо.

Ещё кое-что: в комментарии "The least and greatest numbers in row n are A083329(n-1) and 2^(n-1), for n >= 1.", по-видимому, нужно заменить A083329(n-1) на A052955(n) (см. Crossrefs)

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение03.09.2023, 09:32 
Аватара пользователя


22/11/13
02/04/25
549
KhAl в сообщении #1607748 писал(а):
$s(1) < s(2) < ... < s(k) < n-1$

Это как посмотреть. Если $s(1)>0$, то $s(k)<n$ и в последней сумме будет как и у вас $\sum_{i=1}^k C_{s(i)-1}^i$. Если же $s(1)\geqslant0$, то $s(k)<(n-1)$ и тогда в последней сумме должно быть $\sum_{i=1}^k C_{s(i)}^i$.

Если посмотреть историю A243571, то там видно, что один из самых активных редакторов энциклопедии Michel Marcus еще в процессе рассмотрения правки в разделе CROSSREFS спросил, мол
Цитата:
then in example : The least and greatest numbers in row n are A083329(n-1) and ... is wrong ??

Но проверить видимо поленился и оставил все как есть. Так что это потом надо будет кому-нибудь исправить.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение03.09.2023, 10:36 


23/02/12
3370
kthxbye в сообщении #1607653 писал(а):
К сожалению я плохо знаком с нотацией $O$ чтобы оценить сложность своего решения и выставить минимальные требования.
Вы уже это пишите не первый раз. Пора бы освоить эту тему. Тем более, если ее используете.
kthxbye в сообщении #1607707 писал(а):
Просто спрашивать - как-то скучновато, куда интереснее сначала ставить задачу или даже в какой-то мере бросать вызов.
Кому вызов? Другим? Так они решают задачу и считают за Вас сложность. Вызов себе? Но Вас это не стимулирует для получения новых знаний в математике.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение03.09.2023, 12:09 
Админ форума


02/02/19
2597
kthxbye в сообщении #1607707 писал(а):
Благодарю за совет! К сожалению в ПРР отвечают очень редко, а тут как-то больше активности.

На форуме иногда пишут о разнице ПРР и ОЗ, мол, дескать, пишите в ОЗ только если решение вам известно. Это как раз мой случай. Путь по которому мы приходим к решению - это уже отдельный вопрос. Его всегда можно уточнить у более подкованных в математике участников. Просто спрашивать - как-то скучновато, куда интереснее сначала ставить задачу или даже в какой-то мере бросать вызов.
 !  Если Вы хотите, чтобы Вам объяснили то, чего Вы не понимаете - $O$-нотацию, сложность Вашего решения или почему молоко белое, хотя трава зеленая - то это тема для ПРР. Кому Вы "бросаете вызов", размещая такие вопросы в ОЗ, известно только Вам. Замечание за использование олимпиадного раздела не по назначению.

 Профиль  
                  
 
 Posted automatically
Сообщение03.09.2023, 12:10 
Админ форума


02/02/19
2597
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: см. выше.

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение03.09.2023, 22:08 


13/01/23
307
kthxbye в сообщении #1607694 писал(а):
А вот чтобы просто проверить - есть как минимум одно элегантное решение.
Просто из интереса — вы его придумали?

-- 03.09.2023, 22:16 --

Обнаружил. Возьмём в n-й строке с конца столько чётных чисел, сколько можно взять, не затронув нечётные. (Эмпирически) их число образует очень замечательную последовательность. (как и сами эти числа). С нечётными вначале происходит то же самое.

-- 03.09.2023, 23:03 --

kthxbye извините, не могу написать программу. Мне стало любопытно посмотреть на следующий треугольник:
k-я строка длины $F_k$: пусть b1(n) — n-е с конца число k-й строки A243571, а b2(n) — n+1-е с конца число k+1-й строки A243571. Тогда n-м числом в строке будет b2(n) - b1(n). Пришлёте сюда, скажем, 11 строк (в оффтоп, чтоб не пугали)?

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение03.09.2023, 23:15 


13/01/23
307
Хотя уже не надо...

-- 04.09.2023, 00:03 --

Пусть число $q \geq 4$ находится в какой-нибудь строке, а $b(q)$ — номер (начиная с $1$), который оно занимает в этой строке. Тогда из формулы для $N(q)$ следует
$$b(q) = \begin{cases}
b(\frac{q}{2}) + b(\frac{q+2}{2}) - 1 ,&\text{если $q \equiv 0 \pmod 4$;}\\
b(\frac{q-1}{2}) + b(\frac{q+1}{2}) - 1,&\text{если $q \equiv 1 \pmod 4$;}\\
b(\frac{q}{2}) + b(\frac{q-2}{2}),&\text{если $q \equiv 2 \pmod 4$;}\\
b(\frac{q-1}{2}) + b(\frac{q-3}{2}),&\text{если $q \equiv 3 \pmod 4$.}
\end{cases}$$ (на $q$ обязательно смотреть как на число в двоичной системе счисления, иначе ничего не понятно)

 Профиль  
                  
 
 Re: Проверка что q это p-ый член посл.-ти
Сообщение04.09.2023, 00:39 


13/01/23
307
KhAl в сообщении #1607872 писал(а):
$$b(q) = \begin{cases}
b(\frac{q}{2}) + b(\frac{q+2}{2}) - 1 ,&\text{если $q \equiv 0 \pmod 4$;}\\
b(\frac{q-1}{2}) + b(\frac{q+1}{2}) - 1,&\text{если $q \equiv 1 \pmod 4$;}\\
b(\frac{q}{2}) + b(\frac{q-2}{2}),&\text{если $q \equiv 2 \pmod 4$;}\\
b(\frac{q-1}{2}) + b(\frac{q-3}{2}),&\text{если $q \equiv 3 \pmod 4$.}
\end{cases}$$
Ошибся, формула рабоает только для $q \equiv_4 2$ и $q \equiv_4 1$. Для остальных пока не знаю, как быть.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

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



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

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


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

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