Sloane's OEIS sequence [A001037][1] counts ($n=r$ in your definition):

Number of degree-$n$ irreducible polynomials over $GF(2)$; 

number of $n$-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period $n$; 

number of binary Lyndon words of length $n$.

The first few terms of the sequence are (for $n=1,2,...$ ) $2,1,2,3,6,9,...$

The formula for the sequence is $$\frac{1}{n}\sum_{d|n}\mu(n/d)\cdot 2^d$$. Since the terms of the sum corresponding to strict divisors $d$ of $n$ are much smaller this almost gives what you want (leading term is $2^n/n=O(2^{n/\log n})$.


  [1]: https://oeis.org/A001037