# On the first sequence without collinear triple

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).

• 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?

• This is an interesting question overall, but I don't think there's any connection to primes or $\phi(n)$ at all. – Greg Martin Aug 17 '19 at 2:24
• I'm curious too about a generalized version of this sequence: oeis.org/A300002. – Peter Kagey Aug 17 '19 at 4:41
• @PeterKagey: I just shifted my comment to the post, explaining how your conjecture (written in your OEIS post) and my question are two particular cases of a generalized question. – Sebastien Palcoux Aug 17 '19 at 18:09
• why no three collinear points and no 3-progression are the same? – Fedor Petrov Aug 18 '19 at 11:24
• @FedorPetrov: Yes! In fact, this blunder led me to the current question. – Sebastien Palcoux Aug 18 '19 at 14:45