Sums of powers of two.. with one restriction. For a positive integer $n,$ let $a_n$ denote the number of ways of representing $n$ as a sum of powers of 2, where each power of 2 appears at most three times, and the order of the terms does not matter. For example, $a_8 = 5$ because of the representations
\begin{align*}
8 &= 8 \\
&= 4 + 4 \\
&= 4 + 2 + 2 \\
&= 4 + 2 + 1 + 1 \\
&= 2 + 2 + 2 + 1 + 1.
\end{align*}(The representation $1 + 2 + 1 + 4$ is the same as $4 + 2 + 1 + 1.$) Compute $a_{1000}.$
 A: Let's prove @Oldnboy's conjecture with a hint by @JyrkiLahtonen to a technique the OP might not know well. Restate $n=\sum_jc_j2^j$, with $0\le c_j\le3$, as $x^n=\prod_jx^{c_j2^j}$, so $a_n$ is the $x^n$ coefficient in$$\begin{align}\prod_{j\ge0}(1+x^{2^j}+x^{2\cdot2^j}+x^{3\cdot2^j})&=\prod_j\frac{1-x^{4\cdot2^j}}{1-x^{2^j}}\\&=\frac{1}{(1-x)(1-x^2)}\\&=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots).\end{align}$$This is just the number of integers from $0$ to $n$ inclusive with $n$'s parity, i.e. $\lfloor\tfrac{n}{2}\rfloor+1$ as claimed.
We can use this technique if $3$ is replaced with another Mersenne number. Otherwise, it's a bit tricky because the product doesn't telescope. I've asked a question about further generalization.
A: Well, OP asked for "computed" value of $a_{1000}$and nobody computes better than my Mac ;)
def countInternal(n, last1, last2, last3):
    # recursion will eventually finish here
    if n == 0:
        return 1

    # in the beginning we have to start with 1
    # otherwise we start with the last used number
    start = 1 if last1 == 0 else last1

    # if the last number is already used three times, just double it.
    if start == last2 and start == last3:
        start *= 2

    # here we accumulate the total number of combinations 
    # for various starting numbers
    s = 0

    # when starting number is bigger than n, we are done
    while start <= n:

        # recursive approach
        # we add a number of combinations starting with number start
        # start, last1, last2 are the last 3 used numbers
        s += countInternal(n - start, start, last1, last2)

        # after that, just double the starting number 
        # and do another round
        start *= 2
    return s

def count(n):
    result = countInternal(n, 0, 0, 0)
    print("a(" + str(n) + ")=" + str(result))
    return result

count(1)
count(2)
count(3)
count(8)
count(10)
count(1000)

The code prints:
a(1)=1
a(2)=2
a(3)=2
a(8)=5
a(10)=6
a(1000)=501

So the answer is 501. For the sake of curiosity I have computed a few other values:
a(10000)=5001
a(10001)=5001
a(20000)=10001

Therefore conjecture:
$$\boxed{a_n=\lfloor{\frac{n}{2}}\rfloor + 1}$$
