wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> almost equilateral integer triangles
        
(Message started by: JocK on Feb 20^th, 2005, 7:34am)

Title: almost equilateral integer triangles
Post by JocK on Feb 20^th, 2005, 7:34am

We define an almost equilateral integer triangle as a triangle with integer sides and integer area such that the largest and smallest side differ in length by one.

The first (smallest) almost equilateral integer triangle has sides 5, 5 and 6, and area 12. The next one has sides 17, 17, 16 and area 120.

The first five almost equilateral integer triangle areas are:

12, 120, 1848, 25080, 351780, ...

1) Can you calculate the next five terms in this sequence?

2) The triangle with sides 174725, 174725 and 174726 is also an almost equilateral integer triangle (check this!). Can you come up with a larger triangle and become record-holder "largest almost equilateral integer triangle ever calculated"...? ;)

3) Does the above sequence continue indefinitely? If so, determine the asymptotic behaviour of the n-th term in this sequence for large n. If not, what is the largest almost equilateral integer triangle?

Title: Re: almost equilateral integer triangles
Post by towr on Feb 20^th, 2005, 8:41am

on 02/20/05 at 07:34:55, JocK wrote:

1) Can you calculate the next five terms in this sequence?

Well, I can get my computer do do it.. [e]got 16 so far, including (2,1,1)[/e]

