• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Almost equilateral triangle

 
Ranch Hand
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 311
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Arjunkumar Shastry
Ranch Hand
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I used Math.ceil() and Math.floor() to test it.Definitely not an efficient one compared to yours.
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The first solution I can think of is a 00000003, 00000004, 00000005 triangle.
 
Ranch Hand
Posts: 2937
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
<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
Posts: 311
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

 
Ranch Hand
Posts: 502
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
{
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
Posts: 502
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 999
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic