¿De cuántas formas se puede escribir $N$ como una suma de términos en la forma $2^i3^j?

Question

Dado un entero positivo $N$, sea $f(N)$ el número de formas en que $N$ puede descomponerse como una suma de términos de la forma $2^i3^j$, donde cada término aparece a lo sumo una vez en la suma. Por ejemplo, $f(10) = 5$, ya que 10 se puede expresar como $3^2 + 1, 2^2 + 2 \cdot 3, 2^2 + 3 + 2 + 1, 2 \cdot 3 + 3 + 1,$ y $2^3 + 2$. Me gustaría tener cotas superiores e inferiores en $f(N)$ en términos de $N$. También estoy interesado en el problema más general donde buscamos descomposiciones como sumas de términos de la forma $\Pi p_i^{e_i}$ donde $\{p_i\}$ son primos especificados.

Answer 1

La función generadora es $$\prod_{i \ge 0}\prod_{j \ge 0} \left(1+z^{2^i 3^j}\right),$$ lo cual, por la unicidad de la expansión binaria, se simplifica a $$\prod_{k \ge 0} \frac{1}{1-z^{3^k}},$$ la función generadora de particiones en potencias de $3$. Ver https://oeis.org/A062051