# Row-sum for an integer triangle w/o brute force

The positive integers are arranged in increasing order in a triangle, as shown*. Each row contains one more number than the previous row. The sum of the numbers in the row that contains the number 400 is (the question gives a variety of options).

*Here is my best representation of the picture of the triangle:

         1
2     3
4     5     6
7     8     9    10 ...


I used a brute force approach in C++:

#include <iostream>
#include <vector>

using namespace std;

vector< int > line;

int main (int argc, const char * argv[]) {
int i = 0; //The current number.
int number_in_row = 1; //Number of numbers contained in a row of the triangle.
int row_counter = 0; //Keeps track of what element in the row I'm on.
bool row_with_400 = false; //Checks to see if I reached the row that has the number 400 in it.
bool did_finish_row = false; //Checks to see if I got all the elements from the 400th row.
bool check = false; //Works with did_finish_row.
while (true) {
i++; //Keep incrementing through the numbers
if (i == 400) { //Check if i is = to 400 and then indicate it is on the row with 400.
row_with_400 = true;
check = true; //Used to make sure that the thing finishes the row then breaks out of the loop.
}
line.push_back(i); //Put the contents of the line into a vector.
row_counter++; //Indicate you are moving to the next element in the row in the triangle
if (row_counter == number_in_row) { //Checks to see if I got to end of row
row_counter = 0;
number_in_row++;
if (check == true) { //If on row with 400 indicate that I finished storing all those elements.
did_finish_row = true;
}
if (did_finish_row != true) { //Clear unless I am on the row with 400.
line.clear();
}
}
if (row_with_400 == true && did_finish_row == true) { //Break if I finished the row with 400.
break;
}
}
int final_number = 0;

for (vector<int>::iterator i = line.begin(); i != line.end(); ++i ) {
final_number = final_number + *i; //Add up all the elements of the row with 400.
}

cout << final_number; //Print it out.

}


Basically, I kept track of which row I was on, got to the row with 400 and added up the contents with that. Look at the comments in the code to get a better sense of what I did.

First off I get the answer to be: 10990. Is that right? Second of all, I got this from a sheet that didn't allow people to program. Is there a less brute force method, something that needs only pen or pencil? Could I have a hint at least as how to do that?

• Well, first of all, you can find the expressions for the first and the last number in n-th row. – Nurdin Takenov Dec 6 '11 at 7:04
• Yes, $10990$ is correct. Takes a lot less time than writing a program. – André Nicolas Dec 6 '11 at 7:07
• First we want to identify the row. Say it is row $n$. Then $\frac{n(n+1)}{2}\ge 400$, $\frac{(n-1)(n)}{2}<400$. Could then use general procedure, but easy to see $n=28$. Last entry in row is $\frac{(28)(29)}{2}$, last in previous row is $\frac{(27)(28)}{2}$. Now use general formula. – André Nicolas Dec 6 '11 at 7:12
• @AndréNicolas: I don't get the second equation: $\frac{(n-1)(n)}{2}$... What is that doing exactly? I know the first one is summing up consecutive integers but I don't understand exactly what the slightly modified one is doing. What exactly is it doing? – Dair Dec 6 '11 at 7:20
• Our $n$ will be the smallest integer such that $n(n+1)/2 \ge 400$, so want previous sum to be $<400$. The two inequalities identify $n$. – André Nicolas Dec 6 '11 at 7:22

The $n$-th row contains $n$ numbers, so in the first $n$ rows there are $1+2+3+\cdots+n=\frac{n(n+1)}2$ numbers, and the last number in row $n$ is $\frac{n(n+1)}2$. The last number in row $n-1$ is $\frac{(n-1)n}2$, so $400$ is in row $n$ if and only if $$\frac{(n-1)n}2<400\le\frac{n(n+1)}2;$$ this is equivalent to $n(n-1)<800\le n(n+1)$ and hence to $$n^2-n<800\le n^2+n\;.$$ Clearly we’re looking for an $n$ close to $\sqrt{800}=20\sqrt2\approx 28.28$. Try $n=28$: $28\cdot29=812$, and $28\cdot27=756$, so we’re in business, with $400$ in row $28$.
The last number in row $27$ is $\frac{756}2=378$, and the last number in row $28$ is $\frac{812}2=406$, so the sum of the $28$ numbers in row $28$ is $$379+380+\cdots+406=\frac{28(379+406)}2=14\cdot 785=10,990\;.$$
The last number of the $n$th row is $\sum_{i=1}^n i = \frac{n(n+1)}{2}$. Since $\frac{27(28)}{2} = 378 < 400 < \frac{28(29)}{2} = 406$, 400 must be in the 28th row. Notice that the sum of the numbers in the $k$th row can be written as the sum of all numbers in the first $k$ rows minus the sum of all numbers in the first $(k-1)$ rows. But the sum of all numbers through the first $k$ rows is the sum of all numbers up through the last number of the $k$th row, i.e. $\sum_{i=1}^d i = \frac{d(d+1)}{2}$, where $d = \frac{k(k+1)}{2}$ is the last number of the $k$th row.
Thus the sum of all numbers in the row containing 400 (the 28th row) is $$\frac{406(407)}{2} - \frac{378(379)}{2} = 10990.$$