Triangle Numbers Algorithm: What is it?

[FQVBSina_Jesse]

I was investigating the number of unique grid points in a Cartesian coordinate system if I were to start at a corner (say coordinate 1,1,1), and make one step in each of the three positive directions (coordinates 1,2,1; 2,1,1; and 1,1,2). Now I went from 1 point to 3 points.

I repeat the same process for the three new points and I found 6 unique new points, and then from the 6 I found 10. It turns out this 1,3,6,10 sequence (which I predict the next number is 15) is called the triangle numbers.

My question is, what is the name of the algorithm that finds the number of unique grid points in the way I did it? I knew there must be an existing pattern/equation out there but I don't know what it is called.

Thanks!

 

[jbriggs444]

My question is, what is the name of the algorithm that finds the number of unique grid points in the way I did it? I knew there must be an existing pattern/equation out there but I don't know what it is called.

You could google Triangle Number and get an answer faster than by asking the question here. Or Google "gauss sum of integers".

 

[FQVBSina_Jesse]

You could google Triangle Number and get an answer faster than by asking the question here. Or Google "gauss sum of integers".

I tried. I am looking for the specific algorithm that finds the unique grid points, and searching for Triangle Numbers gives too many mathematical theories. I will try Gauss sum when I get back. Thanks

 

[berkeman]

Google Images searches usually help me get through the clutter faster. Not sure if that helps...

 

[jbriggs444]

I tried. I am looking for the specific algorithm that finds the unique grid points, and searching for Triangle Numbers gives too many mathematical theories. I will try Gauss sum when I get back. Thanks

So you don't want the number (total count) of grid points at a given plane away from the origin. You want the sequence number associated with a given grid point in terms of x, y and z?

Off the top of my head, that should be achievable by taking the sum of x, y and z, and finding that tetrahedral number, finding the sum of x and y and finding that triangular number and then adding tetrahedral number + triangular number + z to get the result.

Tweak for off-by-one errors and scan order in populating the triangles.

 

[mfb]

You are literally producing triangles that way, and the sum of all the coordinates of the points is always 3 (starting at (1,1,1)) plus the number of steps.

You can quickly generate a list of these points if you loop over two coordinates and calculate the last one accordingly.

 

[Charles Link]

@FQVBSina The formula for your nth number is $S_n=\frac{(n+1)n}{2}$. This is because your nth number is $S_n=1+2+3+...+n$ which is the sum of an arithmetic series. The arithmetic series is a well known formula.

 

[jbriggs444]

You are literally producing triangles that way, and the sum of all the coordinates of the points is always 3 (starting at (1,1,1)) plus the number of steps.

I am not sure to whom you are responding. If it is in reference to the x,y,z algorithm that I proposed, it is not literally producing triangles. It involves evaluating one cubic polynomial in x, y and z.

 

[mfb]

Why do you want a cubic polynomial? In the way I understand the first post, everything is linear.

I'm not sure what "specific algorithm that finds the unique grid points" means. I proposed an algorithm that produces a list of these points. If OP is just interested in the number, then the triangle numbers are the answer already and I don't understand what this thread is about.

 

[jbriggs444]

I'm not sure what "specific algorithm that finds the unique grid points"

Nor am I -- so I took a guess: given a grid point, find its index in the diagonal scan order.