Solution

Answer: Such constants exist with \(\lambda=3^{1 / 6}\); we will discuss appropriate values of \(c_{1}\) and \(c_{2}\) in the solution below.

In order to solve this, we will give a complete classification of \(n\)-sequences.

Let \(k=\lfloor n / 2\rfloor\). We will say that an \(n\)-sequence is large if \(a_{i}>k\) for some \(i\), and small if no such \(i\) exists. For now we will assume that \(\left(a_{i}\right)\) is not the identity sequence (in other words, that \(a_{i} \neq i\) for some \(i\) ).

Lemma 1: If \(a_{r}=a_{s}\) and \(r, s<n\), then \(a_{r+1}=a_{s+1}\).

Proof: We have \(a_{r+1}=a_{a_{r}+a_{1}}=a_{a_{s}+a_{1}}=a_{s+1}\).

Lemma 2: If \(i \leqslant k\), then \(a_{i} \leqslant k\).

Proof: We have \(i+i \leqslant n\), so \(a_{i}+a_{i} \leqslant n\) whence \(a_{i} \leqslant k\).

Lemma 3: There exist \(r, s\) such that \(a_{r}=a_{s}\) and \(r \neq s\).

Proof: If \(a_{0} \neq 0\) then \(a_{2 a_{0}}=a_{0}\). Otherwise, \(a_{a_{i}}=a_{i}\) for all \(i\), so take \(i\) such that \(a_{i} \neq i\) (which we can do by our earlier assumption).

Lemma 4: Let \(r\) be the smallest index such that \(a_{s}=a_{r}\) for some \(s>r\), and let \(d\) be the minimum positive integer such that \(a_{r+d}=a_{r}\). Then

1. The subsequence \(\left(a_{r}, a_{r+1}, \ldots, a_{n}\right)\) is periodic with minimal period \(d\). That is, for \(u<v\), we have \(a_{u}=a_{v}\) if and only if \(u, v \geqslant r\) and \(d \mid v-u\).
2. \(a_{i}=i\) for \(i<r\) and \(a_{i} \geqslant r\) for \(i \geqslant r\).

In this case we say \(\left(a_{i}\right)\) has period \(d\) and offset \(r\).

Proof: We prove each in turn:

1. The "if" implication is clear from Lemma 1. For the reverse direction, suppose \(a_{u}=a_{v}\). Then there are integers \(r \leqslant u_{0}, v_{0}<r+d\) such that \(d \mid u-u_{0}, v-v_{0}\), so \(a_{u_{0}}=a_{u}=a_{v}=\) \(a_{v_{0}}\). If \(u_{0}<v_{0}\) then \(a_{r+d+u_{0}-v_{0}}=a_{r+d}=a_{r}\), contradicting the minimality of \(d\). There is a similar contradiction when \(u_{0}>v_{0}\). Thus \(u_{0}=v_{0}\), so \(d \mid u-v\).
2. If \(r=0\) there is nothing to prove. Otherwise \(a_{0}=a_{2 a_{0}}\) so \(2 a_{0}=0\). Then we have \(a_{a_{i}}=a_{i}\) for all \(i\), so \(a_{i}=i\) for \(i<r\).

Lemma 5: Either

1. \(d \mid a_{i}-i\) for all \(i\), or
2. \(r=0\) and \(d \mid a_{i}-i-d / 2\) for all \(i\).

Proof: Note that Lemma 4 tells us that if \(a_{u}=a_{v}\) then \(d \mid u-v\). Since \(a_{a_{i}+a_{0}}=a_{i}\) for all \(i\), we have \(d \mid a_{i}-i+a_{0}\). For \(i=0\), this means that \(d \mid 2 a_{0}\). If \(d \mid a_{0}\) then that means that \(d \mid a_{i}-i\) for all \(i\). Otherwise, if \(d \nmid a_{0}\), then \(d \mid a_{0}-d / 2\) and thus \(d \mid a_{i}-i-d / 2\) for all \(i\). In addition, part 2 of Lemma 4 says that we must have \(r=0\) in this case.

Lemma 6: If \(d\) is even and \(d \mid a_{0}-d / 2\), then \(\left(a_{i}\right)\) is small. (Note that we must have \(r=0\) in this case.)

