Given a positive integer $N$, let $f(N)$ be the number of ways $N$ can be decomposed as a sum of terms of the form $2^i3^j$, where each such term appears at most once in the sum. For example, $f(10) = 5$, since 10 can be expressed as $3^2 + 1, 2^2 + 2 \cdot 3, 2^2 + 3 + 2 + 1, 2 \cdot 3 + 3 + 1,$ and $2^3 + 2$. I would like upper and lower bounds on $f(N)$ in terms of $N$. I am also interested in the more general problem where we look for decompositions as sums of terms of the form $\Pi p_i^{e_i}$ where $\{p_i\}$ are specified primes.
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Are $2=2^0+3^0=2^13^0$ legitimate decompositions? $\endgroup$– markvsAug 4, 2021 at 3:26
-
$\begingroup$ Is this related to this question? mathoverflow.net/questions/383675/… $\endgroup$– Matthieu LatapyAug 4, 2021 at 6:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The generating function is $$\prod_{i \ge 0}\prod_{j \ge 0} \left(1+z^{2^i 3^j}\right),$$ which, by uniqueness of binary expansion, simplifies to $$\prod_{k \ge 0} \frac{1}{1-z^{3^k}},$$ the generating function of partitions into powers of $3$. See https://oeis.org/A062051
-
5$\begingroup$ "at most once" versus "as many times as you want" $\endgroup$– RobPrattAug 4, 2021 at 3:46
-
6$\begingroup$ And the bijection is pretty clear: take all parts $2^i3^j$ with fixed $j$, and replace to corresponding number of $3^j$'s $\endgroup$ Aug 4, 2021 at 4:49
-
$\begingroup$ Thanks for this response! I understand the bijection between the sums of N as 3-smooth parts and the partitions of N into powers of 3, but its still not clear to me how f(N) scales in N. Looking the first few values of f(N), it appears that f(N) grows polynomially in N. Does that sound right? $\endgroup$– GautamAug 4, 2021 at 18:33
-
$\begingroup$ @Gautam: according to hal.inria.fr/hal-01182959/document, Mahler proved that the number of $b$-ary partitions of $n$ grows like $(\log n)^2/(2\log b)$. $\endgroup$ Aug 4, 2021 at 20:16