*
The moose likes Programming Diversions and the fly likes Almost equilateral triangle Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Almost equilateral triangle" Watch "Almost equilateral triangle" New topic
Author

Almost equilateral triangle

Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
This appeared recently in one newspaper:
The sides of an "almost equilateral" triangle are three consecutive eight-digit integers.The area of triangle is also an integer.
What are the sides?
I am getting four different answers.Not sure whether my method is right.I'll post in day or two after somebody tries here.


Namma Suvarna Karnataka
Roger Johnson
Ranch Hand

Joined: Feb 24, 2004
Posts: 311
sounds like a perfect occasion for computer.

for i = 10,000,000 to 99,999,997
if [ area(i) is integer ]
print i, i+1, i+2
i++



regarding area(a,b,c), i better look up in a math manual
[ April 19, 2005: Message edited by: Roger Johnson ]
Jon Pincott
Greenhorn

Joined: Jul 28, 2004
Posts: 17
I get one solution:

Area of triangle with sides (27246963, 27246964, 27246965) = 321467351292366

You can't use Heron's formula directly as the products don't fit into a long, but the initial conditions allow you to simplify and find a neccessary and sufficient condition to test as follows:



P.S. if anyone has got a neater way to test if a number is a square (without precomputing a list of squares in the range) then please post it.


SCJP SCWCD
Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
I used Math.ceil() and Math.floor() to test it.Definitely not an efficient one compared to yours.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006
    
    3
The first solution I can think of is a 00000003, 00000004, 00000005 triangle.
John Smith
Ranch Hand

Joined: Oct 08, 2001
Posts: 2937
<b>JP: Math.sqrt(3L*(b+2)*(b-2)) * b/4</b>

Can you explain how you reduced Heron's formula to this?
Roger Johnson
Ranch Hand

Joined: Feb 24, 2004
Posts: 311
Could you please explain what is "L"? i think it is not defined.

Originally posted by Jon Pincott:
I get one solution:

Area of triangle with sides (27246963, 27246964, 27246965) = 321467351292366

You can't use Heron's formula directly as the products don't fit into a long, but the initial conditions allow you to simplify and find a neccessary and sufficient condition to test as follows:



P.S. if anyone has got a neater way to test if a number is a square (without precomputing a list of squares in the range) then please post it.
Jayesh Lalwani
Ranch Hand

Joined: Nov 05, 2004
Posts: 502
Well, I did some math to redce the number of loops. My initial idea was to write an algorithm that will automatically coumpute the sides that solve the puzzle. I was half succesful. I could whittle the Heron's formula to another formula that will give a range of possible sides, but not all of them are correct. In other words, the set of sides that I get is a superset of the correct answer.

So, I wrote some code that goes through the superset and verifies whether the area is a square. Since, the superset is comparitively smaller, my program goes through less number of loops. Here's the program


Here's the result.. Lots of them. I think all of them are right. Anyone want to check


[ April 21, 2005: Message edited by: Jayesh Lalwani ]
[ April 21, 2005: Message edited by: Jim Yingst ]
Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
Originally posted by John Smith:
<b>JP: Math.sqrt(3L*(b+2)*(b-2)) * b/4</b>
Can you explain how you reduced Heron's formula to this?


I think Haron's formula is :
Area of triangle A = Math.sqrt(s*(s-a)*(s-b)*(s-c)).
s = semiperimeter = (a+b+c)/2
a,b,c are sides of triangle.
I think if we equate Cosine formula with area using Sine(i.e.1/2*a*b*sinC),it should be posible to derive the above one.
Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
Instead of calculating the area compltetely,I tried in different manner.
Sides of triangle are :a,a+1,a+2
cos^2(A) = [(a+1)^2 - (a+2)^2 - - a^2]/[2*(a+1)*(a+2)].....(1)
After few steps,
cosA = (a+5)/(2*(a+2)).................................(2)
sin^2(A) = 1 - cos^2(A)...............................(3)
Substituting value of (2) in (3),after few steps w'll get,
sinA = Math.sqrt(3)*Math.sqrt((a+3)*(a-1))/(2*(a+2))........(4)
Area of triangle,A = 1/2*b*c*sinA
A = (Math.sqrt(3)/4)*b*c*Math.sqrt((a+3)*(a-1))/(a+2).......(5)
(This is "almost" the area of equilateral triangle, if a is the side of equilateral trianglr,then area is (Math.sqrt(3)/4)*a*a )
For A to be an integer,3 must be a factor of (a+3)*(a-1)
If a is even,then b and c are odd,also (a+3)*(a-1) is odd,hence in oder to be divisible by 4,in (5),a must be odd.
(5) can also be reduced to ,
A = (Math.sqrt(3)/4)* (a+1)*Math.sqrt((a+3)*(a-1))
I think,there are many oslutions now.
[ April 22, 2005: Message edited by: Arjunkumar Shastry ]
Jon Pincott
Greenhorn

