3
$\begingroup$

Let the sequence be $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...,n, n, n, n, ..., n...$. The function $f(k)$ will return the $k$th term of this sequence. Using properties of this sequence, it is not too hard to see that if $f(r)=n$, then $r\in\{\frac{n(n-1)}{2}+1+k | k\in\mathbb{W}\}$.

The following questions arise out of just curiosity. On a graph, this function looks like many things. My first guess was that it was some sort of logarithm (idea later revised), but my immediate question was: for domain $[1, p]$, what logarithm base, denoted $b$, would provide the best approximation? Around $2$? My second question is: would a better approximation be a parabola/hyperbola. The sequence slows down very quickly, so instead of a parabola, could it be some sort of flipped $x^6$ or higher even power?

$\endgroup$
3
  • 2
    $\begingroup$ Well, you've already noticed that $f(\frac{n(n-1)}{2} + 1) = n$, and $\frac{n(n-1)}{2}+1$ is quadratic in $n$, so... $\endgroup$ Apr 3 at 0:21
  • $\begingroup$ What is $~\Bbb{W}~?$ $\endgroup$ Apr 3 at 0:53
  • 1
    $\begingroup$ The OEIS sequence A002024 entry has much information about this sequence. This question seems to be a duplicate of math.stackexchange.com/q/455511. $\endgroup$
    – Somos
    Apr 3 at 1:08

1 Answer 1

4
$\begingroup$

Let's use the notation $T_n$ for the $n$th triangle number: $$ T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}. $$

Your (correct) observation amounts to the fact that $f(k) = n$ precisely for those $k$ satisfying $T_{n-1} < k \leq T_n$. We can rearrange these inequalities to solve for $n$: \begin{array}{rcccl} \displaystyle\frac{n(n-1)}{2} &<& k &\leq{}& \displaystyle\frac{n(n+1)}{2} \\[2pt] n^2 - n &<& 2k &\leq& n^2 + n \\ 4n^2 - 4n + 1 &<& 8k + 1 &\leq& 4n^2 + 4n + 1 \\ (2n - 1)^2 &<& 8k + 1 &\leq& (2n + 1)^2 \\ 2n - 1 &<& \sqrt{8k + 1} &\leq& 2n + 1 \\ n - 1 &<& \displaystyle\frac{-1 + \sqrt{8k + 1}}{2} &\leq& n \end{array}

So, we can use the ceiling function (rounding up to the nearest integer) to write $$ f(k) = \Biggl\lceil \frac{-1 + \sqrt{8k + 1}}{2} \Biggr\rceil $$

Since $k \sim n^2$, this inverted function is on the order $n \sim k^{1/2}$, as expected. This formula also gives nice bounds for the $n$th term that are half parabolas opening to the right: $$ \frac{-1 + \sqrt{8k + 1}}{2} \leq f(k) \leq \frac{1 + \sqrt{8k - 7}}{2} $$

Sequence with bounding curves.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .