Zigzag Code for Cubic Functions

Let \(S+T\) denote the concatenation of strings \(S\) and \(T\) in this order.
We will prove several lemmas in order.

Lemma 1

Let \(T_k\) denote the string obtained by repeating each character of \(\mathtt{-++-+--+}\) \(k\) times and concatenating them. Then, for any string \(S\) consisting of \(\mathtt{+-}\), the following holds.

• \(g(S+T_k)=g(S)+48k^4\)

Proof of Lemma 1

Let
\(h_0(x)=\sum_{i=1}^{k}f(x+i)\) \(h_1(x)=h_0(x+k)-h_0(x)\)
\(h_2(x)=h_1(x+2k)-h_1(x)\)
\(h_3(x)=h_2(x+4k)-h_2(x)\).
Then,
\(g(T_k)\; =-h_0(x)+h_0(x+k)+h_0(x+2k)-h_0(x+3k)+h_0(x+4k)-h_0(x+5k)-h_0(x+6k)+h_0(x+7k)\; =h_1(x)-h_1(x+2k)-h_1(x+4k)+h_1(x+6k)\; =-h_2(x)+h_2(x+4k)\; =h_3(x)\).
\(h_0(x)\) is a cubic function whose leading coefficient is \(k\).
The coefficient of the \(x^2\) term in \(k(x+k)^3-kx^3\) is \(3k^2\), so \(h_1(x)\) is a quadratic function whose leading coefficient is \(3k^2\). By the same reasoning, \(h_2(x)\) is a linear function whose leading coefficient is \(12k^3\), and \(h_3(x)\) is a constant function whose value is \(48k^4\). Therefore, \(h_3(x)=48k^4\).

Lemma 2

Let \(T'_k\) denote the string obtained by repeating each character of \(\mathtt{+--+-++-}\) \(k\) times and concatenating them. Then, for any string \(S\) consisting of \(\mathtt{+-}\), the following holds.

• \(g(S+T'_k)=g(S)-48k^4\)

Proof of Lemma 2

This can be shown in the same way as Lemma 1.

Lemma 3

Suppose \(X \equiv Y \pmod{48}\). If there exists a string \(S\) with \(g(S)=X\), then there exists a string \(S'\) with \(g(S')=Y\).

Proof of Lemma 3

Such a string can be constructed by appending some copies of \(T_1\) or \(T'_1\) to the end of \(S\).

Lemma 4

If there exists \(S\) with \(g(S) \equiv N \pmod {48}\), then there exists such an \(S\) with \(|S| \leq 48^2\).

Proof of Lemma 4

Take an \(S\) with \(g(S) \equiv N \pmod {48}\) that minimizes \(|S|\); it suffices to derive a contradiction assuming \(|S| \gt 48^2\).
Let \(S_i\) denote the first \(i\) characters of \(S\).
By the pigeonhole principle, there exist \(i,j \; (0 \leq i < j \leq |S|)\) such that \((|S_i| \pmod{48},g(S_i) \pmod {48})=(|S_j| \pmod{48},g(S_j) \pmod {48})\) (where we define \(g(S_0) \pmod {48}=0\)). The string \(S'\) obtained by removing the \((i+1)\)-th through \(j\)-th characters from \(S\) satisfies \(g(S') \equiv N \pmod{48}\), and since \(j-i \geq 48 > 2\), this is a contradiction.

Lemma 5

\(|\sum_{i=1}^{48^2}f(i)| \leq 5 \times 10^{14}\)

Proof of Lemma 5

This can be verified by actually checking with a program.

Lemma 6

Suppose \(N \leq 670\). Prepare an empty sequence \(A\), and for \(k=5,4,3,2,1\) in this order, repeat the following operation.

• While \(N \geq k^4\), subtract \(k^4\) from \(N\) and append \(k\) to the end of \(A\).

Then, the following holds.

• \(\sum_{i=1}^{|A|}{A_i} \leq 47\)
  

Proof of Lemma 6

For \(k=1,2,3,4\), the number of times \(k^4\) is subtracted is at most \(\left \lfloor \frac{(k+1)^4}{k^4} \right \rfloor\), which is \(15,5,3,2\), respectively.
Also, \(5^4\) is subtracted at most once. Since \(1 \times 15 + 2 \times 5 + 3 \times 3 + 4 \times 2+5 \times 1=47\), the claim is proved.

Lemma 7

Suppose \(N \leq \frac{6 \times 10^{14}}{48}\). Prepare an empty sequence \(A\), and for \(k=\lfloor N^{\frac{1}{4}}\rfloor,\lfloor N^{\frac{1}{4}}\rfloor-1,\dots,1\) in this order, repeat the following operation.

• While \(N \geq k^4\), subtract \(k^4\) from \(N\) and append \(k\) to the end of \(A\).

Then, the following holds.

• \(\sum_{i=1}^{|A|}{A_i} \leq 2590\)
  

Proof of Lemma 7

When subtracting \(k^4\) from \(N\), we have
\(N-k^4 \leq (k+1)^4-1-k^4=4k^3+6k^2+4k \leq 4\lfloor N^{\frac{1}{4}}\rfloor^3+6\lfloor N^{\frac{1}{4}}\rfloor^2+4\lfloor N^{\frac{1}{4}}\rfloor\).
Computing based on this, after \(10\) subtractions \(N\) becomes at most \(670\), and the sum of \(k\) up to that point is at most \(2543\).
Combined with Lemma 6, \(2543+47=2590\), so the claim is proved.

Solution

For \(k=L,L+1,\dots,\min(R,L+47)\), determine whether there exists \(S_k\) with \(g(S_k) \equiv k \pmod {48}\).
By Lemma 4, this can be determined by an \(O(48^3)\) DP.
If it exists, by reconstructing this DP, we can build \(S'_k\) of length at most \(48^2\) with \(g(S'_k) \equiv k \pmod{48}\).
By Lemma 5, \(|g(S'_k) - k|\leq 6 \times 10^{14}\).
Construct \(A\) as in Lemma 7, and for \(i=1,2,\dots,|A|\), let the new \(S_k\) be the string obtained by appending \(T_{A_i}\) (or \(T'_{A_i}\)) to the end of \(S_k\); then it satisfies \(g(S_k)=k\).
By Lemma 7, \(|S_k| \leq 48^2+8 \times 2590=23024\). By appending an appropriate number of copies of \(T_1\) to the end of \(S_k\), we can make a string from which every integer between \(L\) and \(R\) whose remainder when divided by \(48\) equals that of \(k\) is generable.
By concatenating all the strings obtained this way for \(k=L,L+1,\dots,\min(R,L+47)\) (ignoring those for which \(S_k\) does not exist), we can make a string from which every \(k\) is generable, except those for which no string can generate them.
Since
\(48 \times 23024+8 \times 10^5 = 1905152 \leq 2 \times 10^6\),
the length of this string can be kept at most \(2 \times 10^6\).
The latter part of finding \(l,r\) can also be done with appropriate handling.