24
$\begingroup$

There exists a formula for the $n$th term of this sequence A002024 from the OEIS ("$n$ appears $n$ times") $$1, 2, 2, 3, 3, 3, 4, 4 ,4, 4, 5...$$ which is $$\left \lfloor \frac {1+\sqrt{1+8n}}{2} \right \rfloor.$$

Is there a better formula for the $n$th term? A formula that isn't a 'magic' one that just happens to work but one that comes from a well-founded observation. Preferably one not using the floor function. I also have suspicions about the sustainability of the above formula as I feel with very $n$ it may not function properly.

$\endgroup$
5
  • 15
    $\begingroup$ As a computer scientist, I like that this sequence starts from $0$. :) $\endgroup$ – user856 Jul 30 '13 at 18:14
  • 2
    $\begingroup$ possible duplicate of Finding the "triangular root" of a number. $\endgroup$ – MJD Apr 12 '14 at 13:02
  • $\begingroup$ @MJD No it isn't. $\endgroup$ – Ali Caglayan Apr 12 '14 at 19:44
  • 1
    $\begingroup$ I've retracted my close vote, but I still think you should look at this other question, which is almost exactly the same as yours. $\endgroup$ – MJD Apr 12 '14 at 20:58
  • $\begingroup$ @MJD I have read the other post. My question is about the sequence and why the formula works and approaches the topic at a different angle as aposed to using the formula to extract the n. There are many similar looking but slightly different questions however I think it would be in best interest to keep this one. Thank you for your concern your effort is appreciated. $\endgroup$ – Ali Caglayan Apr 12 '14 at 22:12
24
$\begingroup$

I don't think there is a better formula, as it is based on two basic observations:

  • $\displaystyle \sum_{k=0}^{m-1}k=\frac{m(m-1)}{2}$.

  • $\displaystyle \frac{m(m-1)}{2}=n$ with $m>0$ $\Longrightarrow$ $\displaystyle m=\frac{1+\sqrt{1+8n}}{2}$.


Further explanations:

We have a sequence $\{a_n\}$ such that $a_0=1$, $a_1=a_2=2$, $a_3=a_4=a_5=3$, etc, and we want to have a general formula for $a_n$.

To obtain it, let us first ask a somewhat inverse question: for which $n$'s $a_n$ will be equal to a given number $m$? Here we will use the first formula: the numbers from $1$ to $m-1$ occupy $1+2+3+\ldots+(m-1)=m(m-1)/2$ first positions in the sequence. Therefore the number $m$ will correspond to $m$ values of $n$ explicitly given by $$n=\frac{m(m-1)}{2}+1,\frac{m(m-1)}{2}+2,\ldots,\frac{m(m-1)}{2}+m\tag{1}$$ Now we come back to our initial question. Given $n$, (1) implies that $a_n$ will be equal to the largest integer $m$ such that $\displaystyle \frac{m(m-1)}{2}\leq n$. This largest integer is obtained by solving the equation $\displaystyle\frac{m(m-1)}{2}= n$ for $m$ (here we use the 2nd formula) and taking the integer part of the solution.

$\endgroup$
3
  • $\begingroup$ Could you please explain further on how you deduce this result? $\endgroup$ – Ali Caglayan Jul 30 '13 at 16:22
  • $\begingroup$ @Alizter I've tried to add some explanations. Hope now it's more clear. $\endgroup$ – Start wearing purple Jul 30 '13 at 17:09
  • $\begingroup$ when m(m-1)/2 =n??? $\endgroup$ – ahmed allam Jun 23 '20 at 9:17
16
$\begingroup$

There is a better formula: $$a_n = \operatorname{round}{\sqrt {2n}} $$

Where $\operatorname{round}$ means to round to the nearest integer, or if you prefer, $\operatorname{round}{x} = \left\lfloor x+\frac12\right\rfloor$

$\endgroup$
3
  • 7
    $\begingroup$ Nice. How did you derive it? $\endgroup$ – Memming Apr 12 '14 at 20:45
  • 1
    $\begingroup$ @Memming I do believe that one may use $$\frac{n^2}2<\frac{n(n+1)}2<\frac{(n+1)^2}2$$ $\endgroup$ – Simply Beautiful Art Feb 8 '17 at 12:29
  • $\begingroup$ Just to note, this answer requires the sequence start with n=1, whereas the formula in the question requires the sequence start with n=0. $\endgroup$ – Stacey Aug 5 '20 at 20:23
3
$\begingroup$

You got nice answers already, so I'll just address the "sustainability" issue.

The formula you're discussing uses a real (non-integer) arithmetic to compute the integer solution of an integer problem. Theoretically, it is possible that at some point the square root is computed with a minor error and that the obtained solution is wrong (it may depend on processor, as well as some other factors).

To be absolutely certain that your program gives a correct solution (of course, as long as $n$ in the range of integers), you'll have to stick to the integer arithmetic. However, this means computing (but not remembering) the elements of your sequence, up to the $n$-th one. I don't think there is an integer-arithmetic formula that would save you from this.

A drawback? The speed, obviously, as such algorithm performs in $O(n)$ time, while the formula above computes in the constant time. This is significant, since the error should not occur for any reasonably small $n$.

