In how many ways can 2016 be written as a sum $ a_0 + 2 \cdot a_1 + 2^2 \cdot a_2 + \cdots + 2^k \cdot a_k $

if $ a_i $ are only allowed to take values $0,1,2$ or $3$ ?

Steps would be appreciated.


closed as off-topic by Michael Hoppe, user147263, John B, Leucippus, Shailesh Mar 11 '16 at 0:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Michael Hoppe, Community, John B, Leucippus, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Do you know generating functions? $\endgroup$ – Thomas Andrews Mar 10 '16 at 17:24
  • $\begingroup$ Yes but I do not see how it is going to help. I used mod of the whole equation until mod 32 , and the whole process gets a little bit tedious $\endgroup$ – Jack Wother Mar 10 '16 at 17:30

There are two approaches to this.

Easy approach:

Note that each $a_i$ can be written as $c_i+2d_i$ where $c_i,d_i\in\{0,1\}$, and this this is the same as counting the number of ways to write $2016$ as $c+2d$, with the $c_i,d_i$ the binary digits of the $c,d$ respectively.

Generating function approach:

Let $f(n)$ be the number of ways of writing $n$ in this form. Then notice that:

$$\begin{align} \sum f(n)x^n &= \prod_{i=0}^{\infty}\left(1+x^{2^i}+x^{2\cdot 2^i} + x^{3\cdot 2^i}\right)\\ &=\prod_0^{\infty}\frac{x^{2^{i+2}}-1}{x^{2^{i}}-1}\\ &=\frac{1}{(1-x)(1-x^2)} \end{align}$$

Basically, all the denominators except the first ones get cancelled by a numerator.

We then see, again, that $f(n)$ is the number of ways of writing $n=c+2d$.

As the way of mathematics often is, I did the complicated way first, and then when I saw the answer, was able to find the "easy" solution.

  • $\begingroup$ In regards to your "complicated precedes easy" observation, I find that to be true annoyingly often. $\endgroup$ – Brian Tung Mar 10 '16 at 17:55
  • $\begingroup$ I understand most of it but how to compute the number of ways of writing 2016 as it was said? I thinking about precise numer. I just don't understand the last sentence of your solution. $\endgroup$ – Michael Mar 23 '16 at 17:37
  • $\begingroup$ The last sentence is just a comment on math in general. I didn't actually write out a formula, figuring I'd leave that to the questioner. Given $n$, how many ways can you write $n$ as the sum $c+2d$ where $c,d\geq 0$? $\endgroup$ – Thomas Andrews Mar 23 '16 at 18:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.