I remember that I have seen a similar problem to this one here: The set of natural numbers that don't belong to a set (which is a duplicate of $m$ doesn't come in the sequence $a_n=[n+\sqrt{n}+\frac{1}{2}]$ iff m is a perfect square). If my memory serves me right, that problem was about a sequence excluding triangular numbers, and the sequence was given by something of the form $n\mapsto\left\lfloor n+\sqrt{an+b}+c\right\rfloor$ for some rational numbers $a,b,c$. Does anybody know anything about such problems (such as where these problems are form, or whether there are other similar problems)? I believe that I have also seen other similar problems. Hence, I am trying to establish something akin to a quadratic version of Beatty's Theorem.
In this post, $\mathbb{N}$ denotes the set of positive integers (i.e., $0\notin\mathbb{N}$). Let $p:\mathbb{N}\to\mathbb{N}$ be a near-quadratic function, that is, $p$ is a strictly increasing function given by $$p(n):=\left\lfloor\alpha n^2+\beta n+\gamma\right\rfloor \tag{*}$$ for all $n\in\mathbb{N}$, where $\alpha,\beta,\gamma\in\mathbb{R}$ with $\alpha>0$ which is called the leading coefficient of $p$. (Note that, if $\beta>1-3\alpha$, then it is guaranteed that $p$ is strictly increasing.) Also, an almost-linear function $q:\mathbb{N}\to\mathbb{N}$ is defined as $$q(n):=\left\lfloor n+\sqrt{an+b}+c\right\rfloor\tag{**}$$ for all $n\in\mathbb{N}$, where $a,b,c\in\mathbb{R}$ and $a>0$. We say that two functions $p:\mathbb{N}\to\mathbb{N}$ and $q:\mathbb{N}\to\mathbb{N}$ are complementary functions iff $$\big\{p(n)\,\boldsymbol{\big{|}}\,n\in\mathbb{N}\big\}\text{ and }\big\{q(n)\,\boldsymbol{\big{|}}\,n\in\mathbb{N}\big\}$$ form a partition of the set of positive integers $\mathbb{N}$.
Question: What are all the near-quadratic functions $p:\mathbb{N}\to\mathbb{N}$ such that there exists a complementary function $q:\mathbb{N}\to\mathbb{N}$ which is almost-linear? What is an example of a near-quadratic function $p$ with a complementary function $q$ such that the leading coefficient $\alpha$ of $p$ is irrational? Which $\alpha>0$ can be the leading coefficient of a near-quadratic function $p$ with a complementary function $q$?
According to Jyrki Lahtonen's suggestion, it can be shown that, if (*) and (**) are complementary, then $$a\alpha=1\,.$$ From this result, I have recovered a sequence skipping triangular numbers: $n\mapsto \left\lfloor n+\sqrt{2n}+\frac{1}{2}\right\rfloor$. I have not proven this claim, but I am positive it is correct.
Partial Answer: It appears that, for a fixed $k\in\mathbb{N}$, if $p:\mathbb{N}\to\mathbb{N}$ is given by $$p(n)=\left\lfloor\dfrac{k}{2}n^2-\frac{(k-2)}{2}n+\frac{k-1}{8}\right\rfloor$$ for all $n\in\mathbb{N}$, then $q:\mathbb{N}\to\mathbb{N}$ defined via$$q(n)=\left\lfloor n+\sqrt{\frac{2}{k}n}+\frac{1}{2}\right\rfloor$$ for all $n\in\mathbb{N}$ is a complementary function to $p$.
It also appears that, for a fixed $k\in\mathbb{N}$, if $p:\mathbb{N}\to\mathbb{N}$ is given by $$p(n):=\left\lfloor\frac{1}{k}n^2+\frac{(k-1)}{k}n\right\rfloor$$ for all $n\in\mathbb{N}$, then $q:\mathbb{N}\to\mathbb{N}$ defined via $$q(n):=\left\lfloor n+\sqrt{kn}+\frac{1}{2}\right\rfloor$$ for all $n\in\mathbb{N}$ is complementary to $p$. I have not yet tried to prove any of these assertions.