I suspect there are infinitely many, but I don't know how to proof there are an infinite number of integer solution to the squareroot of a certain (pair of) quadratic(s)..
And since the hide-tags still don't work I won't post it yet :P (Not that it's hard to derive)

Title: Re: almost equilateral integer triangles
Post by towr on Feb 20^th, 2005, 9:20am

The side lengths belonging to almost equilateral integer triangle seem to be very regularly spaced, always a factor of about 2+[sqrt]3 between them. (Unfortunately, although this does significantly help speed up finding them, it doesn't help me find more of them. Probably a representation-limit of the computer)
But it's a nice number other people can prove something about ;)

Title: Re: almost equilateral integer triangles
Post by Barukh on Feb 20^th, 2005, 10:10am

on 02/20/05 at 08:41:30, towr wrote:

I suspect there are infinitely many

I think you are right and I believe I can prove it.

Title: Re: almost equilateral integer triangles
Post by towr on Feb 20^th, 2005, 10:48am

A few simple observations:
There is always one even side, and two odd sides (easily proven)
The last digit of even length sides seem to repeat the sequence 666020
The odd sides alternate between one less and one more than the even side, and so not surprising repeat the sequence 575111
The area similarly repeats the sequence 208000
The first digits also seem to repeat (but I'm less sure about this), if we skip the first number of the sequence, the sides repeats 1629314, and the area 1123469 (same digits, different order :P)

Title: Re: almost equilateral integer triangles
Post by Sir Col on Feb 20^th, 2005, 11:47am

I've not managed to prove that there exist infinitely many, but maybe this can be developed...

Using Heron's formula, the area of the triangle A=sqrt(s(s-a)(s-b)(s-c)), where s=(a+b+c)/2.

W.L.O.G. let a=b:
A = sqrt((a+c/2)(c/2)(c/2)(a-c/2)) = (c/4)*sqrt(4a²-c²)

Writing 4a²-c² = k², we get (2a)² = c²+k².

So it amounts to showing that there exist infinitely many Pythagorean triplets (x,y,z)=(c,k,2a) for which z/2 is one more or one less than x.

Here are the two examples that Jock gave...
(6,8,10): 2a=10, so a=5 and c=6, hence A=12.
(16,30,34): 2a=34, so a=17 and c=16, hence A=120.

The next five being...
(66,112,130): a=65, c=66, and A=1848
(240,418,418): a=241, c=240, and A=25080
(902,1560,1802): a=901, c=902, and A=351780
(3360,5822,6722): a=3361, c=3360, and A=4890480
(12536,21728,25090): a=12545, c=1254, and A=68149872

Anyway, you get the idea.

Title: Re: almost equilateral integer triangles
Post by Eigenray on Feb 20^th, 2005, 3:00pm

on 02/20/05 at 11:47:34, Sir Col wrote:

I've not managed to prove that there exist infinitely many, but maybe this can be developed
[...]
(2a)² = c²+k².

(2a)² = (a +- 1)² + k²
can be rewritten as
((3a -+ 1)/2)² - 3(k/2)² = 1,
so we are looking for integer solutions to the [link=http://mathworld.wolfram.com/PellEquation.html]Pell equation[/link] x²-3y²=1
Given a solution (x,y), of which infinitely many exist, note that x²=1 mod 3 implies 2x = 3a -+ 1 for some integer a, and we may take k=2y. This gives the triangle
(a, a, a +- 1), with area A = (c/4) k = (a +- 1)y/2, also an integer, since a is odd.

Title: Re: almost equilateral integer triangles
Post by Barukh on Feb 21^st, 2005, 8:57am

I took essentially the same approach as Sir Col, just used sides 2a, 2a[pm]1 to avoid fractions.

From Eigenray’s formulas, we see that the side of the sought triangle is a linear function of x as a solution of the Pell equation. In the same link provided by Eigenray, we find how a whole family of solutions may be generated from a single solution (x₀, y₀), that is:
x_n = 1/2 * [ x₀ + y₀[sqrt]3)ⁿ + (x₀ - y₀[sqrt]3)ⁿ ].

The simplest solution in our case is (x₀, y₀) = (2,1), so that the second term in the above formula is less than 1, and for significantly large n the value x_n is dominated by the first term 1/2 * (2 + [sqrt]3)ⁿ. This explains the number found by towr earlier.

Title: Re: almost equilateral integer triangles
Post by Sir Col on Feb 21^st, 2005, 12:17pm

Great work with the Pell equation, Eigenray!

I found a method that almost trivialises the initial (Heron's forumula) approach...

Consider an isosceles triangle with sides (a,a,c). By drawing a perpendicular from the apex to base we produce two right triangles back-to-back.

If c (the base) were odd, c/2 and the height, h, would be non-integer, so the area would be non-integer.

So it is necessary for c to be even. As c=a+-1, a will be odd (confirming towr's observation).

a² = (c/2)²+h² = (a+-1)²/4+h²

3a²-+2a-1-4h² = 0

9a²-+6a+1-12h² = 4

(3a-+1)²-12h² = 4

((3a-+1)/2)²-3h² = 1

As a is odd, 3a-+1 will be even, and so divisible by 2. Therefore we do indeed get integers througout. Finally, as Eigenray explained, this is equivalent to the Pell equation, x²-3y² = 1, and we establish that there are infintely many solutions.

Title: Re: almost equilateral integer triangles
Post by JocK on Feb 21^st, 2005, 3:13pm

Well done folks!

This was too easy for you. So, why not try a slightly more complicated higher dimensional problem next:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1108939528

Title: Re: almost equilateral integer triangles
Post by Sir Col on Feb 22^nd, 2005, 11:38am

I don't feel that I'm quite done on this yet. Does anyone know anything about generating the solutions sets for Pell equations?

A method seems to be...

Given x²-ny² = 1 and the the solution (x,y), then (x²+ndy²,2xy) will also be a solution (easily proved). However this misses solutions, so it is, perhaps, better to use the fact that given the solutions (a,b) and (c,d), then (ac+-nbd,ad+-nbc) will also be solutions; this can be applied recursively.

Given the obvious solution (2,1), we also get (2²+3*1²,2*2*1)=(7,4).

From any solution set we only need x, as x=(3a-+1)/2. Therefore a=(2x+-1)/3 and we know that c=a+-1 (note the same sign).

For example, in (7,4), x=7, so a=(2*7+-1)/3. But the only integer solution is a=5 (by adding 1), so c=6.

But when we combine (2,1) and (7,4) we get (26,15): x=26, a=(52+-1)/3=17 (this time we subtract 1), so c=16.

My question... will this method produce ALL solutions?

Title: Re: almost equilateral integer triangles
Post by Barukh on Feb 23^rd, 2005, 10:27am

Sir Col, I don't know if your your method gives all solutions.

Don’t you remember discussing the similar problem in this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1080900827)? The method presented there is used to get the minimal solution (also called fundamental) which we denote (x₁, y₁). In our case it’s simply (2, 1).

Then, all the solutions may be obtained as described in the previous post. Let me elaborate. Denote X = x₁ + [sqrt]3y₁ = 3.732…, Y = x₁ - [sqrt]3y₁ = 0.268… Then, the n-th solution is obtained as follows:
x_n = (Xⁿ + Yⁿ) / 2, y_n = (Xⁿ - Yⁿ) / 2[sqrt]3
In our case, because Y < 1, we should have that for “sufficiently large” n, x_n+1 is the integer closest to Xx_n. In fact, it’s correct even for n = 1! Indeed:

2*X = 7.46….
7*X = 26.124…
26*X = 97.030…
97*X = 362.004…

Title: Re: almost equilateral integer triangles
Post by Sir Col on Feb 23^rd, 2005, 3:07pm

Oh yes, I certainly do remember that thread.

Thanks for the information, Barukh.

I was such a pain at school: always asking question and not caring how stupid I might appear. So would you mind me asking a couple of (stupid) questions... ?

How did you derive your iterative form?

In Eigenray's MathWorld link: http://mathworld.wolfram.com/PellEquation.html, how do they go from (31) to (32) and (33)? Why must those particular factors on the LHS and RHS match? For example, why can't (x+sqrt(D)y) be made up (p+sqrt(D)q)^j(p-sqrt(D)q)^k?

Title: Re: almost equilateral integer triangles
Post by Barukh on Feb 24^th, 2005, 11:29pm

on 02/23/05 at 15:07:26, Sir Col wrote:

For example, why can't (x+sqrt(D)y) be made up (p+sqrt(D)q)^j(p-sqrt(D)q)^k?

Clearly, j [ne] k, for otherwise we would get an irrational number on the lhs, and 1 on the rhs. So let j > k, and get
x+[sqrt]Dy = (p+q[sqrt]D)^j(p-q[sqrt]D)^k = (p+q[sqrt]D) ^j-k

But that’s more difficult then I thought… Actually, we want to show the following: (x,y) is also a solution iff
x + y[sqrt]D = (p + q[sqrt]D)ⁿ
for some integer n.

The “if” part is easy: If x + y[sqrt]D = (p + q[sqrt]D)ⁿ, then clearly x - y[sqrt]D = (p - q[sqrt]D)ⁿ, therefore

x² – Dy² = (x + y[sqrt]D)(x - y[sqrt]D) = (p + q[sqrt]D)ⁿ(p - q[sqrt]D)ⁿ = (p² – Dq²) ⁿ = 1.

The “only if” part is trickier. It follows directly from a theorem in algebraic number theory, but this is advanced stuff, but I wanted a simpler argument…

Title: Re: almost equilateral integer triangles
Post by Sir Col on Mar 21^st, 2005, 9:35am

on 02/23/05 at 15:07:26, Sir Col wrote:

How did you derive your iterative form?

Sorry that was a dumb question!

Yⁿ tends towards zero as n increases, so x_n = (Xⁿ+Yⁿ) ~= Xⁿ/2, and Xⁿ ~= 2x_n.

Therefore x_n+1 ~= Xⁿ⁺¹/2 = (X/2)Xⁿ ~= (X/2)2x_n = X*x_n.

Title: Re: almost equilateral integer triangles
Post by Deedlit on Apr 3^rd, 2005, 7:24pm

on 02/24/05 at 23:29:23, Barukh wrote:

The “only if” part is trickier. It follows directly from a theorem in algebraic number theory, but this is advanced stuff, but I wanted a simpler argument…

Interestingly, the solutions to a Pell equation form a group under the operation

(a,b) * (c,d) = (e,f)

where e + f sqrt (D) = (a + b sqrt (D)) (c + d sqrt (D)),

since

e² - D f²
= (e + f sqrt (D)) (e - f sqrt (D))
= (a + b sqrt (D)) (c + d sqrt (D)) (a - b sqrt (D)) (c - d sqrt (D))
= (a² - D b²) (c² - D d²) = 1

and if (a,b) is a solution, so is (a,-b) and

(a + b sqrt (D)) (a - b sqrt (D)) = a² - D b² = 1.

So if (p,q) is the minimal solution with |(p,q)| = p + q sqrt (D) > 1, for any positive solution (x,y) there is some n such that 1 <= |(x,y) * (p,q)ⁿ| < |(p,q)|. By minimality of (p,q), the above must be 1. Hence the positive solutions are (p,q)ⁿ for integer n. Of course the negative solutions are just (-x,-y) for postive solutions (x,y)