Проверка что q это p-ый член посл.-ти

[kthxbye]

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

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

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

[KhAl]

Можно по $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)$ считается)

[kthxbye]

$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$. Последняя операция может оказаться относительно дорогой. А вот чтобы просто проверить - есть как минимум одно элегантное решение. К сожалению я не до конца понимаю как оно работает, но возможно после его публикации кто-нибудь сможет мне это объяснить.

[vicvolf]

kthxbye в сообщении #1607653 писал(а):

К сожалению я плохо знаком с нотацией $O$ чтобы оценить сложность своего решения и выставить минимальные требования.

kthxbye в сообщении #1607694 писал(а):

К сожалению я не до конца понимаю как оно работает, но возможно после его публикации кто-нибудь сможет мне это объяснить.

Может лучше помещать такие темы в разделе ПРР.

[kthxbye]

vicvolf в сообщении #1607705 писал(а):

Может лучше помещать такие темы в разделе ПРР.

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

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

[KhAl]

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$

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

[kthxbye]

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) уже заняты, а одобрят их только где-то через месяц или два.

[KhAl]

Цитата:

В конце концов, до меня начало доходить что вы берете не все номера единиц со старшим битом включительно, а только те, что идут до него

ой, это я сглупил, хотел написать $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)

[kthxbye]

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 ??

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

[vicvolf]

kthxbye в сообщении #1607653 писал(а):

К сожалению я плохо знаком с нотацией $O$ чтобы оценить сложность своего решения и выставить минимальные требования.

Вы уже это пишите не первый раз. Пора бы освоить эту тему. Тем более, если ее используете.

kthxbye в сообщении #1607707 писал(а):

Просто спрашивать - как-то скучновато, куда интереснее сначала ставить задачу или даже в какой-то мере бросать вызов.

Кому вызов? Другим? Так они решают задачу и считают за Вас сложность. Вызов себе? Но Вас это не стимулирует для получения новых знаний в математике.

[Ende]

kthxbye в сообщении #1607707 писал(а):

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

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

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

[Ende]

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

[KhAl]

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 строк (в оффтоп, чтоб не пугали)?

[KhAl]

Хотя уже не надо...

-- 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$ обязательно смотреть как на число в двоичной системе счисления, иначе ничего не понятно)

[KhAl]

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$. Для остальных пока не знаю, как быть.