Murimuri Sequence

The equation $ax^2+bx+c=0$ has a real root whenever its discriminant $b^2-4ac$ is nonnegative. In particular, this is always true when $ac\leq0$.

We therefore arrange the sequence so that values two positions apart have opposite signs. Use the following sign pattern:

$$0,+,-,-,+,+,-,-,+,+,\ldots$$

After the initial zero, the length-$4$ pattern $+,-,-,+$ repeats. Two positions apart in this pattern always have opposite signs, while a pair involving the first value has product zero.

Among the remaining $2N$ positions, exactly $N$ are positive and $N$ are negative. Put $1,2,\ldots,N$ into the positive positions and $-1,-2,\dots ,-$ into the negative positions. Thus every integer from to is used exactly once.

For any three consecutive values $a,b,c$, the construction gives $ac\leq0$. Hence

$$b^2-4ac\geq b^2\geq0,$$

so every required equation has at least one real root.

The time complexity is $O(N)$, equal to the output size, and the additional space complexity is $O(1)$.

Solution written by GPT6