Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$ Question

Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow aB$ where $A$ and $B$ are non-terminals?

Remark

Symbol minimal means that there is no other context-free grammar that generates $L_n$ with fewer characters (symbols) for all rules. For instance, the number of symbols of the rules in $\{ S \rightarrow a, S \rightarrow aS \}$ is 7 (these rules are also minimal for $\{ a \}^+$).

Known Results

Facts about G (a symbol minimal context-free language for $L_n$) that I have already proved:


The right hand side of the rules of $G$ consist of at least 2 characters (non-terminals and/or terminals) (otherwise it’s easy to find a grammar that has fewer symbols).
For each non-terminal of $G$ there exists exactly one rule (can be shown by contradiction).
There are no loops in the derivations of $G$ (because $L_n$ is finite).
There is an upper bound for the number of symbols: we can trivially generate $L_n$ with the rules $\{ S \rightarrow a^n \}$. We count the number of symbols and get $n + 2$ – that’s an upper bound.


I wrote a program that finds symbol minimal grammars for a specific $n$ by creating all possible grammars generating $L_n$ (there are only a finite number because we have an upper bound). Here are the results for some small $n$:


$n = 2$: $\{ S \rightarrow aa \}$, $4$ symbols
$n = 3$: $\{ S \rightarrow aaa \}$, $5$ symbols
…
$n = 7$: $\{ S \rightarrow aaaaaaa \}$, $9$ symbols
$n = 8$: $\{ S \rightarrow a^8\}$, $\{ S \rightarrow AA, A \rightarrow a^4 \}$, $\{ S \rightarrow AAAA, A \rightarrow aa \}$, $10$ symbols
$n = 9$: $\{ S \rightarrow AAA, A \rightarrow a^3 \}$, $10$ symbols
$n = 10$: $\{ S \rightarrow AA, A \rightarrow a^5 \}$, $\{ S \rightarrow A^5, A \rightarrow aa \}$, $\{ S \rightarrow aA^3, A \rightarrow a^3 \}$, $11$ symbols
$n = 11$: $\{ S \rightarrow aAA, A \rightarrow a^5 \}$, $\{ S \rightarrow aA^5, A \rightarrow aa \}$, $\{ S \rightarrow aaA^3, A \rightarrow a^3 \}$, $12$ symbols
$n = 12$: $\{ S \rightarrow AAA, A \rightarrow a^4 \}$, $\{ S \rightarrow A^4, A \rightarrow aaa \}$, $11$ symbols
$n = 13$: …,  $12$ symbols
$n = 14$: …,  $13$ symbols
$n = 15$: …,  $12$ symbols
$n = 16$: …,  $12$ symbols


There are nice „ups and downs“ in the number of symbols, right? I have seen grammars that contain rules like $A \rightarrow aB$ but they were not symbol minimal …
First, let me add some more to the known results section, specific to your question.


$B$ must occur in another RHS than $A\rightarrow aB$, or we could just copy the rule that has $B$ on the LHS instead of $B$ to the above rule to get a smaller system.
In any other RHS that has $B$, there can be no terminal symbol because instead of $aB$ we could write $A$.
$A$ must occur at least $4$ times on the RHS, otherwise, we could just write $aB$ instead of it.


This already shows that $n$ will be quite large that satisfies these. However, I think such an $n$ might exist. Below I give a set of rules for $n=93$ with $28$ symbols and I challenge all to make a smaller system! (If the challenge is too easy, generalize it in the obvious way...)

$S\rightarrow AAAACCC$

$A\rightarrow aB$

$B\rightarrow aaa$

$C\rightarrow DDD$

$D\rightarrow BBB$

Update

Well, this is not optimal for any $n$ as shown by Peter in the comment...