Proof: Note that if \(d \leqslant k+1\), then by Lemma \(2,\left(a_{0}, \ldots, a_{d-1}\right)\) is a period for the sequence consisting of elements at most \(k\), so \(\left(a_{i}\right)\) must be small. Now suppose \(d>k+1\). We show that \(a_{i} \leqslant k\) for all \(i\) by induction. Note that Lemma 2 already establishes this for \(i \leqslant k\). We must have \(d \mid a_{d / 2}\) and \(a_{d / 2} \leqslant k<d\) so \(a_{d / 2}=0\). Thus, for \(i>k\), if \(a_{j} \leqslant k\) for \(j<i\), then \(a_{i-d / 2} \leqslant k\), so \(a_{i}=a_{(i-d / 2)+d / 2}=a_{a_{i-d / 2}} \leqslant k\).

Lemma 7: If \(\left(a_{i}\right)\) is small, then \(r+d \leqslant k+1\).

Proof: Since \(\left(a_{i}\right)\) is small, there exists \(u, v \leqslant k+1\) such that \(u<v\) and \(a_{u}=a_{v}\). Thus \(u \leqslant r\) and \(d \mid v-u\), so \(r+d \leqslant v \leqslant k+1\).

Lemma 8: If \(\left(a_{i}\right)\) is large, then \(r+d>k+1\) and \(a_{i}=i\) for all \(0 \leqslant i<r+d\).

Proof: Since \(\left(a_{i}\right)\) is large and has period \(d\) and offset \(r\), the period \(\left(a_{r}, \ldots, a_{r+d-1}\right)\) must have an element that is larger than \(k\), so by Lemma 2 we must have \(r+d-1>k\).

We already have \(a_{i}=i\) for \(i<r\). Now we show that \(a_{i}=i\) for \(r \leqslant i \leqslant k\). By Lemma 6 we have \(d \mid a_{i}-i\) but \(r \leqslant i \leqslant k\). Since \(k-r+1>d\), this means that \(a_{i}=i\) for \(i \leqslant k\).

Finally, one can show inductively that \(a_{i}=i\) for \(k<i<r+d\). Indeed, if \(a_{j}=j\) for all \(j<i\), then \(a_{i} \geqslant i\) (otherwise \(a_{i}=a_{j}\) for some \(j<i\), but then \(r \leqslant j\) and \(i<r+d\) means that \(d \nmid j-i\).) However, \(a_{i}+(n-i)=a_{i}+a_{n-i} \leqslant n\), so \(a_{i}=i\).

Thus large sequences are determined by \(r\) and \(d\). It is not hard to check that all sequences of the form \(a_{i}=i\) for \(i<r+d\) and with period \(d\) and offset \(r\) are \(n\)-sequences. There are \((n-k-1)(n+k+2) / 2\) possible choices of \((r, d)\) where \(0 \leqslant r<n, d \geqslant 1\), and \(k+1<r+d \leqslant n\).

For small sequences, for a given period \(d\) and offset \(r\), we need to choose the period \(\left(a_{r}, \ldots, a_{r+d-1}\right)\) satisfying \(r \leqslant a j \leqslant k\) and \(d \mid a_{j}-j\) for \(r \leqslant j<r+d\). There are \(g(k+1-r, d)\) such choices, where we define \(g(x, d)\) to be \((p+1)^{q} p^{d-q}\) with \(p=\lfloor x / d\rfloor\) and \(q=x-d p\).

Furthermore, if \(d\) is even then there are \(g(k+1, d)\) choices for the period \(\left(a_{0}, \ldots, a_{d-1}\right)\) satisfying \(d \mid a_{j}-j-d / 2\) for \(j<d\). Again it is not hard to check that, once these choices are made, then the resulting sequence is an \(n\)-sequence.

Thus the total number of \(n\)-sequences is

\[\begin{equation*} f(n)=1+\frac{(n-k-1)(n+k+2)}{2}+\sum_{d^{\prime}=1}^{\lfloor(k+1) / 2\rfloor} g\left(k+1,2 d^{\prime}\right)+\sum_{r=0}^{k} \sum_{d=1}^{k+1-r} g(k+1-r, d) \tag{1} \end{equation*}\]

