This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.

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.

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

posted

0

I used Math.ceil() and Math.floor() to test it.Definitely not an efficient one compared to yours.

Can you explain how you reduced Heron's formula to this?

Roger Johnson
Ranch Hand

Joined: Feb 24, 2004
Posts: 311

posted

0

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.

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

posted

0

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

posted

0

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

posted

0

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

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

posted

0

Just noticed that if you start counting from b=2, you get this output:

{ 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

posted

0

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

posted

0

The above code does not print anything.I assume isSquare method,you are picking up from another poster.I tried to run the following.