搜索下一个边长都是平方数的海伦三角形

mathe

面积和边长都是整数的三角形称为海伦三角形.
A318575 中给出了两个三边长均平方数的本原（三边长公因子为1）海伦三角形的面积
a(1)=32918611718880, 对应三角形三边长为\(1853^2, 4380^2, 4427^2\)
a(2)=284239560530875680, 对应三角形边长为\(11789^2, 68104^2, 68595^2\)
请问能否或如何找到第三个？

mathe

如果我们假设三角形三边分别为\(a=l^2,b=m^2,c=n^2\)并且记\(x=l^4,y=m^4,z=n^4\),
那么三角形面积的平方为\(\Delta^2=2xy+2yz+2zx-x^2-y^2-z^2\).
我们还可以吧上面的表达式写成
\(\Delta^2+(x+y-z)^2=4xy\)
这个表明整数\(4xy\)可以表示成两个完全平方数之和。
由于对于一个整数如果因子分解后为\(2^a p_1^{u_1}p_2^{u_2}\cdots p_t^{u_t} q_1^{v_1}q_2^{v_2}\cdots p_s^{v_s}\), 其中\(p_h\)是模4为1的素因子，\(q_h\)为模4为3的素因子
那么由于\(2=(1+i)(1-i)\), 而对于其中每个\(p_h\)，可以写成\(p_h=(a_h+b_h i)(a_h-b_h i)\).
那么上面整数可以写成两个整数平方数之和的充分必要条件所有的\(v_i\)都是偶数，而且所有表达形式可以通过上面这些基本复数表示组合而成。
由于对于我们这里的4xy,所有素数幂的次数都是偶数（对于奇素因子实际次数都是4的倍数），所以必然有解。所以我们可以对于给定的x,y, 通过枚举\(4xy\)所有分解为两个整数平方和的形式的方法来枚举所有可能的x+y-z, 然后由此求出z并且判断z是否为一个整数的4次方来确定是否是一个合法解。

计算过程中，没有可以先预先求出所有模4余1的素数分解为两个整数平方和的形式，然后搜索并且穷举每两个可能的x,y。
我们可以穷举一定范围内的,l,m , 比如如果我们目标是穷举\(l\le m \le n\le N=10^6\), 那么需要时间复杂度估计应该约等于\(O(N^2 \log(N))\). 而现在我这边已经花了10多天（8核），穷举到\(N=3*10^5\)并没有发现新的解。

为此，我们需要估算一下解的密度到底可能有多高。
搜先我们知道对于给定\(l,m, n\le N\)，\(2xy+2yz+2zx-x^2-y^2-z^2\approx O(N^8)\), 而由于 \(\frac{d x^2} {dx}=2x\), 所以我们可以认为，随机选择一个正整数x,它是平方数的概率大概为\(O(\frac1{\sqrt{x}})\),
由此得出这个表达式\(2xy+2yz+2zx-x^2-y^2-z^2\approx O(N^8)\)是完全平方数的概率大概为\(O(\frac1{N^4})\). 但是其中至少一条边为N的情况的数目大概为O(N^2), 所以得到，最终数目大概为\(\int_{N=N_0}^{\infty}O(\frac{N^2}{N^4})dN\)是有限的。
但是这里的估计中，面积结果为\(O(N^8)\)是按最大情况估计的，实际上可能会略大一些。

数论爱好者

第三组解可能含有一,二组解的开头4个因子.你先退一步,找一找面积是开头4个因子与其它素数组合后,面积是平方数的规律看看.

wayne

三边是$(a,b,c)=(x^2,y^2,z^2)$, 经过一番比较麻烦的有理化过程,最终就是求 寻找有理数$(s,t)$同时满足$\frac{s^2 t^2+1}{(s^2+1) t}=(\frac{x}{z})^2=X^2,\frac{(t+1)(1-s^2 t)}{(s^2+1) t}=(\frac{y}{z})^2=Y^2$