Joined: Jul 28, 2004
Posts: 17
To answer a couple of questions regarding my previous post:

Heron's formula for the area of a triangle, A, with sides (a,b,c) is:

A = sqrt( s(s-a)(s-b)(s-c) ), where s=(a+b+c)/2

Given that the sides are consecutive integers, we can write a=b-1, c=b+1

=> s = 3b/2

=> A^2 = (1/2)^4 * (3b)(3b-2a)(3b-2b)(3b-2c)
= (1/4)^2 * (3b)(b+2)(b)(b-2)
= (b/4)^2 * 3(b+2)(b-2)

=> A = (b/4) * sqrt( 3(b+2)(b-2) ) ...(1)

Also, given that 4A and b are integers, we can deduce that

A is an integer <=> sqrt( 3(b+2)(b-2) ) is an integer
<=> 3(b+2)(b-2) is a square ...(2)

So, to test for solutions in Java:

1) Loop over (int) b from 10000001 to 99999998 to cover all 8-digit triples.
2) For each b, test whether 3(b+2)(b-2) is a square. (from eq(2))
3) If b is square, calculate the area and output. (from eq(1))

Note that in my code b is an int, so the argument for the isSquare test is 3L(b+2)(b-2). The 3L is a long literal and implicitly promotes the rest of the calculation to long values, otherwise the product (b+2)(b-2) would be an int calculation with a result > Integer.MAX_VALUE.

Here's a breakdown of my solution:

a = 27246963
b = 27246964
c = 27246965

s = 40870446
s-a = 13623483
s-b = 13623482
s-c = 13623481

A = sqrt( s(s-a)(s-b)(s-c) )
= sqrt(103341257946929448170409877956)
= 321467351292366

If you're getting other solutions, check your ints/longs aren't exceeding their max values and that your doubles have enough significant digits. There's only one solution in the range specified, as indicated by the wording of the puzzle. Try googling 321467351292366 or check out "Pell Equation" at mathworld if you want to read more. (P.S. You can show that eq(2) reduces to the Pell-type equation x^2-3y^2=4, where x=b)

BTW I'm new to this posting lark, so apologies if the formatting of the above is screwy.
Jon Pincott
Greenhorn

Joined: Jul 28, 2004
Posts: 17
Just noticed that if you start counting from b=2, you get this output:



which agrees with The On-Line Encyclopedia of Integer Sequences (lookup 321467351292366)
[ April 22, 2005: Message edited by: Jon Pincott ]
Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
{
1) Loop over (int) b from 10000001 to 99999998 to cover all 8-digit triples.
2) For each b, test whether 3(b+2)(b-2) is a square. (from eq(2))
}
Looping can be reduced to half as b will always be even integer.i.e. a will alway be odd integer as shown above in your result.
Jayesh Lalwani
Ranch Hand

Joined: Nov 05, 2004
Posts: 502
Originally posted by Arjunkumar Shastry:
{
1) Loop over (int) b from 10000001 to 99999998 to cover all 8-digit triples.
2) For each b, test whether 3(b+2)(b-2) is a square. (from eq(2))
}
Looping can be reduced to half as b will always be even integer.i.e. a will alway be odd integer as shown above in your result.


Well, 3(b+2)(b-2) has to be a square, doesn't it mean that one solution could be
a) that b+2 should be divisible by 3, and after you divide b+2 by 3, the result should be a square
b) b-2 should be a square

So, we can setup a loop from b=10000000 onwards and increment by 3. Then we can test b-2 is squared or not. That will reduce the number of loops by a third

or better yet
let's say b+2 = 3*p*p where p is an integer from 1826 to 5773

So we iterate over p, calculate b, and test if b-2 is a square. Tht will whittle the iterations down to 4000

Similarily, we can have
a) that b-2 should be divisible by 3, and after you divide b-2 by 3, the result should be a square
b) b+2 should be squared

so, let's say b-2 = 3*q*q where q is an integer from 1826 to 5773. So, we can have another check for this in the same loop

Like this


How's that?
Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
The above code does not print anything.I assume isSquare method,you are picking up from another poster.I tried to run the following.


Follwing is mine,
very slow
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Almost equilateral triangle
 
Similar Threads
Triangles on a sphere.
operator & cannot be applied to boolean.java.lang.String
Triangle Problem
ValidatingTrianlges.java
Boolean Help Needed in J2SDK1.4.2_06!