All in all, I'd go with the above formula, as I'm fairly certain that this would not happen, since the square root would not allow lose $1$ as the significant digit, and I see no other threats, assuming that the processor is not buggy (i.e., it doesn't compute $\sqrt{x}$ to have a smaller integer part than the actual $\sqrt{x}$).

If it's absolutely crucial to get correct results for really large $n$, you might want to do some error estimate and see if the formula can actually produce wrong results. Again, I'm fairly certain that it can not.

$\endgroup$
7
  • $\begingroup$ Thank you for your contribution on addressing the accuracy situation. The reason that I have suspicions with it was because of the floor function as it implies that without it the answer is not accurate. And if it is relying on rounding down then the decimal fraction could have a possibility of skipping integer bounds. $\endgroup$ – Ali Caglayan Jul 30 '13 at 17:55
  • $\begingroup$ Yes, that is a general problem. However, your formula is very specific. So, when can the error occur? The answer is: when $1+\sqrt{1+8n}$ is computed as $<2x$ for some $x \in \mathbb{N}$, while in reality it should be $\ge 2x$. One obvious reason is that $\sqrt{8n}$ is computed as $< 2x-1$ instead of $\ge 2x$, but I don't think a square root gets you this kind of an error on modern computers (I wouldn't even expect the old ones to miss that much). $\endgroup$ – Vedran Šego Jul 30 '13 at 18:46
  • 1
    $\begingroup$ You can calculate the integer square root of $1+8n$, that is $\left\lfloor\sqrt{1+8n}\right\rfloor$, using only integer operations, in $O(\sqrt n)$ time, and I think probably in $O(\log n)$ time. $\endgroup$ – MJD Jul 30 '13 at 18:46
  • $\begingroup$ The less obvious reason would be for $1+\sqrt{1+8n}$ to be computed the same value as $\sqrt{1+8n}$, i.e., that this expression loses the least significant integer digit. However, in 64-bit arithmetic, $8n+1$ would have 64 bits, i.e., around $3 \cdot 6 + 1 = 19$ digits. Taking a square root, you are left with approximately $10$ integer digits, while the double arithmetic has around $16$ significant digits, so this case should also present no problems. $\endgroup$ – Vedran Šego Jul 30 '13 at 18:49
  • $\begingroup$ Of course, you can listen to MJD's idea, sticking only to the integer arithmetic to keep it safer, but - as I explained - I see no place where the ordinary double precision arithmetic would fail in this case. The emphasis being on this case, because - generally - computing integer stuff with the real arithmetic can cause trouble. $\endgroup$ – Vedran Šego Jul 30 '13 at 18:51
0
$\begingroup$

As mentioned in the OEIS, the sequence is recursively given by $$\begin{cases} a(0) &= 1\\ a(1) &= 2\\ a(n+1) &= a\bigl( n+1-a(n) \bigr) + 1, \end{cases}$$ which is a better formula in the sense that it is a simpler construction from the viewpoint of logic.

If you arrange the terms of the series in the following way, you can get a feel for how the formula works:

a(01)⬅a(03)⬅a(06)⬅a(10)⬅a(15)
⬆
a(02)⬅a(05)⬅a(09)⬅a(14)
⬆
a(04)⬅a(08)⬅a(13)
⬆
a(07)⬅a(12)
⬆
a(11)

i.e.

1⬅2⬅3⬅4⬅5
⬆
2⬅3⬅4⬅5
⬆
3⬅4⬅5
⬆
4⬅5
⬆
5

An arrow from the $(n+1)$th position to the $k$th position indicates that the value of $a(n+1)$ is obtained by applying $a$ to $k = n + 1 - a(n)$ and adding $1$.

A proof showing that the formula works:

Let $T_n$ denote the $n$th triangular number: $$\begin{cases} T_0 &= 0\\ T_n &= T_{n-1}+n. \end{cases}$$ It is obvious that $$\forall k \, \forall n : \; T_n + 1 \leq k \leq T_{n+1} \; \rightarrow \; k\text{th term} = n+1$$ defines our sequence. We show that the function $a$ indeed generates this sequence.

We argue by induction on $n_0$: Suppose, the function $a$ generates the sequence up to $T_{n_0}$ for some positive integer $n_0$, meaning that $$\forall k \, \forall n \leq n_0 - 1 : \; T_n + 1 \leq k \leq T_{n+1} \; \rightarrow \; a(k) = n+1 \qquad (*)$$ holds. By induction on $m$, we prove $$a(T_{n_0} + m) = n_0 + 1 \quad \text{if } 1 \leq m \leq n_0 + 1.$$ Base case ($m = 1$): \begin{align*} a(T_{n_0}+1) &= a\bigl( T_{n_0}+1-a(T_{n_0}) \bigr)+1 \overset{(*)}{=} a(T_{n_0}+1-n_0)+1\\ &= a(T_{n_0-1}+n_0+1-n_0)+1 = a(T_{n_0-1}+1)+1 \overset{(*)}{=} n_0+1. \end{align*} Induction hypothesis $(\mathrm{IH})$: Suppose $a(T_{n_0} + m) = n_0 + 1$ holds for some $m$ with $1 \leq m \leq n_0 + 1$.

Inductive step: \begin{align*} T_{n_0} + m + 1 - a(T_{n_0}+m) &\overset{\mathrm{(IH)}}{=} T_{n_0} + m + 1 - (n_0+1)\\ &= T_{n_0} - n_0 + m = T_{n_0-1} + m, \end{align*} therefore \begin{align*} a(T_{n_0} + m + 1) &= a\bigl( T_{n_0} + m + 1 - a(T_{n_0}+ m) \bigr) + 1\\ &= a(T_{n_0-1} + m), \end{align*} so \begin{align*} a(T_{n_0} + m + 1) &= a(T_{n_0-1} + m)\\ &\overset{(*)}{=} n_0 + 1 \quad \text{if } 1 \leq m+1 \leq n_0+1. \end{align*} We have now completed both inductions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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