Let $u_n$ be the sequence lexicographically first among the sequences of nonnegative integers with graphs without collinear three points (as for $a_n=n^2$ or $b_n=2^n$). It is a variation of that one.
We can find the terms with a kind of Sieve of Eratosthenes:
The above animation reveals the first terms of this sequence:
$$ 0,0,1,1,4,3,8,2,2,5,7,4,5,8 $$
Obviously, an integer appears at most two times in this sequence.
Question: Does each nonnegative integer appear in this sequence? Exactly two times?
By searching the first terms in OEIS, we are lucky to find A236266 (due to Alois P. Heinz, 2014):
$$ 0, 0, 1, 1, 4, 3, 8, 2, 2, 5, 7, 4, 5, 8, 16, 3, 7, 14, 12, 23, 16, 12, 25, 31, 13, 6, 11, 28, 11, \dots $$
This sequence leads to many other possible questions like the existence of a link with
- the Euler's totient function (because their graph look alike),
- the prime numbers (because their finding process are similar: "Sieve of Eratosthenes"-like).
We could also ask about
- bounds: $u_n \in [n/10,5n/4]$?
- the gaps observed in the graph: Is there $\alpha<1$ such that $$u_n \not \in [\alpha n,n] \cup [\alpha n/2,n/2] \cup [\alpha n/4,n/4] \cup [\alpha 3n/4,3n/4] \cup \cdots \ ?$$ at least for each component of this union and $n$ large enough?
- What would be the exact value of $\alpha$? or at least a good approximation? $\alpha \sim 0.9$?
Following the comment of Peter Kagey, here is a huge generalization of the above sequence and of the main question.
Let $A$ be a subset of $\mathbb{Z}_{\ge 0}$, and consider the sequence $S_A$ which is the lexicographically first sequence of positive integers such that no $k+2$ points fall on any polynomial of degree $≤k$, for any $k \in A$. Then the sequence of Peter Kagey (A300002) is $S_{\mathbb{Z}_{\ge 0}}$, the above plus one is $S_{\{1\}}$ and $S_{\{0 \}}$ is the sequence of natural numbers.
For any nonempty subset $A \subset \mathbb{Z}_{\ge 0}$:
Generalized question: Is it true that any positive number appears exactly $\min(A)+1$ times in $S_A$?
In particular, if $0 \in A$: Is $S_A$ a permutation of the natural numbers?
Bonus Question: Is it true that $S_A = S_B$ if and only if $A=B$?
Let us compute the first terms of the sequence $S_{\{0,1\}}$:
This animation reveals the first terms: $1, 2, 4, 3, 6, 5, 9, 12$. They are the same in $S_{\mathbb{Z}_{\ge 0}}$ (A300002), except the last one which is $16$ (instead of $12$), so $S_{\{0,1\}} \neq S_{\mathbb{Z}_{\ge 0}}$ (see Bonus Question above).
By searching them on OEIS, we find A231334 (Paul Tek, 2013): $$ 1, 2, 4, 3, 6, 5, 9, 12, 7, 14, 13, 8, 23, 17, 18, 22, 10, 15, 11, 28, 19, 16, 20, 29, 32, 44, 35, \dots$$
Moreover, the author asks also the question Is this a permutation of the natural numbers?
