Skip to main content
5 of 6
edited tags
user avatar
user avatar

Strange (or stupid) arithmetic derivation

Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to any integer multilpe times, it will eventually get into a finite cycle?) Is there a constant $K$ such that any integer will fall into a cycle after $K$ steps?

I think that the answer to the first question is yes, but to the second no. We tested the first $10000$ integers and every integer fell into a cycle after at most $6$ steps.

Edit: @MarkSapir proved that the answer to the second question is no. His proof raises the (third) question: How long can such a cycle be?

Edit2: István Kovács pointed out that there is a nice formula for $f(n)$ using the 'number of divisors' function: $$ f(n):= d \left( \frac{n}{ \prod_{i=1}^{n}p_i } \right) \frac{n}{ \prod_{i=1}^{n}p_i } $$ from which it fillows that for any $\varepsilon >0 , \quad f(n)=o(n^{1+\varepsilon})$.

Edit3: I proposed two questions (in retrospect, it was a minor mistake), one of them was answered. To appreciate this, i accept Mark Sapir's answer, and alter the original text by putting the unanswered stuff into parentheses. Making the answered one the main question.