Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$
You can use simple enumeration.  This will be about as fast as you can achieve, for a modulus of the form $2^n-1$.

Namely, for each possible $k$, you check whether $C_k$ is a new set (distinct from the ones you already know about).  If it is, you add it to the set; if it isn't; you skip it and move onto the next $k$.

This gives an algorithm like the following:


Set $S := \emptyset$ and $A := \emptyset$.  ($A$ holds the set of representatives; $S$ holds the set of elements covered by one of the corresponding cyclotomic classes.)
For each $k=1,2,\dots,2^n-1$:


If $k \notin S$, add $k$ to $A$ and set $S := S \cup C_k$.



The running time of this algorithm will be $\Theta(2^n)$.

This is also within a $\Theta(n)$ factor of optimal.  In particular, any algorithm must have running time at least $\Theta(2^n/n)$.  The reason is that, for a modulus of the form $2^n-1$, the output size of any correct algorithm must be $\Theta(2^n/n)$: there are $\Theta(2^n/n)$ distinct cyclotomic classes.  Therefore, no algorithm can run faster than $\Theta(2^n/n)$ time, since it will take at least $\Theta(2^n/n)$ time to print/construct the desired output.

Why is the output size $\Theta(2^n/n)$.  Well, for the specific modulus $2^n-1$, it is guaranteed that each cyclotomic class has size $n$.  (Proof: $2^n \equiv 1 \pmod{2^n-1}$, so no cyclotomic class can have size larger than $n$.  Also $2^j &lt; 2^n-1$ when $j&lt;n$, so $2^j \not\equiv 1 \pmod{2^n-1}$ when $j&lt;n$.  Therefore each cyclotomic class has size exactly $n$.)  This result is specific to the particular kind of modulus you are focusing on.