2 Keys Keyboard


Well, the following argument excerpted from this article is not strong enough. How can you make sure a split in three parts "pqk" is no better than spliting in two parts "pq"?
"Such a split never uses more moves: we use p+q moves when splitting, and pq moves previously. As p+q <= pq is equivalent to 1 <= (p1)(q1), which is true as long as p >= 2 and q >= 2."

@newtt If any g_i are composite, we showed that there exists a split such that it uses less moves. This proves that any optimal solution cannot have g_i composite. Any factorization g = p * q (regardless of whether p, q are prime, just as long as they are at least 2) is sufficient.