Return to Answer

Sloane's OEIS sequence A001037 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})$.

Sloane's OEIS sequence A001037 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})$.

Sloane's OEIS sequence A001037 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 gives what you want.

Sloane's OEIS sequence A001037 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})$.

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$$.

Sloane's OEIS sequence A001037 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 gives what you want.