Возвращение индексов членов подпоследовательности

[kthxbye]

Вопрос достаточно простой. Существует ли примитивная и общепринятая математическая функция, возвращающая индексы членов подпоследовательности в последовательности, подпоследовательностью которой она является?

Иначе говоря, имеем некоторую последовательность $a(n)$ и подпоследовательность $b(n)$. Положим, что $a(n)$ бесконечна, ровно как и $b(n)$. Пусть $a(c(n)) = b(n)$. Найти формулу (любую) для генерации $c(n)$ не представляется возможным. Можно ли вернуть последнюю примитивной функцией через $b(n)$?

[svv]

Пусть последовательность $(a_k)_{k=0}^{\infty}$ задаётся правилом $a_k = k\operatorname{mod} 10$:
$(a_k)=(0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,...)$

Пусть её подпоследовательность $(b_n)_{n=0}^{\infty}$ — это десятичное разложение $\pi$:
$(b_n)=(3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,...)$

Можете ли Вы сказать, какие именно элементы $a$ составили подпоследовательность $b$ ?

[kthxbye]

svv, замечательный пример! Исключения, естественно, возможны.

Интересен как минимум один случай, когда обе последовательности возрастающие.

[geomath]

А что, программу для компьютера нельзя считать "формулой"?

[svv]

kthxbye
Наверное, стоит «программу» построить так. Даны последовательности $(a_k)_{k=0}^{\infty}$ и $(b_n)_{n=0}^{\infty}$. Гарантируется, что $(b)$ — подпоследовательность $(a)$.
Сначала программа ищет наименьший индекс $k_0$ такой, что $a_{k_0}=b_0$.
Потом она ищет наименьший индекс $k_1>k_0$ такой, что $a_{k_1}=b_1$.
Потом она ищет наименьший индекс $k_2>k_1$ такой, что $a_{k_2}=b_2$.
И так далее.

Фишка тут в том, что, хотя в $(a)$ может быть много элементов $a_k$, равных заданному $b_n$, мы ничего не потеряем, выбрав из них тот, у которого наименьший индекс (больший индексов уже найденных предыдущих элементов). Если же мы первый подходящий элемент $a_k$ пропустим, понадеявшись, что дальше будут и другие, тоже равные $b_n$, подпоследовательность может и не сложиться!

Такой программе соответствует рекурсивная функция $f$:
$f(n)=\begin{cases}\min\{ k\in \mathbb N_0 \;| \; a_k=b_n \},&n=0\\\min\{ k\in \mathbb N_0 \;| \; a_k=b_n,\; k>f(n-1) \},&n>0\end{cases}$