比如,我代入$s=frac{3}{34}$ ,得到$1156 + 9 t^2 - 1165 t X^2 = 0$,对应的椭圆方程是$v^2  = u^3 +14120568900*u$,映射关系是$t=1346740/u, X = v/(1165*u)$, 这是一个秩为3的曲线, 轻轻松松得到一个解, 只可惜要同时满足方程2,就只有这一个了.

1. {4,4,4,(1853,4380,4427),[(0, 0, -1, 2), (0, 0, 1, 2)] }
   
2. {4,4,4,(1853,4427,4380),[(-1, -1, 0, 0), (-1, -1, 0, 1), (1, 1, 0, 0), (1, 1, 0, 1)] }
   

复制代码

wayne

如果把两个方程联合起来,消去s,可以得到$(t+1) X^2+(t-1) Y^2=t+1$ 也就是说,我们需要选择合适的有理数t,使得这个椭圆存在 有理点.,得到有理点后,再回代到$s^2=\frac{-X^4+Y^4-2 Y^2+1}{X^4-Y^4-2 Y^2-1}$进行验证, 是否可以开平方.
总的来说, 就是要对有理数t进行穷举, 然后因子分解, 这可以大大简化搜索力度, 是个很大的突破点.

当然我们也可以采取分析手段,比如,我们取 $t=380192/8513$,代入$(t+1) X^2+(t-1) Y^2=t+1$得到$-388705 + 388705 X^2 + 371679 Y^2=0$,进而得到参数解$(X,Y)\to(\frac{388705-371679 u^2}{371679 u^2+388705},-\frac{777410 u}{371679 u^2+388705})$,
然后我们再代回$s^2=\frac{8513 \left(138145279041 u^4-302183154050 u^2+151091577025\right)}{380192 \left(138145279041 u^4+302183154050 u^2+151091577025\right)}$, 也就是$S^2=8513 (138145279041 u^4-302183154050 u^2+151091577025)*380192 *(138145279041 u^4+302183154050 u^2+151091577025)$,而这个是超椭圆曲线, 只有有限个点,可以定性. 然后我们先计算 $s^2=\frac{8513 \left(138145279041 U^2-302183154050 U+151091577025\right)}{380192 \left(138145279041 U^2+302183154050 U+151091577025\right)}$, 这个椭圆曲线

wayne

绕来绕去的,差点晕了, 我发现其实就是这么一个通解,设三边是$(a,b,c)=(x^2,y^2,z^2)$,那么存在$[x^2 : y^2 : z^2] = [s^2 t^2+1 : (t+1)(1-s^2 t) :  (s^2+1) t]$, 此时面积就是 $A= d^2 s t (1 + t) (1-s^2 t)$, 如果$x^2 = d(s^2 t^2+1)$
我们要解的就是这么一个通解, d是公约数,是调节因子.s,t是任意有理数, 使得
\[x^2 = d(s^2 t^2+1) \\
y^2 = d (t+1)(1-s^2 t) \\
z^2 = d (s^2+1) t \]

两个特例都经过了验证

