É, eu não sei como faz pra editar a parte de cima, então eu vo colocar aqui mesmo.
Acho que não há dúvidas no enunciado, ele está bem claro. Eu não vou descrever o meu algoritmo aqui, vou colocar a coisa mais ou menos do jeito que eu pensei, ou seja, a demostração de que todo número admite uma decomposição em uma soma de fatores primos entre si da forma $2^a3^b$. A demonstração é por indução e a partir dela é fácil conseguir um algoritmo recursivo.
Os casos base $n=0,1$, certamente admitem uma decomposição desejada, respectivamente vazia e $2^03^0$.
Suponha então, que para todo $i < n$ existe uma decomposição. Aqui temos dois casos,
- $n \equiv 0 \pmod{2}$ Neste caso, basta tomar uma decomposição para $\frac{n}{2}$ (usando a nossa hipótese de indução) e multiplicar cada um de seus termos por 2. É fácil ver que esta é uma decomposição válida para $n$, pois os termos continuam primos entre si após multiplicarmos todos eles por $2$.
- $n \equiv 1 \pmod{2}$ Neste caso, seja $k$ o maior número tal que $3^k \le n$. Considere $n - 3^k$, é claro que este número é par ($n$ e $3^k$ são ímpares), assim considere uma decomposição para $\frac{n - 3^k}{2}$ e multiplique cada termo por $2$ como no caso anterior. Chame esta decomposição para $n - 3^k$ de $d_{1}$ e acrescente o termo $3^k$. Vamos provar que esta é uma decomposição válida para $n$, veja que $3^k$ não divide nenhum termo de $d_{1}$, pois $k$ é maior do que qualquer expoente de $3$ de cada termo de $d_{1}$ ($k$ é o maior número tal que $3^k \le n$). Agora, nenhum termo de $d_{1}$ divide $3^k$, pois todos eles são pares. Portanto, $d_{1}$ mais o termo $3^k$ é uma decomposição válida para $n$.
Logo, para todo $n$ existe (pelo menos) uma decomposição em uma soma de fatores primos entre si da forma $2^a3^b$.