Номер массива и позиция в нем (PARI)

[kthxbye]

Имеется массив состоящий из $k$ подмассивов. В каждом таком подмассиве по $m_k$ элементов. Каждое натуральное число встречается в массиве ровно по одному разу. Кол.-во подмассивов и элементов в них зависит также от некоторого значения $n$. Кроме того, в массиве совокупность всех элементов образует множество $\left\lbrace1,2,\cdots,n\right\rbrace$.

Необходимо какой-нибудь не слишком сложной функцией определять в каком из $k$ подмассивов находится некий выбранный элемент $i$ и какая у него позиция в этом подмассиве. Хотелось бы как-нибудь избежать повторных пробегов по всем элементам каждого из подмассивов, но, в принципе, устроит и такой вариант.

[StepV]

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

Необходимо какой-нибудь не слишком сложной функцией определять в каком из $k$ подмассивов находится некий выбранный элемент $i$ и какая у него позиция в этом подмассиве.

В программировании часто возникают задачи, в которых надо использовать один из подходов: решение за минимальное время (т.е. фактически, не надо жалеть память), либо решение с минимальным использованием объема памяти (т.е. без лимита процессорного времени) .
Похoже у вас первый случай. В этом случае вам необходимо выполнить следующие действия:
- создать массив кортежей, полями у кортежа будут: $n, i_k, N_m_k $, где n - ваше натуральное число, $i_k$-индекс подмассива, $N_m_k$- индекс по подмассиву;
- создать функцию, которая по $n$ будет выдавать вам из этого кортежа $i_k, N_m_k $ (об этой функции и стоял вопрос);
- написать функцию, которая в начале работы программы формирует этот массив кортежей по заданному массиву подмассивов или же функцию, которая совместно заполняет основной массив числами и одновременно формирует записи в массиве кортежей.
P.S. Если n - очень большое, но могут быть дыры в последовательности, то вместо массива можно формировать список с соответствующими операциями по списку.

[wrest]

Ну раз у вас число это ключ (встречется не больше одного раза), то мне кажется вам надо вывернуть массивы-подмассивы в плоский список. Например в карту.

Создаем пустую карту
? M=Map()

Нполняем карту значениями.
В строках ниже добавляем три числа 1,2 и 4 и значения индексов массив-подмассив (для числа 1 это 2 и 3; для числа 2 это 3 и 5)
? mapput(M,1,[2,3])
? mapput(M,2,[3,5])
? mapput(M,4,[5,8])

Создаём пустую переменную -- массив из двух значений. Туда будем получать массив-подмассив если число найдётся.
? v=[[],[]]

Теперь ищем есть ли в карте число 1. Если есть, то передаём в переменную v и печатаем номер массива i и позицию в нём j
? k=1;if(mapisdefined(M,k,&v),print("For n=",k," i=",v[1]," j=",v[2]),print("n=",k," does not exist"))
For n=1 i=2 j=3

Ищем есть ли в карте число 7. Его там нет - печатаем, что его нет.
? k=7;if(mapisdefined(M,k,&v),print("For k=",k," i=",v[1]," j=",v[2]),print("n=",k," does not exist"))
n=7 does not exist

Или одно и тоже число может входить в разные массивы-подмассивы и вам надо выяснить в какие?

(Оффтоп)

Я традиционно не понял что вы хотите. Зарекался ведь...

[kthxbye]

wrest, благодарю за комментарий! Чуть позже буду разбираться.

Нет, число не может входить в разные подмассивы, т.к. встречается не более одного раза.

Для чего мне все это нужно? Вот мое решение:

