Weird arithmetics with prime numbers...

Question

Hello here is a problem with which I struggle quite a bit: For any integer $n \geq 2$, with prime factor decomposition $n = p_1^{α_1}\times p_2^{α_2}\times ... p_k^{a_k}$, let $f(n) = α_1^{p_1}\times α_2^{p_2}\times ... α_k^{p_k}$. Which means for instance that, since $424242 = 2^1\times 3^2\times 7^2 \times 13^{1} \times 37^{1}$, we have $f(424242) = 1^2 \times 2^3 \times 2^7 \times 1^{13} \times 1^{37} = 2^{10} = 1024$. And then, $f(1024) = 10^2 = 100$. Doing it one more time, with $100 = 2^2\times 5^2$, $f(100) = 2^2\times 2^5 = 128$. Let $f^i$ denote the composition of $f$ $i$ times with itself (meaning that $f^2(424 242) = 100$, and then $f^3(424 242) = 128$).

The following three questions give me a lot of trouble:

1. Give an example of an integer $n$ such that the sequence $(f^i(n))$ is periodic with period $2$ (but not constant). Characterize such integers.
2. Solve: $f(n) = 1$, then $f(n) = 2$ and finally $f(n)=4$.
3. (the one giving me the most trouble:) Let $(a_1,a_2, ... , a_k)$ k integers greater than or equal to $2$ and $(b_1,b_2,...,b_k)$ such that $b_k \in \mathbb{N}$ (with the definition that $\mathbb{N}$ contains $0$). Show that: $$\sum_{i=1}^k a_i b_i \leq \prod_{i=1}^k a_i ^{b_i}$$.

I would appreciate any pointers, especially concerning the third one. I'll keep searching on my end, but arithmetic is not my strong suit.

Thank you in advance.

Answer 1

1. We can give an example by considering prime-powers $p^a$ with $f^2(p^a) = p^a$. Write $a = p_1^{b_1} \dots p_m^{b_m}$. Then \begin{align} f(p^a) = a^p = p_1^{b_1p} \dots p_m^{b_mp} \end{align} and we must have \begin{align} f^2(p^a) = p^{p_1 + \dots + p_m}b_1^{p_1} \dots b_m^{p_m} = p^a. \end{align} By unique factorisation, $b_j = p^{c_j}$ for some $c_j$ for each $j \in \{1, \dots, m\}$. Then \begin{align} p_1(1 + c_1) + \dots + p_m(1 + c_m) = a = p_1^{(p^{c_1})} \dots p_m^{(p^{c_m})}. \quad (1) \end{align} Conversely, if $p_1, \dots, p_m, c_1, \dots, c_m$ satisfy $(1)$, then $f^2(p^a) = p^a$ with $f(p^a) \neq p^a$ (if we have equality then we force $p = 1$). This at least characterises prime-powers having period $2$ and provides a sufficient condition for a general integer to have period $2$ (take a product of prime powers $p^a$ satisfying $(1)$).
2. Write $n = p_1^{a_1} \dots p_m^{a_m}$, then $f(n) = a_1^{p_1} \dots a_m^{p_m}$. Then $f(n) = 1$ if and only if all $a_j = 1$, i.e., if and only if $n$ is squarefree. For $f(n) = 2$, we have one $a_j = 2$ and all other $a_i = 1$ ($i \neq j$). Then $f(n) = 2$ if and only if $n = p^2m$ where $p$ is prime and $m$ is squarefree. For $f(n) = 4$, we can have one $a_j = 4$ and all other $a_i = 1$ or some $a_j = a_k = 2$ and all other $a_i = 1$. Then $f(n) = 4$ if and only if $n = p^4m$ or $p^2q^2m$ where $p, q$ are prime and $m$ is squarefree.
3. We can argue by induction. For powers, we have $ab \leq a^b$. If the inequality holds for $k - 1$ integers, then \begin{align} \prod_{i = 1}^k a_i^{b_i} &= a_k^{b_k} \prod_{i = 1}^{k - 1}a_i^{b_i} \\ &\geq a_k^{b_k} \sum_{i = 1}^{k - 1} a_ib_i \\ &\geq (1 + a_kb_k)\sum_{i = 1}^{k - 1} a_i b_i \\ &= \sum_{i = 1}^{k - 1} a_i b_i + a_kb_k\sum_{i = 1}^{k - 1} a_i b_i \\ &\geq \sum_{i = 1}^k a_ib_i. \end{align} Here we have used the slightly stronger inequality $a_k^{b_k} \geq 1 + a_kb_k$, true as long as $b_k \geq 3$. If $b_k = 1$, then (actually the first inequality below is only true if some $b_j \neq 0$ or $k \geq 3$, but the cases $k \in \{1, 2\}$ and all $b_j = 0$ can easily be dealt with separately) \begin{align} \sum_{i = 1}^{k - 1} a_i^{b_i} \geq 2 \geq \frac{a_k}{a_k - 1} \quad (2) \end{align} gives \begin{align} a_k\prod_{i = 1}^{k - 1}a_i^{b_i} \geq a_k\sum_{i = 1}^{k - 1}a_ib_i \geq a_k + \sum_{i = 1}^{k - 1} a_ib_i. \end{align} Finally when $b_k = 2$, just use $4/3 \geq a_k^2/(a_k^2 - 1)$ in a similar inequality to $(2)$ and rearrange.

Please let me know if there are any mistakes (there probably are). I know that my answer to 1. does not give a complete characterisation. I will think more about it and edit my answer later, perhaps. I might also clean up the proof of 3.

Edit: I have a necessary and sufficient condition for $n$ to have period $2$, but it's not that nice. Let $v_p$ be the $p$-adic valuation so that $v_p(n) = m$ if and only if $p^m$ divides $n$ and $p^{m + 1}$ doesn't. \begin{align} f(n) = \prod_p f(p^{v_p(n)}) = \prod_p v_p(n)^p = \prod_p (\prod_q q^{(v_qv_p)(n)})^p = \prod_q q^{\sum_p p(v_qv_p)(n)} \\ f^2(n) = \prod_q \Big(\sum_p p(v_qv_p)(n)\Big)^q = \prod_q \Big(\prod_r r^{v_r(\sum_p p(v_qv_p)(n))}\Big)^q = \prod_r r^{\sum_q qv_r(\sum_p p(v_qv_p)(n))}. \end{align} By unique factorisation, $n$ has period $2$ if and only if it satisfies the equation \begin{align} v_r(n) = \sum_q qv_r(\sum_p p(v_qv_p)(n)) \end{align} for all primes $r$. I think that there will not be a nice necessary and sufficient condition because we cannot calculate the $r$-adic valuation of the sum over $p$ in any straight-forward way. I would be interested in any developments though.