Инъективная функция.

[Руст]

Приведите пример функции f(n) из N в N, что для каждого натурального числа n существует число k(n), что k(n) итерация функции $f^{k(n)}(n)=2n, (f^2(x)=f(f(x)),f^{l+1}(x)=f(f^l(x))).$ Причём k(n)>10n для большинства (в каждом конечном отрезке) n .

[juna]

Не совсем понятно, что Вы имеете в виду. Возьмем $f(n)=2n$ получаем искомое на первой итерации. Или требование

Цитата:

Причём k(n)>10n для большинства (в каждом конечном отрезке) n .

является принципиальным, тогда не понятно словосочетание "для большинства". Поясните, пожалуйста.

[Руст]

Это значит, что число тех n<N>10n ,больше N/2. Можно сделать так же, чтобы отношение тех, для которых k(n) не превосходит 10n к тем, для которых больше 10n стремилось к нулю с ростом N.
Маленькая подсказка. Можно выбрать такую функцию f(n), чтобы f(n)<=3n.

[nworm]

Наверное, надо примерно так определять.
$f(1)=1001$
$f(1001)=999$
$f(999)=997$
$\ldots $
$f(3)=2$
$f(2)=2^{BIG}+1$
$f(2^{BIG}+1)=2^{BIG}-1$
$\ldots $
$f(1003)=4$
$f(4)=4^{BIG}+1$
$\ldots $
Тогда числа будут удваиваться ой как не скоро.

[Руст]

nworm писал(а):

Наверное, надо примерно так определять.
$f(1)=1001$
$f(1001)=999$
$f(999)=997$
$\ldots $
$f(3)=2$
$f(2)=2^{BIG}+1$
$f(2^{BIG}+1)=2^{BIG}-1$
$\ldots $
$f(1003)=4$
$f(4)=4^{BIG}+1$
$\ldots $
Тогда числа будут удваиваться ой как не скоро.

Я не понял многоточия. Например, какая итерация от функции при аргументе 1001 даст значение 2002.

[nworm]

Напишу подлиннее
$f(1001)=999$
$f(999)=997$
$f(997)=995$
$f(995)=993$
$f(993)=991$
$\ldots$
$f(9)=7$
$f(7)=5$
$f(5)=3$
$f(3)=2$
Смысл в том, что чётные числа пропускаются. Число 2002 будет достигнуто только после применения
$f(1000)=1000^{BIG}+1$
$f(1000^{BIG}+1)=1000^{BIG}-1$
$f(1000^{BIG}-1)=1000^{BIG}-3$
$f(1000^{BIG}-3)=1000^{BIG}-5$
$f(1000^{BIG}-5)=1000^{BIG}-7$
$\ldots$
$f(999^{BIG}+9)=999^{BIG}+7$
$f(999^{BIG}+7)=999^{BIG}+5$
$f(999^{BIG}+5)=999^{BIG}+3$
$f(999^{BIG}+3)=2002$
Количество итераций зависит от числа $BIG$ и может быть достаточно большим.

[Руст]

Это является своеобразной перестановкой натурального ряда и работает, хотя появляются очень большие отношения f(n)/n. Несколько проще такой пример. Разлагаем N на произведение трёх множеств сопоставляя n числа x,y,m по формуле: $n=2^x3^ym,(m,6)=1,x\ge 0,y\ge 0.$ Для каждого m выберем k(n)=k(m) большое число например $k(m)=1000m^2^ и определим функцию

$$f(n)=3n,(y\to y+1 ), \ if \ k(n)\not |ord_3(3n), \ else \ f(n)=3^{1-k(n)}*n*2$$

.
При этом всё происходит только умножениями на 3 или умножением на 2 с делением на большую степень 3. Разные орбиты не пересекаются.

[juna]

Может быть этим условиям будет удовлетворять и следующая недобропорядочная функция:
$f(n)=n+(\frac{2}{p(n)})$, в скобках символ Лежандра, $p(n)$ - простое число под номером $n$.
Я эту идею не додумывал, поэтому строго не судите.

[Руст]

Сразу можно сказать, что это не годится.

[juna]

Идея была следующая: берем функцию следования $f(n)=n+1$, ее n-я итерация равна 2n. Для того, чтобы функция росла медленнее, нужно на некоторых итерациях единицу не прибавлять, а вычитать, но в среднем количество положительных единиц должно быть больше. Думаю, что идея работоспособна, нужно только подобрать функцию $g(n)=+(-)1$.

[Руст]

Для такой функции найдётся такое n, что f(n)=n+1,f(n+1)=n, а стало быть любая итерация от n либо n либо n+1.