Thread: Integer points in a triangle ?

Hello all,

Pardon me if I am putting the question under the wrong topic , but I feel mine is geometric problem.

A triangle is formed on a graph paper 3 line equations

1 : X axis
2 : X<=N
3 : Y<=mX ( m <= 1)

Can I find a generalized equation for finding the number of integer points in the triangle formed ?

Regards

Tanvi
Pune

I don't know exactly what you are asking, but I'm thinking this is the answer to your question: $\displaystyle \sum_{k=1}^{N} [[{km}]] $ (note the greatest integer function).

Hello,

Thank you for replying.

I actually couldn't relate your solution to my problem, sorry for that.

I will give you 2 examples I guess that would make it clear

n=8
m=0.2

so if you form a triangle with x axis , x<=8 and y <=0.2 , i need to find the number of (x,y) points that are within triangle when plotted on a graph paper.
Ans = 13 in this case.

There is also a large example that I can give
n = 713241932
m = 127894722/957823358

Ans = 34065182435132155

I have this not only for my Math class but the same teacher has given this for our computer class as well.

I hope I have made things clear here !!

Regards
Tanvi

Originally Posted by tanvi.azgaonkar

Hello,

n=8
m=0.2

so if you form a triangle with x axis , x<=8 and y <=0.2 , i need to find the number of (x,y) points that are within triangle when plotted on a graph paper.
Ans = 13 in this case.

Do you mean the triangle formed by the x-axis, $\displaystyle x \le n$, and $\displaystyle y \le mx$?

First, let me explain the formula from my first post, then I'll correct it (since there's a mistake in it that I found based on your second post).

Based on my original assumptions, I could only see 5 "integer" points when these are plotted in your example. They would be (5,1), (6,1), (7,1), and (8,1). The ones I missed in my original response were those lying ON the x-axis (again, I'll correct this after I explain the formula).

Essentially what the formula in my original response was saying is this: if you start at x=0, then you've got no integer points.

Move over to x=1 and you've now got - well, still just the origin because you're only up to y=0.2 and there are no 'integer points below the line.

Move over to x=2 and you've now got - same as with x=1 since you're only up to y=0.4.

Move over to x=3 and it is the same: no 'integer' points below y=0.6.

Move over to x=4 and you're up to y=0.8: still no 'integer points in the triangle.

Move over to x=5 and you're up to y=1.0. Finally you've got another 'integer' point at (5,1) - this one is on the triangle so it is key to have the $\displaystyle \le$ instead of just <.

Move over to x=6 and you're up to y=1.2, so you've got (6,1) but no more.

Move over to x=7 and it is the same story. Up to y=1.4 with (7,1) as the only 'integer' point in the triagle here.

Move over to x=8 - the last one - and you're up to y=1.6, which means you've got (8,1) inside the triangle but no more.

That progression is what the formula does. First it starts at x=1, then moves to x=2, then to x=3 and so on all the way to x=n. That is what the numbers above and below the sigma ($\displaystyle \sum$) indicate. whichever number you are on as you increment through the x values is called k.

For each value of k (which are your x values), the following calculation is made: [[km]]. This means that the k (x-value) is multiplied times the slope. This gives you the y-value for the kth x-value. This is the number of integers below the y-value unless the y-value is a decimal. Then you need to just subtract off the decimal portion of the number. The 'greatest integer function' is what accomplishes that: [[km]] is read "the greatest integer of km" and is defined as the 'greatest integer less than or equal to km'. You can see in the hand-done increments that this is what is going on.

And finally, the sigma itself means you take all the numbers you came up with and add them up. The "sigma notation" is literally the way mathmeticians write "summation" into a formula. In your computer class it would be a loop:
For k=1 to n
y=[[km]] (I don't know the syntax of your programming lingo, but I'll bet there's a greatest integer function built into it somewhere)
S=S+y
Next k

Ok, now my original error. I did not count the points ON the x-axis. This is easily fixed though, since there is simply one more point in the triangle for each x-value. Therefore, you can use the following formula instead: $\displaystyle \sum_{k=0}^{n} [[km+1]] $ (and you need to start at k=0 to get the origin).

I hope this helps. I'm not sure how to write it without the summation (sigma) symbol since it needs to have an iterative process.

Thank you sir for this comprehensive explanation.
The formula and approach definitely finds useful in my math class , however there is still some tweak to be done for this problem for my computer class.
The reason the limit of n given is of the order 10^9. So any loop of the order 10^9 usually times out in our system. Our teacher insists that a solution exists such that the program wont time out. I do not know if the question is any longer mathematical, so pardon me if I have gone off track to the scope of he forum. However I would like to share with you a link http://jwilson.coe.uga.edu/EMAT6680F.../Pick_Main.htm
The site gives direct formula for calculating number of integer points in a triangle but an assumption made there is the vertex of the triangle is always and integer. In my case 2 vertex are always integer and the one remaining is necessarily not.
I hope you have understood my problem.
Regards
Tanvi