Рекуррентный пол

[maxal]

Определим последовательность рекуррентно:

$$a(n) = \begin{cases} 1, & \mbox{if}\ n=1;\\ \left\lfloor \frac{n}{a\left(\lfloor n/2\rfloor\right)} \right\rfloor, & \mbox{if}\ n>1.\end{cases}$$

Докажите, что для любого $m>1$

$$ \min \{n\colon a(n)=m\} = m\cdot 2^{\lfloor \log_2(m)\rfloor-1}.$$

[Руст]

Очевидно проверяется, что если $a(n)|n$, то $a(2n)|2n$.
Так как $2\le a(n)\le n, n>1$ (точнее по индукции $2^k\le a(n)<2^{k+1},k=[\log_2(n)/2]$) то для нечетного $m>3$ $a(m)\not |m$. Соответственно надо искать $n=2^km$ для того, чтобы $m|a(n)$. Степень k находим по индукции как число $k=[\log_2(m)]-1, m>1$.

Тогда находится и для четных $m=m_1*2^{k}$ по той же формуле $n=n_1(m_1)*2^{k}.$

[maxal]

Руст в сообщении #419068 писал(а):

Соответственно надо искать $n=2^km$ для того, чтобы $m|a(n)$.

Пока что ниоткуда не следует, что минимальное $n$ должно иметь вид $2^k m$. И вообще почему $m$ должно быть делителем $n$?

[venco]

Вообще-то, легко доказать, что

$$a(n) = \begin{cases} \left\lfloor\frac n {2^k}\right\rfloor, & \mbox{if}\ \lfloor \log_2 n \rfloor = 2k+1;\\ 2^k, & \mbox{if}\ \lfloor \log_2 n \rfloor = 2k.\end{cases}$$

[maxal]

Это другое дело.

[venco]

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

[maxal]

Задачка посложнее - найдите явную формулу для последовательности:

$$b(n) = \begin{cases} 1, & \mbox{if}\ n=1;\\ \left\lceil \frac{n}{b\left(\lceil n/2\rceil\right)} \right\rceil, & \mbox{if}\ n>1.\end{cases}$$