39. The sequence $\left\{a_{n}\right\}$ is defined as follows:
$$a_{1}=0, a_{n}=a\left[\frac{n}{2}\right]+(-1)^{\frac{n(n+1)}{2}}, n=2,3, \cdots$$

For each $k \in \mathbf{N}$, find the number of indices $n$ that satisfy $2^{k} \leqslant n<2^{k+1}$ and $a_{n}=0$.
For each $n \in \mathbf{N}^{*}$, let $x_{n}$ be the number of times the adjacent pairs 00 and 11 appear in the binary representation of $n$, and $y_{n}$ be the number of times the adjacent pairs 01 and 10 appear. We prove:
$$a_{n}=x_{n}-y_{n}$$

In fact, when $n=1$, $x_{1}=y_{1}=0$, so (7) holds for $n=1$.
Now assume (7) holds for indices $1,2, \cdots, n-1(n \geqslant 2)$, and consider the case for $n$.
If the last two digits of the binary representation of $n$ are 00 or 11, then $n \equiv 0$ or $3(\bmod 4)$, in this case, $a_{n}=a\left[\frac{n}{2}\right]+1$, and
$$x_{n}=x\left[\frac{n}{2}\right]+1, y_{n}=y\left[\frac{n}{2}\right]$$

Therefore, (7) holds for $n$.
If the last two digits of the binary representation of $n$ are 01 or 10, then $n \equiv 1$ or $2(\bmod 4)$, in this case, $a_{n}=a\left[\frac{n}{2}\right]-1$, and
$$x_{n}=x\left[\frac{n}{2}\right], y_{n}=y\left[\frac{n}{2}\right]+1,$$

Therefore, (7) holds for $n$.
In summary, (7) holds for all $n \in \mathbf{N}^{*}$.
Now we need to calculate the number of $n$ such that $2^{k} \leqslant n<2^{k+1}$ and $x_{n}$ equals $y_{n}$ in the binary representation.

In this case, $n$ in binary representation is a $(k+1)$-bit number, denoted as $B_{n}$. When $k \geqslant 1$, subtract the next bit from each bit of $B_{n}$ from left to right, and take the absolute value, to obtain a $k$-element 0,1 array $C_{n}$ (for example: if $B_{n}=(1101)_{2}$, then $\left.C_{n}=(011)\right)$. Note that, each adjacent pair 00 and 11 in $B_{n}$ becomes a 0 in $C_{n}$, and 01 and 10 become a 1 in $C_{n}$. Therefore, if $x_{n}=y_{n}$, then the number of 1s in $C_{n}$ is the same as the number of 0s. Conversely, for a $k$-element 0,1 array $C_{n}=\left(c_{1} c_{2} \cdots c_{k}\right)$, then in $\bmod 2$ sense, compute the following sum:
$$b_{1}=1+c_{1}, b_{2}=b_{1}+c_{2}, \cdots b_{k}=b_{k-1}+b_{k}$$

Here $b_{0}=1$, then $B_{n}=\left(b_{0} b_{1} \cdots b_{k}\right)_{2}$ is a binary representation of a number $n$ satisfying $2^{k} \leqslant n<2^{k+1}$. This indicates: $B_{n}$ and $C_{n}$ form a one-to-one correspondence.

Therefore, the answer to the original problem is equal to the number of $k$-element 0,1 arrays where the number of 0s and 1s are the same. Thus, when $k$ is odd, the answer is 0; when $k$ is even, the answer is $\mathrm{C}_{k}^{\frac{k}{2}}$ (note that $\mathrm{C}_{0}^{0}=1$).