题目

Problem 224: Almost right-angled triangles II

Let us call an integer sided triangle with sides a ≤ b ≤ c barely obtuse if the sides satisfy
a2 + b2 = c2 - 1.

How many barely obtuse triangles are there with perimeter ≤ 75,000,000?

题解

第224题:准直角三角形(二)

我们称满足以下条件的整数边长 a ≤ b ≤ c 的三角形为勉强钝角三角形:
a2 + b2 = c2 - 1.

请问有多少个周长不超过 75,000,000 的勉强钝角三角形?

题目中的三角形是钝角三角形,当边长很大时,钝角非常接近直角。

分析

设三角形的周长为 p,边长分别为 a, b, c,且 a ≤ b ≤ c 。满足 a2 + b2 = c2 - 1 的最小的 (a, b, c) 值是 (2, 2, 3) 。从此出发,构造以下三元组:

  • (d - b, d - a, d + c), where d = 2(c + b + a)
  • (e - b, e + a, e + c), where e = 2(c + b - a)
  • (f - a, f + b, f + c), where f = 2(c - b + a)

也就是:

  • (2c + b + 2a, 2c + 2b + a, 3c + 2b + 2a)
  • (2c + b - 2a, 2c + 2b - a, 3c + 2b - 2a)
  • (2c - 2b + a, 2c - b + 2a, 3c - 2b + 2a)

注意当 a = b 时后两组值相等。计算不重复的满足 a+b+c ≤ p 的 (a, b, c) 的个数,就是本题的答案。(注意,我们还需要证明这没有遗漏。)

前几个三元组 (a, b, c) 的值如下所示:

我们知道,第 223 题和第 224 题中的三元组 (a, b, c) 满足以下条件:

  • a ≤ b ≤ c
  • a2 + b2 - c2 = ±1

容易验证,新的三元组也满足以上两个条件。

第二个条件验证如下:

(2c + b + 2a)2 + (2c + 2b + a)2 - (3c + 2b + 2a)2
= 4c2 + b2 + 4a2 + 4bc + 4ab + 8ac
+ 4c2 + 4b2 + a2 + 8bc + 4ab + 4ac
- 9c2 - 4b2 - 4a2 - 12bc - 8ab - 12ac
= a2 + b2 - c2

(2c + b - 2a)2 + (2c + 2b - a)2 - (3c + 2b - 2a)2
= 4c2 + b2 + 4a2 + 4bc - 4ab - 8ac
+ 4c2 + 4b2 + a2 + 8bc - 4ab - 4ac
- 9c2 - 4b2 - 4a2 - 12bc + 8ab + 12ac
= a2 + b2 - c2

(2c - 2b + a)2 + (2c - b + 2a)2 - (3c - 2b + 2a)2
= 4c2 + 4b2 + a2 - 8bc - 4ab + 4ac
+ 4c2 + b2 + 4a2 - 4bc - 4ab + 8ac
- 9c2 - 4b2 - 4a2 + 12bc + 8ab - 12ac
= a2 + b2 - c2

解答

根据以上分析,我们有以下 Haskell 程序:

main = let p = 75*10^6 in print $ f p 2 2 3 0 where
  f p a b c v = if a+b+c > p then v else let
    z =           f p (2*c-2*b+a) (2*c-b+2*a) (3*c-2*b+2*a) $
                  f p (2*c+b+2*a) (2*c+2*b+a) (3*c+2*b+2*a) (v+1) in
    if a < b then f p (2*c+b-2*a) (2*c+2*b-a) (3*c+2*b-2*a) z else z

这个程序的运行时间将近 2 秒。

第223题第四个解答分析

满足 a2 + b2 = c2 + 1 的头两个三元组 (a, b, c) 是 (1, 1, 1) 和 (1, 2, 2) 。从这两组值出发,依照前面的方法构造新的三元组,可以解出第 223 题。

前几个三元组 (a, b, c) 的值如下所示:


工作原理

这个算法来自 Doraki,根据他在欧拉计划论坛的帖子,其工作原理如下:

I didn't do the details, but I bet infinite descent should work.

Those 3 transformations are isometric when you use the "scalar product" given by <a,b,c ; a',b',c'> = aa'+bb'-cc',
And they send triplets with 0≤a≤b≤c on triplets with 0≤a≤b≤c.
Moreover, their determinant are +/-1, so the inverse transformations still have integral coefficients.

Actually, the images of the cone 0≤a≤b≤c should be 3 sub-cones (which we can compute) and the important part is that the surface S : a²+b²-c² = 0 should be included in R:= the reunion of those 3 sub-cones.

Now you only need to check for solutions of a²+b²-c² = k that are not in R (they are finite because R contains S), and start from them.

I think you can't descend infinitely within R because taking those transformations backwards should push you away from the surface S. (Maybe this could be checked in a projective geometry sense)

And, in order to obtain those transformations, I have this :
If y is of norm 1, I get the reflection using the plane orthogonal to y : the application x -> x-2<x,y>y is linear with integral coefficient, and is isometric.

So first I search for small solutions of <y,y>=1 (though <y,y>=+2,-1,or -2 should work just as well), to get a few reflections.
Then I compose them together a bit (and also with trivial ones such as swapping a and b in our case), looking for something where the cone we're interested in is stable.