Suppose the positive integers are partitioned as $\left\{\left\{1\right\},\left\{2,3\right\},\left\{4,5,6\right\},\ldots\right\}.$ Call the elements of the partition $A_{n}$ where $A_{n}$ contains $n$ integers. Then, what is the sum of the integers in $A_{n}$? Call these sums $S_{n}.$
We can calculate a few sums easily by hand: $S_{1}=1,$ $S_{2}=5,$ $S_{3}=15,$ $S_{4}=34,$ $S_{5}=65,$ and $S_{6}=111.$
I actually did these in my head! But how? Well, with a little trick from our friend Gauss!
Recall the story of a young Gauss who surprised his primary school teacher by solving a problem given as busy work in seconds. He was asked to add the integers from 1 to 100 together and figured out rather quickly that this could be rephrased as a multiplication problem by pairing the numbers on either end together, 1 with 100, 2 with 99, and so on, giving 50 copies of 101, hence a sum of 5050.
However, when $n$ is odd, the number in the middle won’t have an integer to pair with. While this still works out and gives the correct closed form expression in the end, it’s always nicer to have a single trick that works in every case. To make this trick work even for odd $n,$ we can pair the integers by taking two copies of the sum, like so:
$$n + \left(n-1\right) + \cdots + 2 + 1$$
$$1 + 2 + \cdots + \left(n-1\right) + n$$
Adding these two expressions together by pairing an integer on top with the one directly below gives $n$ copies of $n+1$, giving a total of $n\left(n+1\right)$. Since this is actually twice the sum of the first $n$ positive integers, we divide by 2 to get $\frac{n\left(n+1\right)}{2}$ as the sum of the first $n$ positive integers. This is called the $n$th triangular number, $t_{n}.$
Now let’s apply this trick to our problem. We’ll start with a specific case, $n = 10.$
First of all, let’s just note (read: the reader should figure out) that $A_{10} = \left\lbrace 46, 47, 48, 49, 50, 51, 52, 53, 54, 55 \right\rbrace.$ We will write out $S_{10}$ in two different orders.
$$S_{10} = 46 + 47 + 48 + 49 + 50 + 51 + 52 + 53 + 54 + 55$$
$$S_{10} = 55 + 54 + 53 + 52 + 51 + 50 + 49 + 48 + 47 + 46$$
As we learned from Gauss, let’s pair up summands from each column (46 with 55, 47 with 54, etc.) and add them together. Since we’re adding two copies of $S_{10}$ together, we have $$2S_{10} = 101 + 101 + 101 + 101 + 101 + 101 + 101 + 101 + 101 + 101 = 10\cdot 101,$$ and so $S_{10} = \frac{10\cdot 101}{2} = 505.$
We could have also written this as $S_{10} = \frac{10\cdot\left(10^{2} + 1\right)}{2},$ and the examples I wrote above could also be written in a similar form, which suggests that $S_{n} = \frac{n\left(n^{2} + 1\right)}{2}$ may be the closed form we’re looking for. Let’s prove it!
Proposition. Partition the positive integers as $\left\{\left\{1\right\},\left\{2,3\right\},\left\{4,5,6\right\},\ldots\right\}.$ For each $n\geq 1,$ let $A_{n}$ be the member of this partition with $n$ elements and let $S_{n}$ be the sum of the elements of $A_{n}.$ Then, $$S_{n} = \frac{n\left(n^{2}+1\right)}{2}.$$
Proof.
When $n = 1,$ the result is true, since $1 = \frac{1\cdot\left(1^{2} + 1\right)}{2}.$
For $n\geq 2,$ let $\ell_{n-1}$ be the largest element of $A_{n-1}.$ Then, the smallest element of $A_{n}$ is $\ell_{n-1} + 1,$ and so we can write $S_{n}$ in these two orders:
$$S_{n} = \left(\ell_{n-1} + n\right) + \cdots + \left(\ell_{n-1}+1\right)$$
$$S_{n} = \left(\ell_{n-1}+1\right) + \cdots + \left(\ell_{n-1} + n\right)$$
After pairing summands on each column, we see that that we have precisely $n$ copies of $2\ell_{n-1}$ and $n$ copies of $n+1,$ giving $2S_{n} = 2n \ell_{n-1} + n\left(n+1\right)$, and so $S_{n} = n\ell_{n-1} + \frac{n\left(n+1\right)}{2} = n\ell_{n-1} + t_{n}$.
To find a closed form for $\ell_{n-1}$, note that $\ell_{n}$ satisfies the recurrence $\ell_{n} = \ell_{n-1} + n$ with $\ell_{1} = 1$. This recurrence corresponds to adding the first $n$ positive integers, which means $\ell_{n-1} = t_{n-1} = \frac{n\left(n-1\right)}{2}$.
Therefore, $$S_{n} = n t_{n-1} + t_{n} = \frac{n^{2}\left(n-1\right)}{2} + \frac{n\left(n+1\right)}{2} = \frac{n^{3} – n^{2} + n^{2} + n}{2} = \frac{n\left(n^{2}+1\right)}{2},$$ as required.
QED
Note that a little trial and error was needed to figure out that we should frame our sum around the largest element of the previous partition element. To see why, try running the proof using $\ell_{n}$ as the smallest element of $A_{n}$ and see where the analogy to the original sum of integers problem breaks.
This also makes it easier to figure out where to start each partition element. We can now see, for example, that $A_{1337}$ starts at $\frac{1337\cdot1336}{2} + 1 = 893117$ and, therefore, ends at 894453 with a sum of $S_{1337} = 1194990545$.