Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$
There is a grammar of size $O(\log n)$ using repeated squaring.

Let's start with the simpler case $n = 2^m$:
$$
\begin{align*}
&amp;S \to a B_0 B_1 \dots B_{m-1} \\
&amp;B_i \to A_i | \epsilon &amp;&amp; (0 \leq i \leq m-1) \\
&amp;A_i \to A_{i-1}A_{i-1} &amp;&amp; (1 \leq i \leq m-1) \\
&amp;A_0 \to a
\end{align*}
$$
Here $A_i \to a^{2^i}$ and $B_i \to a^{2^i}|\epsilon$.

More generally, suppose $n-1 = 2^{d_0} + 2^{d_1} + \cdots + 2^{d_\ell}$, where $d_0 &gt; d_1 &gt; \cdots &gt; d_\ell$. The corresponding grammar is:
$$
\begin{align*}
&amp;S \to a B_{d_0} | a C_0 B_{d_1} | a C_1 B_{d_2} | \cdots | a C_{\ell-1} B_{d_\ell} | aC_\ell  \\
&amp;C_j \to C_{j-1} A_{d_j} &amp;&amp; (1 \leq j \leq \ell) \\
&amp;C_0 \to A_{d_0} \\
&amp;B_i \to B_{i-1} A_{i-1} | B_{i-1} &amp;&amp; (1 \leq i \leq d_0) \\
&amp;B_0 \to \epsilon \\
&amp;A_i \to A_{i-1}A_{i-1} &amp;&amp; (1 \leq i \leq d_0) \\
&amp;A_0 \to a
\end{align*}
$$
Here $A_i \to a^{2^i}$, $B_i \to \{a^k : 0 \leq k &lt; 2^i\}$ and $C_j \to a^{2^{d_0} + \cdots + 2^{d_j}}$.

As an extra property, both grammars are unambiguous.