Now, to show that \(f(n)>c_{1} \lambda^{n}\) for some \(c_{1}\), we note that

\[f(n)>g\left(k+1,\left\lfloor\frac{k+1}{3}\right\rfloor\right) \geqslant 3^{\lfloor(k+1) / 3\rfloor}>3^{n / 6}-1\]

To show that \(f(n) for some \(c_{2}\), it actually suffices to show that there is a positive real number \(c_{3}\) such that for all positive integers \(x\),

\[\sum_{d=1}^{x} g(x, d) \leqslant c_{3} 3^{x / 3}\]

In fact, the following lemma suffices, as it bounds the left hand side of the above inequality by a pair of geometric series with initial term \(3^{x / 3}\) : **Lemma:** For positive \(d, x\), we have:

\[g(x, d) \leqslant \begin{cases}3^{x / 3}\left(\frac{64}{81}\right)^{x / 3-d}, & \text { if } d \leqslant x / 3 \\ 3^{x / 3}\left(\frac{8}{9}\right)^{d-x / 3}, & \text { if } d \geqslant x / 3\end{cases}\]

*Proof:* There are a few key observations needed, all of which are immediate from the definition: - \((x, d)\) is the maximum product of a sequence of \(d\) integers that sums to \(x\). - For any positive integer \(k\), we have \(g(k x, k d)=g(x, d)^{k}\). - If \(2 d \leqslant x \leqslant 3 d\), then \(g(x, d)=2^{3 d-x} 3^{x-2 d}\). Likewise, if \(3 d \leqslant x \leqslant 4 d\) then \(g(x, d)=\) \(3^{4 d-x} 4^{x-3 d}\). With these observations, if \(d \leqslant x / 3\), then

\[3^{4(x-3 d)} g(3 x, 3 d) \leqslant g(3 x+12(x-3 d), 3 d+4(x-3 d))=g(15 x-36 d, 4 x-9 d)\]

To calculate \(g(15 x-36 d, 4 x-9 d)\), note that

\[\begin{aligned} & 3(4 x-9 d)=12 x-27 d \leqslant 15 x-36 d \\ & 4(4 x-9 d)=16 x-36 d \geqslant 15 x-36 d \end{aligned}\]

so

\[g(15 x-36 d, 4 x-9 d)=3^{4(4 x-9 d)-(15 x-36 d)} 4^{(15 x-36 d)-3(4 x-9 d)}=3^{x} 4^{3(x-3 d)}\]

Thus

\[g(x, d)^{3}=g(3 x, 3 d)=\frac{3^{4(x-3 d)} g(3 x, 3 d)}{3^{4(x-3 d)}} \leqslant \frac{3^{x} 4^{3(x-3 d)}}{3^{4(x-3 d)}}=3^{x}\left(\frac{64}{81}\right)^{x-3 d}\]

which completes the proof of the first claim. Likewise, if \(d \geqslant x / 3\),

\[3^{2(3 d-x)} g(3 x, 3 d) 3 \leqslant g(3 x+6(3 d-x), 3 d+2(3 d-x))=g(18 d-3 x, 9 d-2 x)\]

Again we have

\[2(9 d-2 x) \leqslant 18-3 x \leqslant 18-3 x+3(3 d-x)=3(9 d-2 x)\]

so

\[g(18 d-3 x, 9 d-2 x)=2^{3(9 d-2 x)-(18 d-3 x)} 3^{(18 d-3 x)-2(9 d-2 x)}=2^{3(3 d-x)} 3^{x}\]

Thus

\[g(x, d)^{3}=g(3 x, 3 d)=\frac{2^{3(3 d-x)} g(3 x, 3 d)}{3^{2(3 d-x)}} \leqslant \frac{2^{3(3 d-x) 3^{x}}}{3^{2(3 d-x)}}=3^{x}\left(\frac{8}{9}\right)^{3 d-x}\]

from which the second claim follows. ### Common remarks The best possible value of \(c_{1}\) is constrained by \(n=1\): in this case, \(f(1)=2\), which means that \(c_{1}>2 \cdot 3^{-1 / 6} \approx 1.66537\). With a careful analysis one can show that the best possible value of \(c_{2}\) is \(\frac{236567}{4930} 3^{1 / 3} \approx\) 69.20662$.