# algebraic expression for a counting function

consider a 2d "counting" function given by the $(x,y)$ points/pairs:

(1,1),
(2,2),(3,2),
(4,3),(5,3),(6,3),
(7,4),(8,4),(9,4),(10,4),
(11,5),(12,5),(13,5),(14,5),(15,5), ...

ie $x$ increments in each pair, $y$ increments on each row, and there are $n+1$ pairs on each subsequent row.

I did a curve fit of this function and got a close fit to an equation in the form $y=ax ^ b + c$. is there an exact or closed-form formula? have some experience with generating functions/recurrence relations with integer coefficients but this seems to be different. (it does seem to be similar to the Fibonacci sequence...) is there a general theory for generating functions for integer equations but with noninteger (rational, irrational) coefficients? what is a good ref on that?

-
It might help to plot the function. It's not surprising that you could get a fit of the form $ax^b+c$, given the shape of the curve. Accuracy of such a fit, however, is not an indication that there is some underlying structural relationship. –  Arkamis Dec 5 '12 at 19:09
yes know what overfitting is. did plot it and the error/delta with the curve fit (which looks remarkable) & it seems there may be an exact fit with an equation similar to form $\lceil ax^b + c \rceil$ .. looking for a paper/book/general theory etc in the area.. –  vzn Dec 5 '12 at 19:13
Ok, sorry for the incorrect answer before. I've added a correct answer (I believe). –  Arkamis Dec 5 '12 at 19:54

You can write this exactly in terms of $n$, where $n$ is the number of times $x$ has been incremented:

$$y = n.$$

You can compute $n$ in terms of $x$ as

$$n =\left\lfloor \frac{-1+\sqrt{1+8(x-1/2)}}{2} \right\rfloor + 1$$

Since the value of $y$ is simply the index of its "row", we simply need to figure out what row it's in based on its corresponding $x$ value. Notice that for the first number in the $n$th row, there are $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ values preceding it in the sequence.

So we essentially need to compute the partition to which $x$ belongs. Note that

$$\frac{n(n+1)}{2} < x \le \frac{(n+1)(n+2)}{2}.$$

Solve

$$n^2+n-2x = 0.$$

Since this parabola is opening upwards, the floor of the largest $n$ (in magnitude) that solves this should give us the lower bound of the inequality above.

$$n =\max \left|\left\lfloor \frac{-1\pm \sqrt{1+8x}}{2} \right\rfloor\right|$$

Note, however, that the zeros are going to be shifted by the $-1/2$. To account for this, let's induce this shift in $x$ to make things symmetric, so it doesn't matter which sign we use in the quadratic formula:

$$n =\left\lfloor \frac{-1+\sqrt{1+8(x-1/2)}}{2} \right\rfloor$$

However, to compute the $n$ that we need, we must increment by 1 (remember, solving for $n$ gives us the lower bound, which is the index of the previous row). Therefore:

$$n =\left\lfloor \frac{-1+\sqrt{1+8(x-1/2)}}{2} \right\rfloor + 1.$$

To respond to your reference request, any elementary number theory book should include problems such as this.

-