Existence of closed form formulas for integer sequences

Question

Suppose that

z x y
————————
0 1 0
1 2 0
2 2 1
3 3 0
4 3 1
5 3 2
6 4 0
7 4 1
8 4 2
9 4 3
. . .
. . .
. . .
n xn yn

the z column is from 0 to n, and the x and y columns are the corresponding values. Do equations exist that can be used to derive the xn and yn values based on n (n can be arbitrary value)?

Answer 1

$\newcommand{\round}{\operatorname{round}}$

The formula given by @Leox

$$x_n=\underbrace{\round(\sqrt{2n})}_N$$

is exact. I will use it in the following closed-form expression I propose for the second sequence:

$$y_{n-2}=n-1- \frac12 \ \underbrace{\round(\sqrt{2n})}_N \times (\underbrace{\round(\sqrt{2n})}_N-1) \tag{1}$$

(valid for $n \ge 2$).

Explanation: one recognizes in (1) the classical formula $S=\frac12 N (N-1)$ for the sum of the $N-1$ first integers ; indeed the zeros in sequence $y_n$ "uprise" at positions $1, 1+2, 1+2+3, etc.$ ; subtracting $S$ at the right position and with the right amount allows the recurrent "zero-settings".

Edit: in fact, I just decovered that sequence $x_n$ is known in OEIS with interesting comments, in particular the fact that "For any $n \ge 0$, $x_{n+1}$ is the least integer $m$ such that $m(m+1)/2$ is larger than $n$." making the connection with the second sequence: it is another way to express the formula (1).

Answer 2

Based on the comments/answers, I wrote the following CXX code

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main()
{
    const int Dsize = 1e5;

    vector<int> n, x_true, x_estimated, y_true, y_estimated;
    n.reserve(Dsize);
    x_true.reserve(Dsize);
    x_estimated.reserve(Dsize);
    y_true.reserve(Dsize);
    y_estimated.reserve(Dsize);

    for (int i = 0;; ++i)
    {
        if (n.size() == Dsize)
            break;

        n.push_back(i);

        int x_est = floor((pow(2 * (i + 1), 0.5) + 1 / 2.0));

        x_estimated.push_back(x_est);

        y_estimated.push_back(i - 0.5 * x_est * (x_est - 1));

        if (x_true.size() < Dsize)
            for (int j = 0; j < i + 1; ++j)
            {
                if (x_true.size() == Dsize)
                    break;

                x_true.push_back(i + 1);
            }

        if (y_true.size() < Dsize)
            for (int j = 0; j < i + 1; ++j)
            {
                if (y_true.size() == Dsize)
                    break;

                y_true.push_back(j);
            }
    }

    for (int i = 0; i < Dsize; ++i)
    {
        if (x_estimated[i] - x_true[i] != 0)
        {
            cout << "n = " << i << endl;
            cout << "wrong estimation of x\n";
            exit(0);
        }

        if (y_estimated[i] - y_true[i] != 0)
        {
            cout << "n = " << i << endl;
            cout << "wrong estimation of y\n";
            exit(0);
        }
        //cout << n[i] << ",\t" << x_estimated[i] << ",\t" << x_true[i] << ",\t" << y_estimated[i] << ",\t" << y_true[i]<< endl;
    }
    return 0;
};

The above CXX code was used to verify the closed form formulas for integer sequences. The estimation of x is $$x_{est}=floor(\sqrt{2*(n + 1)} + 0.5),$$ and the estimation of y is $$y_{est}=n - 0.5 * x_{est} * (x_{est} - 1).$$ The formulas here is slightly different, but the principle behind is the same (see the above accepted answer and comments for more details).

The true values ($x_{true}$ and $y_{true}$) were assigned in a for loop, which can be understood with little thought.

I tested the formulas in the case of n ranging from 0 to $1e5$. The result showed that the formulas hold true.