8
$\begingroup$

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:

enter image description here

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 $$
enter image description here

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\}}$:

enter image description here

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$$

enter image description here

Moreover, the author asks also the question Is this a permutation of the natural numbers?

$\endgroup$
  • 2
    $\begingroup$ This is an interesting question overall, but I don't think there's any connection to primes or $\phi(n)$ at all. $\endgroup$ – Greg Martin Aug 17 at 2:24
  • 1
    $\begingroup$ I'm curious too about a generalized version of this sequence: oeis.org/A300002. $\endgroup$ – Peter Kagey Aug 17 at 4:41
  • $\begingroup$ @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. $\endgroup$ – Sebastien Palcoux Aug 17 at 18:09
  • $\begingroup$ why no three collinear points and no 3-progression are the same? $\endgroup$ – Fedor Petrov Aug 18 at 11:24
  • 1
    $\begingroup$ @FedorPetrov: Yes! In fact, this blunder led me to the current question. $\endgroup$ – Sebastien Palcoux Aug 18 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.