Let $k>1$ be an integer. A function $f:\mathbb{N^*}\to\mathbb{N^*}$ is called $k$-tastrophic when for every integer $n>0$, we have $f_k(n)=n^k$ where $f_k$ is the $k$-th iteration of $f$: \[f_k(n)=\underbrace{f\circ f\circ\cdots \circ f}_{k\text{ times}}(n)\] For which $k$ does there exist a $k$-tastrophic function?
Problem
Source: French TST 2012
Tags: function, algebra unsolved, algebra
03.08.2012 08:17
WakeUp wrote: Let $k>1$ be an integer. A function $f:\mathbb{N^*}\to\mathbb{N^*}$ is called $k$-tastrophic when for every integer $n>0$, we have $f_k(n)=n^k$ where $f_k$ is the $k$-th iteration of $f$: \[f_k(n)=\underbrace{f\circ f\circ\cdots \circ f}_{k\text{ times}}(n)\] For which $k$ does there exist a $k$-tastrophic function? I suppose that $N^*=\mathbb N$ is the set of all positive integers. There exists a k-tastrophic function for any integer $k>1$. Unlike the funny claim in previous post, here is the proof : Let integer $k>1$ Let $v_k(n)$ be the greatest power of $k$ which divides $n$ Let $A$ be the set of all positive integers which are not divisible by $k$. Since $k>1$, $A$ is an infinite set and so we may split it in $k$ equinumerous subsets $A_1,A_2,...A_k$ Let $\{g_i(n)\}_{i=1}^{k-1}$ a set of bijections from $A_i\to A_{i+1}$ Let $h(n)$ bijection from $A_k\to A_1$ defined as $h(n)=g_{1}^{-1}(g_{2}^{-1}(...g_{k-1}^{-1}(n)...))$ Let $g(x)$ from $\mathbb N\to\mathbb N$ defined as : If $\frac n{k^{v_k(n)}}\in A_i$ with $i\ne k$, then $g(n)=k^{v_k(n)}g_i\left (\frac n{k^{v_k(n)}}\right )$ If $\frac n{k^{v_k(n)}}\in A_k$, then $g(n)=k^{v_k(n)+1}h\left (\frac n{k^{v_k(n)}}\right )$ Then $g_k(n)=kn$ And then just define $f(n)$ as : $f(1)=1$ For $n>1$ : $f(n)=$ $f\left(\prod p_i^{n_i}\right)=\prod p_i^{g(n_i)}$ where $\prod p_i^{n_i}$ is the prime decomposition of $n$ Q.E.D.