Why is the number of binary Lyndon words of length n usually divisible by 3? Binary Lyndon words are counted by the OEIS sequence A001037.  Of the first 100 of terms in this sequence, about 80% are divisible by 3.  There are hints of a pattern, but I see nothing solid.  The OEIS entry lists formulas for calculating the sequence, but I don't see an answer there.
 A: One of the formulas for the sequence is
$$
a_n = \tfrac1n \sum_{d\mid n} \mu\big(\tfrac nd\big) 2^d,
$$
which implies
$$
- n a_n \equiv \sum_{d\mid n} \mu\big(\tfrac nd\big) (-1)^{d-1} \pmod3.
$$
Notice that the right-hand side is the Dirichlet convolution of two multiplicative functions $\mu(k)$ and $(-1)^{k-1}$; therefore its values are determined by its values on prime powers. Moreover, its value on every prime power is quickly calculated to be $0$, except for the prime power $2^1$ where it equals $-2$. In other words, the right-hand side equals $0$ for all integers greater than $2$.
Consequently, the left-hand side is a multiple of $3$ for all $n\ge3$. When $n$ itself is a multiple of $3$ we haven't learned anything, but we now know that $a_n$ is a multiple of $3$ for all $n>3$, $3\nmid n$.
That accounts for $67$% of the integers. Numerically it seems that the sequence also vanishes modulo $3$ for about half the multiples of $3$. I don't immediately see a pattern, but maybe a similar analysis will prove insightful.
A: Consider the following sequence:
$a(n) = \displaystyle \frac{1}{2} \sum \limits_{d \mid n} \mu(d) 2^{n/d}$
It is known that $a(n)$ is divisible by $3$ for all $n \ge 3$.  See A000740 for more details.
The number of binary Lyndon words can be written as follows:
$b(n) = \displaystyle \frac{1}{n} \sum \limits_{d \mid n} \mu(d) 2^{n/d}$
$b(n) = \frac{2}{n} a(n)$
Therefore, whenever $n \ge 3$ is not a multiple of $3$, we know that $b(n)$ is divisible by $3$.  On the other hand, when $n$ is a multiple of $3$, then $b(n)$ is divisible by $3$ only when $a(n)$ is divisible by $9$.
Using the above facts we can determine heuristically that the fraction of binary Lyndon words divisible by $3$ is approximately  $\frac{2}{3}+\frac{1}{9}$, or $77.77 \%$.  Pretty close to the $80 \%$ you mentioned in your question.