r=(1+sqrt(5))/2 
\\ в поздней версии можно также использовать r=quadgen(5) 
seq_upto(nMax)={my(v1, v2, v3, v4, v5); nMax++; 
v1=vector(nMax, i, 0); v1[1]=1; for(i=1, nMax-1, v1[i+1]=v1[i\r+1]+1); 
v2=vector(nMax, i, 0); v2[1]=1; for(i=2, nMax, v2[i]=v1[i]-v1[i-1]); 
v3=vector(v1[nMax]\2,i,0); v3[1]=[2,4]; 
for(i=2, v1[nMax]\2, v3[i]=[v3[i-1][1]+fibonacci(2*i),v3[i-1][2]+fibonacci(2*i+1)]); my(j=2, A=0, B=0); 
until(B>=nMax, A=if(j==2,6,B); v3[1]=concat(v3[1],A); j++; B=if(v2[v3[1][j]+1],v3[1][j]+fibonacci(v1[j])+1,v3[1][j]+1)); 
for(i=2,v1[nMax]\2, my(j=2, A=0, B=0); until(B>=nMax, A=if(j==2,v3[i-1][3]+fibonacci(2*i+2),B); v3[i]=concat(v3[i],A); j++; B=v3[i-1][j+1]+fibonacci(v1[j+1]+2*i-1))); 
v4=vector(nMax-1, i, 0); 
for(i=1, nMax-1, my(A, B, j=1); until(A>0 || v2[i], A=sum(k=1,#v3[j],j*(v3[j][k]==i)); B=sum(k=1,#v3[j],k*(v3[j][k]==i)); j++); v4[i]=if(v2[i],[(v1[i]+1)\2,1-v1[i]%2],[A,B])); 
v5=vector(nMax-1,i,0); 
for(i=1, nMax-1, v5[i]=if(v4[i][2]==0,2^(v4[i][1]-1)*(2^v4[i][1]+1),2^(v4[i][1]-1)*(v5[v4[i][2]]+2^(v1[v4[i][2]]+v4[i][1])))); v5}

Решение реализовано в цикле после того, как задан массив v4.

Что генерирует в конечном счете программа? Вот эту последовательность: https://oeis.org/draft/A353654.

Программа связана со следующими формулами:

Since {A000045(2n)} UNION {A133512(n) + 1} UNION {A133512(n) + A000045(A072649(n) + 3) + 1} UNION {A133512(n) + A000045(A072649(n) + 3) + A000045(A072649(n) + 5) + 1} UNION ... UNION {A133512(n) + 1 + Sum_{k=1..m} A000045(A072649(n) + 2k + 1)} UNION ... etc. is essentially natural numbers, we can generate sequence by the following:
a(A000045(2n)) = 2^(n-1)*(2^n + 1) for n > 0.
a(A133512(n) + 1) = a(n) + 2^(A072649(n) + 1) for n > 0.
a(A133512(n) + A000045(A072649(n) + 3) + 1) = 2*(a(n) + 2^(A072649(n) + 2)) for n > 0.
a(A133512(n) + A000045(A072649(n) + 3) + A000045(A072649(n) + 5) + 1) = 2^2*(a(n) + 2^(A072649(n) + 3)) for n > 0.
a(A133512(n) + 1 + Sum_{k=1..m} A000045(A072649(n) + 2k + 1)) = 2^m*(a(n) + 2^(A072649(n) + m + 1)) for n > 0.

Они выводятся из определения, которое предложил некий Kevin Ryde. Определение такое: если $x$ - член последовательности, то

$$1[x], 10[x]0, 100[x]00, \cdots, 1\underbrace{0\cdots 0}_{k}[x]\underbrace{0\cdots 0}_{k}, \cdots$$

и т.д. также являются членами этой последовательности, где $[x]$ это двоичная запись $x$. Очевидно, что результирующие числа также записаны в двоичной записи. Здесь $x$ может быть также единицей (вероятно это значение будет включено в последовательность как $a(0)=1$).

В программе массив v1 это A072649, массив v2 это A010056; массив v3 это основной массив из первого поста. Здесь подмассив v3[1] это A133512+1, подмассив v3[2] это подмассив v3[1], увеличенный на A000045(A072649 + 3); подмассив v3[3] это подмассив v3[2], увеличенный на A000045(A072649 + 5); и т.д., т.е. подмассив v3[k] это подмассив v3[k-1], увеличенный на A000045(A072649 + 2k - 1).

Для удобства массивы генерируются под наши нужды, т.е. следующий после максимального элемент в каждом из подмассивов всегда $\geqslant$ nMax.

Вместо v5 можно выводить в конце другие массивы, чтобы посмотреть на то, что именно в них содержится.

К сожалению программа почему-то не работает для nMax $=\operatorname{Fibonacci}(2n+1)+k$, где $\operatorname{Fibonacci}(0)=0$, $\operatorname{Fibonacci}(1)=1$ и $k\in\left\lbrace-1, 0 , 1\right\rbrace$.