Representations of 100

Define $v(n)$ to be the number of such ways for $n \in \mathbb{Z^+}$ to be expressed as above. Suppose we want to partition our said sum into 2 parts: One part of the sum consists of terms divisible by 3, the other consists of terms not divisible by 3. In particular, our latter group of terms will consist of terms of form $2^x$ , where $x \in \mathbb{Z^+} \cup \{ 0 \}$ .

Our latter part will have a unique sum of terms, since it is well known that for any $n \in \mathbb{Z^+}$ it can be uniquely expressed as the sum of distinct terms of form $2^x$ , where $x \in \mathbb{Z^+} \cup \{ 0 \}$ . (Just convert to binary to find said sum of powers of 2, with 1 if odd)

We need to find all such sums that are partitioned as above where the first group of terms would sum to $3m$ , where $m \in \mathbb{Z^+} \cup \{ 0 \}$ . For $n=100$ there are $34$ such groupings, where the first group sums to $3m$ and the second group sums to $100-3m$ where $m$ is a non-negative integer and $0 \leq m \leq 33$ . Since we know from the previous paragraph that the second group has a unique sum, we hence only need to focus on the first group.

Now, the number of ways to find a sum of $3m$ with the terms following the above conditions as well as being divisible by 3 is equivalent to finding $v(m)$ for $0 \leq m \leq 33$ . We thus need to find $\displaystyle \sum_{i=0}^{33}v(i)$ . Note that by using analogous reasoning above for n in general, we have $v(3l)=v(3l+1)=v(3l+2)$ for $l \in \mathbb{Z^+} \cup \{ 0 \}$ , since we have $v(n)=\displaystyle \sum_{i=0}^{\lfloor n/3 \rfloor}v(i)$ (we only focus on the first group of terms that has a sum of form $3m$ where $m \in \mathbb{Z^+} \cup \{ 0 \}$ ). Then, our summation reduces to $3 (\displaystyle \sum_{i=0}^{10}v(3i)) + v(33)$ .

By using the same reasoning again on our now-reduced summation, where we substitute $v(3i)=\displaystyle \sum_{j=0}^{i}v(j)$ , we can reduce our summation further to $v(100)=\displaystyle\sum_{i=0}^{11}((12-i)*v(i)) + \displaystyle\sum_{i=0}^{10}((11-i)*v(i))$

It's not hard to figure out through a few sums that we have $v(0)=v(1)=v(2)=1, v(3)=v(4)=v(5)=2,$ $v(6)=v(7)=v(8)=3, v(9)=v(10)=v(11)=5$ . Plugging in these values to the above sum, we get $\fbox{402}$

Using generating functions:

We must partition 100 using parts in the form of $$2^{a}3^{b}, \space 0 \leq a \leq 6, \space 0 \leq b \leq 4$$ Let S be the set of all such numbers less than 100.

Then we are looking for the coefficient of x^100 in $$\prod_{i \in S} (1 + x^{i}) $$

This can be verified using a computer to be 402.

So this is hardly a graceful solution, but anyhow....

Noting that each summand has only prime factors 2 and 3 (or neither) gives this as a complete list: $1,2,3,4,6,8,9,12,18,16,24,27,32,36,48,54,64,72,81,96.$

At this point, you cheat monumentally by simply finding the co-efficient of 100 in the expansion of this ridiculous polynomial:

$(1+x)(1+x^{2}) (1+x^{3})(1+x^{4}) (1+x^{6})(1+x^{8}) (1+x^{9})(1+x^{12}) (1+x^{16})(1+x^{18})(1+x^{24})(1+x^{27}) (1+x^{32})(1+x^{36}) (1+x^{48})(1+x^{54}) (1+x^{64})(1+x^{72}) (1+x^{81})(1+x^{96})$

This gives an answer of $\boxed{40}$

Of course, this solution is awful, so please ofter a better alternative!