Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.