1. Table[{p,Select[Solve[{d(1+s^2 t^2)==x^2 ,d(1+t)(1-s^2 t)==y^2 ,d t(s^2+1)==z^2 ,A== d^2 s t (1+t) (1-s^2 t)}/.Thread[{x,y,z}->p],{d,s,t,A}],Last[#[[-1]]]>0&]},{p,Permutations[{11789,68104,68595},{3}]}]//Column

复制代码

\[\begin{array}{l}
\left\{\{1853,4380,4427\},\left\{\left\{d\to \frac{8306217}{5},s\to \frac{3}{34},t\to \frac{24548}{2097},A\to 32918611718880\right\}\right\}\right\} \\
\left\{\{1853,4427,4380\},\left\{\left\{d\to \frac{482770097}{233},s\to \frac{3}{34},t\to \frac{48960}{5329},A\to 32918611718880\right\}\right\}\right\} \\
\left\{\{4380,1853,4427\},\left\{\left\{d\to \frac{1874703404880}{201977},s\to \frac{4320}{5329},t\to \frac{1923769}{1509840},A\to 32918611718880\right\}\right\}\right\} \\
\left\{\{4380,4427,1853\},\left\{\left\{d\to \frac{4435433280}{233},s\to \frac{4320}{5329},t\to \frac{5329}{48960},A\to 32918611718880\right\}\right\}\right\} \\
\left\{\{4427,1853,4380\},\left\{\left\{d\to \frac{2388661245233}{201977},s\to \frac{722}{699},t\to \frac{1509840}{1923769},A\to 32918611718880\right\}\right\}\right\} \\
\left\{\{4427,4380,1853\},\left\{\left\{d\to \frac{97234628}{5},s\to \frac{722}{699},t\to \frac{2097}{24548},A\to 32918611718880\right\}\right\}\right\} \\
\end{array}
\]
.
\[
\begin{array}{l}
\left\{\{11789,68104,68595\},\left\{\left\{d\to \frac{625347242521}{17026},s\to \frac{257}{19729},t\to \frac{143819505}{1122833},A\to 284239560530875680\right\}\right\}\right\} \\
\left\{\{11789,68595,68104\},\left\{\left\{d\to \frac{2374227967609}{22865},s\to \frac{257}{19729},t\to \frac{380192}{8513},A\to 284239560530875680\right\}\right\}\right\} \\
\left\{\{68104,11789,68595\},\left\{\left\{d\to \frac{170354594418600736}{138980521},s\to \frac{896416}{1540853},t\to \frac{103049865}{35930656},A\to 284239560530875680\right\}\right\}\right\} \\
\left\{\{68104,68595,11789\},\left\{\left\{d\to \frac{106033417063456}{22865},s\to \frac{896416}{1540853},t\to \frac{8513}{380192},A\to 284239560530875680\right\}\right\}\right\} \\
\left\{\{68595,11789,68104\},\left\{\left\{d\to \frac{488580502314418065}{138980521},s\to \frac{1319445}{790789},t\to \frac{35930656}{103049865},A\to 284239560530875680\right\}\right\}\right\} \\
\left\{\{68595,68104,11789\},\left\{\left\{d\to \frac{80098403656185}{17026},s\to \frac{1319445}{790789},t\to \frac{1122833}{143819505},A\to 284239560530875680\right\}\right\}\right\} \\
\end{array}
\]

数论爱好者

参数太多,未知数太多,穷举已经不现实了,可能要新的数学理论工具了.
有一个网页专找海伦三角形的面积是平方数的类型.可惜,边长就不是平方数,二者不能兼得.
他说:没有原始的Heronian三角形的面积为3600,因为通过他的编程,m=5000没有找到解.
可以看看下面这个网页:https://math.stackexchange.com/q ... res?r=SearchResults
      area 32400  square root    180  NEW    A: 697  B: 657  C: 104
      area 396900  square root    630  NEW    A: 1066  B: 1017  C: 833
      area 213444  square root    462  NEW    A: 1233  B: 890  C: 539
      area 435600  square root    660  NEW    A: 2993  B: 2057  C: 1000
......

mathe

一定范围内整数运算效率很重要，有256比特整数特别高效的现成计算库吗？

wayne

boost的multiprecision, 可以调用GMP/ mpfr作为 backend,也可以 用自己的header only的实现
https://www.boost.org/doc/libs/l ... recision/intro.html

我现在正在用python + SageMath 穷举 s, s的分子分母 都小于2000的所有 椭圆曲线的解.  给定s,就能得到确定的椭圆曲线, 进而得到无数组$x^2,z^2$, 但是$y$不一定是平方数,用这个过滤一下, 目前是可以轻轻松松拿到 最小解, s=3/34的时候取得.

mathe

我现在搜索到边长\(500000^2\)以内都没有找到第三组解，所以还有解的概率是非常小了