# Product of exponents of prime factorization

Let $p(n)$ be the product of the exponents of the prime factorization of $n$. For example, $$p(5184) = p(2^6 3^4) = 24 \;,$$ $$p(65536) = p(2^{16}) = 16 \;.$$ Define $P(n)$ as the number of iterations of $p(\;)$ to reduce $n$ to $1$. For example, $P(5184) = 3$ because $$p(5184)=24, \;p(24) = p(2^3 3^1) = 3, \;p(3)=1 \;;$$ and $P(65536)=4$ because $$p(65536) = 16, \;p(16)=p(2^4)=4, \;p(4)=p(2^2)=2, \; p(2)=1 \;.$$ Finally, define $m(k)$ to be the minimum value of $n$ such that $P(n) = k$.

What is $m(k)$?

For example, $m(1)=2$ and $m(2)=4$ and $m(3)=16$. Is $m(k)$ always $2$ to some power?

Update. Calvin Lin showed that $m(4)$ is not a power of $2$, and is at most $2^4 3^4$. Indeed I have verified (by search) that $m(4)=1296$.

-
Now also posted on MathOverflow. – Joseph O'Rourke Oct 1 '13 at 23:52
Will Jagy showed (on MO) that $m(5) = 2^9 3^6 5^4 7^3 11^2 =9681819840000 \approx 10^{13}$. – Joseph O'Rourke Oct 4 '13 at 11:36

No. Consider $m(4)$. If it was a power of 2, then it must be at least $2^{16}$. (Since if it's of the form $2^n$, then $n$ needs 3 iterations, and so $n \geq m(3) = 16$.)
But $p( 2^4 3^4) = 16$, so $m(k) \leq 2^4 \times 3^4 < 2^{16}$.
Nice! This makes $m(k)$ more interesting. :-) – Joseph O'Rourke Sep 28 '13 at 15:31
This suggests an approach to find $m(k)$. Take all the factorizations of $m(k-1)$ and search for the minimum. So for $m(4)$ we check $2^{16},2^83,2^43^4,2^43^25^2$ and find $2^43^4=1296$ as the minimum. It is not guaranteed. We could have $p(m(5)) \gt m(4)$ – Ross Millikan Sep 28 '13 at 16:11
@RossMillikan But there could be other possibilities, resulting from values where $P(n) = 3$. For example, IF (a big if, because it is not true) $P(27) = 3$, then we should use $2^3 3^3 5^3$. – Calvin Lin Sep 28 '13 at 16:20