F:N-->N , and its "iterates" F(F(F(...)))....

[sasa]

Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_j^{\alpha_j}$ be the decomposition in prime factors of a positive integer $n$ .
If ${\mathbf q}\in {\mathbb N}^* :=\{1,2,..\} $define $F: {\mathbb N}^* \to {\mathbb N}^* $ by $ \begin{array}{|c|} \hline F(n)=F(n,{\mathbf q})=1+\sum\limits_{\nu=1}^{j}\alpha_{\nu}^{{\mathbf q}}p_{\nu} \\ \hline \end{array}\; . $


Consider the "iterates " of $F$ that is $F^2=F\circ F ,\; F^k (x)= (\underbrace{F\circ F \circ \cdots \circ F}_{k-\mbox{{\tiny times}}})(x) \; ,\; k\in {\mathbb N}^* $

i) If ${\mathbf q}=1$ prove (or verify by means of a computer) that for each integer $n\; ,\; n>6 ,$
there exists ${\mathbf k_0}={\mathbf k_0(n)}\in {\mathbb N}^* $ such that $F^{\mathbf k_0}(n)={\mathbf 7} \; .$

ii) What about case ${\mathbf q\ge 2}$ ?

[Руст]

Если n и m взаимно просты, то F(nm,q)=F(n,q)+F(m,q)-1. Если n=p^k степень простого числа p, то F(n,q)=1+p*k^q<=n, если k>1 и p>2^q. F(p)=p+1. Поэтому, если n>(2^q+1)^2, то вторая итерация F(F(n,q),q)<n. Соответственно достаточно проверить как ведуть себя итерации при этом ограничении. Траектории итераций могут стабилизироваться или образовать циклы.

[juna]

Непонятно, что имелось ввиду.
Пусть n=90, q=3, 90>81.
Находим F(F(90,3),3)=F(32,3)=251<90 – ложь.
Допустим имелось ввиду n<(2^q+1)^2.
Пусть n=69, q=3 69<81.
Находим F(F(69,3),3)=F(27,3)=82<69 – ложь
Таким образом, на второй итерации отображение не обязано сжиматься.

Цитата:

если n>(2^q+1)^2, то вторая итерация F(F(n,q),q)<n

[Руст]

Да, допустил неточность, заключающийся в распространении оценки минимального простого числа (максимальное возможное значение для второй степени, при этом хотя оценки для более высоких степеней и дают меньшие возможные простые значения, но их степени могут превышать вторую степень полученную ограничением через вторые степени) со второй степени на большие степени. Поэтому эту оценку надо заменить оценкой $max_{k,p}( p^k|p^k\le 1+k^qp)$. Ясно, что это конечное число. А здесь главное доказать, что через какое то число шагов получим некоторый ограниченный некоторым числом член последовательности. Итерирую в дальнейшем мы можем вылазти за границу, но через какое то количество шагов опять попадём в пределы эти границы. Поэтому проверки (итерации с начальными значениями в пределах этой границы) содержат часть любой траектории.

[juna]

Пусть q=1, G(N)=F(N,1) тогда для всех N<6 G(N)=N+1, G(6)=6 – неподвижная точка отображения. Если мы попадем в полосу до шести, то застрянем на неподвижной точке. Далее G(7)=8, G(8)=7 – цикл, по которому будем двигаться, если не попадем в полосу до шести. Заметим теперь, что для любого составного D имеем G(D)<D, действительно произведение чисел всегда больше их суммы, а степень еще больше усугубляет это неравенство, и только для простого D всегда имеем G(D)=D+1, но если D – простое, тогда D+1 – составное и поэтому G(G(D))<G(D). Таким образом, наше отображение всегда будет сжиматься и нужно лишь доказать, что при N>6 мы никогда не попадем в полосу до шести. Но ведь из условия требуется доказать теорему для всех N>6, а в полосу до шести мы попадаем только если 1+ap<=6 т.е. ap<=5, что не возможно для N>6. ч.т.д.
Случай с q<>1 много сложнее и цикл, в который мы там попадаем тоже намного сложнее. Но, следует заметить, что траектория всегда для любого числа и при любом q будет вырождаться в цикл, и поэтому поиск верхних, нижних ограничений на q неуместен.

В связи с этим хотелось бы предложить для форумчан исследовать следующее предложение: В n-мерном пространстве задано n возрастающих функций (возможно даже дискретных). Доказать, что найдется такое K, что отображение-суперпозиция, выполненное K раз – для всех i=1..n вида: f1(x1,x2,..xn), f2(x1,x2,..,xn)..fn(x1,x2..xn) -> f1(f1(x1,x2,..xn), f2(x1,x2,..,xn),.. fn(x1,x2..xn)), f2(f1(x1,x2,..xn), f2(x1,x2,..,xn),.. fn(x1,x2..xn)).. fn(f1(x1,x2,..xn), f2(x1,x2,..,xn),.. fn(x1,x2..xn))-> и т.д. выродится в неподвижную точку ли цикл. Тут же сразу возникает вопрос, а что будет, если некоторые функции будут убывающими.

[Руст]

Если растущие никакого цикла, разве что назвать бесконечную точку стационарной точкой. А как туда будет стремится зависит от вида функции f(x) (я не расписываю функцию и аргумент как первокурсник) аргумент и значения принадлежат некоторому множеству X, например Z^n.

[juna]

Цитата:

Если растущие никакого цикла, разве что назвать бесконечную точку стационарной точкой. А как туда будет стремится зависит от вида функции f(x) (я не расписываю функцию и аргумент как первокурсник) аргумент и значения принадлежат некоторому множеству X, например Z^n.

Вас легко опровергнуть - возьмите, например, среднее геометрическое и среднее арифметическое, подставляйте одно в другое и будите сходиться к неподвижной точке - значению некоторого эллиптического интеграла.

[Руст]

А это не итерация растущей функции. Вообще то под растущей я подразумевал, то что увеличивает некоторую норму |f(x)|>|x|.

[juna]

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

[Руст]

Но если значения натуральные и строго растущие, то это как правило (за исключением x-a) приводит к росту нормы, и не зацикливает.

[juna]

Здесь вы правы. Немного поправлюсь - перед итерациями нормируем наши функции на отрезок [0,1].

[Co_Gito]

ii) is of course not true. Take n=7 and q=2. Then, you get the values of
F^k(7,2) for k=1,...,6 as follows:
8, 19, 20, 14, 10, 8 .... periodic function that never hits 7.

Conjecture: For all q\geq 2 and n>6, there is no k_0(n) such that F^{k_0}(n)=7.

[juna]

Я и не утверждал, что во втором случае для любого числа должна появиться 7, я лишь утверждал, что циклы обязательно появятся.

[Руст]

Речь не идёт, что сохраняться циклы с младших q. Просто растут значения N(q) куда обязательно возвращаются все последовательности. Как я уже писал они могут выйти за пределы этого, но опять снова попадут. Поэтому обязательно образуются циклы (возможно длины 1, т.е. стационарные).

[Co_Gito]

How about the Conjecture I've posted? Any comments?

I've read your way of argumenting the solution. However, I felt that the original post asked for the definitive answer.