I have 3 more questions about [maximal words](https://mathoverflow.net/questions/38657/minimal-words-of-length-n) (which are just another way of talking of necklaces).


Let W be a finite word on a two symbol alphabet {0,1}; let us say that W is maximal if it is the last item in the list of all its cyclic permutation (ordered lexicographically).


The number w(n) of maximal words of length n can be expressed with the aid of Eulers' totient function (see 
[Minimal words of length n](https://mathoverflow.net/questions/38657/minimal-words-of-length-n/38798#38798)). 


**Question 1**: What can be said about the asymptotics of w(n)? I expect that $lim (1/n) \log w(n) = h$ for some positive value h ...


**Question 2:** **The bisection scheme.**
Let us play the following game: start with the two string list [1,0] (which are both maximal) then we put in between the string obtained concatenating them, so we obtain the list [1,10,0], we go on like this (for any two neighbouring strings S,T we put the string ST in between), obtaining in turn the lists [1,110,10,100,0], [1,1110,110,11010,10,10100,100,1000,0] ... und so weiter.


I guess (and almost can prove) that in this way you generate all (and only) **primitive maximal words** of any length (let us say that a maximal word is *primitive* if it is not the repetition of a shorter one).


Has anybody a nice proof of this?


**Question 3:** is there an asymptotic distribution for the lengths of primitive maximal words generated by n runs of the prvious algorithm?



Maximal words (reloaded)
I can answer your first question fully, and the second question only partially.


**Question 1:** Assuming you meant $\log\_2$ in your expression, the answer is $h=1$. That is because $w(n)=\frac{1}{n}\sum\_{d|n}\phi(d)2^{n/d}\geq \frac{1}{n}2^n$ by just considering the first summand, and $w(n)=\frac{1}{n}\sum\_{d|n}\phi(d)2^{n/d}\leq n 2^n$ by upper-bounding the number of summands to be $n$ each at most $n2^n$.


**Question 2:** I'm afraid not all necklaces are generated by your method. Continue two more steps to notice the only two full-period necklaces of length $6$ you produce are $111110$ and $100000$.


