Arjunkumar Shastry

Ranch Hand

Posts: 986

posted 12 years ago

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.

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

Posts: 311

Jon Pincott

Greenhorn

Posts: 17

posted 12 years ago

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.

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

Posts: 986

Ryan McGuire

Ranch Hand

Posts: 1113

7

John Smith

Ranch Hand

Posts: 2937

Roger Johnson

Ranch Hand

Posts: 311

posted 12 years ago

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

Posts: 502

posted 12 years ago

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 ]

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

Posts: 986

posted 12 years ago

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.

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.

Namma Suvarna Karnataka

Arjunkumar Shastry

Ranch Hand

Posts: 986

posted 12 years ago

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 ]

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 ]

Namma Suvarna Karnataka

Jon Pincott

Greenhorn

Posts: 17

posted 12 years ago

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.

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.

SCJP SCWCD

Jon Pincott

Greenhorn

Posts: 17

posted 12 years ago

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 ]

which agrees with The On-Line Encyclopedia of Integer Sequences (lookup 321467351292366)

[ April 22, 2005: Message edited by: Jon Pincott ]

SCJP SCWCD

Arjunkumar Shastry

Ranch Hand

Posts: 986

posted 12 years ago

{

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.

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.

Namma Suvarna Karnataka

Jayesh Lalwani

Ranch Hand

Posts: 502

posted 12 years ago

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?

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?