0
$\begingroup$

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?

  • 0
    Ok, sorry for the incorrect answer before. I've added a correct answer (I believe).2012-12-05

1 Answers 1

1

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.