MATL, 15 bytes
t4*:tB!s&=Rs-=s
Try it online! Or verify all test cases.
This makes use of the following result:
Claim
\$a(n) \le 3n/4\$ for \$n \geq 3\$.
Here is a graphical illustration. The bound is quite loose, but it is sufficient to establish that only a finite number of values of \$k\$ need to be tested for a given \$n\$ (more on that in “How the code works”).
Proof
The sequence \$a(n)\$ (A263017) is the amount of numbers in the set \$\{1,2,\ldots,n\}\$ that have the same binary weight as \$n\$. The binary expansion of \$n\$ has \$b \leq \log_2 n + 1\$ digits, with a leading 1. Let \$w\$ be the binary weight of \$n\$. Clearly \$w \in \{0,\ldots,b\}\$.
The number of unique permutations of the binary expansion of \$n\$, not necessarily with a leading 1, is \${b\choose w}\$. \$a(n)\$ will be at most equal to this value. It can be less, because some of the permutations may produce a number exceeding \$n\$. Thus,
$$
a(n) \leq {b\choose w}.
$$
For \$b\$ even, the bound
$$
{2m \choose m} \leq \frac{4^m}{\sqrt{3m+1}} \text{ for all } m \geq 1
$$
and the fact that \${b\choose w} \leq {b\choose b/2}\$ imply that
$$
{b \choose w} \leq \frac{2^b}{\sqrt{\frac{3b+2}{2}}}.
$$
For \$b\$ not necessarily even, the bound holds with \$b\$ replaced by \$b+1\$:
$$
{b \choose w} \leq \frac{2^{b+1}}{\sqrt{\frac{3b+5}{2}}}.
$$
Since \$b \leq \log_2 n + 1\$,
$$
a(n) \leq {b\choose w} \leq \frac{2^{b+1}}{\sqrt{\frac{3b+5}{2}}} \leq \frac{4n}{\sqrt{ 3/2 \cdot \log_2 n + 4}}.
$$
This is less than \$3n/4\$ for \$n \geq 80478\$, because
$$
\sqrt{3/2 \cdot \log_2 80478 + 4}\ = 5.3333348 > 16/3.
$$
For \$n = 3, \ldots, 80477 \$, direct computation of \$a(n)\$ shows that \$a(n) \leq 3n/4\$. Therefore \$a(n) \leq 3n/4\$ for \$n \geq 3\$.
How the code works
The above result implies that
$$
k-a(k) \geq k / 4.
$$
for all \$k \geq 3\$. Thus, given \$n\$, to compute the number of positive integers \$k\$ that satisfy
$$
k-a(k)\ = n
$$
it suffices to test the latter equality for \$k = 1, \ldots, 4n\$.
Consider input 1 as an example.
t4* % Implicit input: n. Duplicate. Multiply by 4
% STACK: 1, 4
: % Range. Gives [1 2 ... 4*n]. This is the vector of k values
% STACK: 1, [1 2 3 4]
tB % Duplicate. Binary expansion. Gives a binary matrix, where each row
% corresponds to a value of k
% STACK: 1, [1 2 3 4], [0 0 1;
0 1 0;
0 1 1;
1 0 0]
!s % Tranpose. Sum of each column. This gives the binary weights
% STACK: 1, [1 2 3 4], [1 1 2 1]
&= % Matrix of pair-wise equality comparisons
% STACK: 1, [1 2 3 4], [1 1 0 1;
1 1 0 1;
0 0 1 0;
1 1 0 1]
R % Upper triangular part. This sets elements below the diagonal to 0
% STACK: 1, [1 2 3 4], [1 1 0 1;
0 1 0 1;
0 0 1 0;
0 0 0 1]
s % Sum of each column. For each column k, this gives the amount of
% number up to k with the same weight as k; that is, a(k). Note that
% the condition "up to k" corresponds to having taken the upper
% triangular part of the matrix
% STACK: 1, [1 2 3 4], [1 2 1 3]
- % Subtract, element-wise. This gives k-a(k)
% STACK: 1, [0 0 2 1]
= % Equality comparison, element-wise. This compares n with each
% value k-a(k)
% STACK: [0 0 0 1]
s % Sum. Implicit display
% STACK: 1
