简介
2008年11月northwolves在csdn要求 :
1. 四个不同自然数a\lt b\lt c\lt d 满足a^2+b^2+c^2+d^2=abcd，列出1亿内的所有组合。
- n个不同自然数a_1\lt a_2\lt\dots\lt a_n 满足a_1^2+a_2^2+\dots+a_n^2=a_1a_2\dots a_n，列出1亿内的所有组合。
2013年2月wayne在数学研发论坛寻求下面不定方程的解 :
求正整数解：
x^2+y^2+z^2=3xyz
===============
更进一步，假如 0\lt x\le y\le z\le 10^{10}，那么总共有多少组呢?
litaoye(绿色夹克衫)给出了一种利用韦达定理进行递降的巧妙算法，mathe利用这种方法彻底解决了更大范围的解。
比如其中问题1的第10000组解为
a=1155707276902
b=52631648121718437290225329446159132818342
c=121653557459230956410906311942093212906353571240214806
d=54756951556826666523961130929258828162755166803423037863993739741969018235335921416820498267983420590064684413368261305133980613412835260713754668464533252084098231022109546996215107093857821479530279109208302608
详细内容
northwolves先给出了一组问题1的解: 2，6，22，262
medie2005很快发现:
一般的,对如下的数列:
a[0]=a[1]=a[2]=a[3]=2.
a[n]=a[n-1]\times a[n-2]\times a[n-3]-a[n-4]
相邻四项都满足:a[n-3]^2+a[n-2]^2+a[n-1]^2+a[n]^2=a[n-3]\times a[n-2]\times a[n-1]\times a[n].
因此,22, 262, 34582, 199330642也是一组解.
262, 34582, 199330642, 1806032092550706也是一组解.
对a^2+b^2+c^2=abc.我们同样可以构造一系列解.
a[0]=a[1]=a[2]=3.
a[n]=a[n-1]\times a[n-2]-a[n-3]
于是,(3,6,15),(6,15,87),(15,87,1299),…都满足a^2+b^2+c^2=abc.
一般的,对k=a^{k-2}.我们选定k,如果方程有解a_0,那么,我们可以定义数列:
a[0]=a[1]=\dots=a[k-1]=a_0;
a[n]=a[n-1]\times\dots\times a[n-(k-1)]-a[n-k].
那么，(a[n-(k-1)],\times,a[n-1],a[n])为a_1^2+a_2^2+\dots+a_k^2=a_1a_2\dots a_k的解.
northwolves发现medie2005构造的解就是A061292.
而n=3时的问题对应A086326
而A002559 Markoff numbers对应wayne的问题。
但是northwolves发现还有解不在medie2005的系列解之中，比如
2 22 82 3606
6 22 262 34582
2 82 306 50182
2 306 1142 698902
2 262 3122 1635922
6 262 3122 4907782
22 82 3606 6505222
22 262 11522 66412806
northwolves搜索了部分解，medie2005根据northwolves陆续搜索出来的结果总结出
对第k组解(a,b,c,d)，a,b必然在前k-1组解中出现！
因此，我们猜测：所有的a,b都可以在前面的解中找到。
如果这个猜测成立，那么，(a,b)的选择范围就很小了。
litaoye(绿色夹克衫)总结出可以利用二次方程的韦达定理来构造出所有的解:
看lz给的数据，看来有可能从最小的一组解，构造出全部解的可能（不过还需要证明，可以构造出一组解不难证明，可以构造出全部解，就不容易证明了）
我说说我看到的一些规律（估计lz早就发现了）
最小的一组解是
2 2 2 2
固定前3个可以得出
2^2 + 2^2 + 2^2 + X^2 = 8X(解1元2次方程)
x的两个解为x=2和x=6
现在成了2 2 2 6 -> 2 6 2 2
固定前3个可以得出
2^2 + 6^2 + 2^2 + X^2 = 24X(解1元2次方程)
x的两个解为x=2和x=22
现在成了2 6 2 22 -> 2 6 22 2
固定前3个可以得出
2^2 + 6^2 + 22^2 + X^2 = 264X(解1元2次方程)
x的两个解为x=2和x=262
现在成了2 6 22 264
同样的方法就可以构造出
2 6 262 3122
2 6 3122 37202
2 6 37202 443302
2 6 443302 5282422
2 6 5282422 62945762
2 22 82 3606
的构造方法如下
2 2 2 2 -> 2 2 2 6-> 2 2 6 22-> 2 2 22 82->2 22 82 3606
至少目前给出的解,都可以从2 2 2 2构造出来
然后他给出了证明思路:
假设存在四个不同自然数a\lt b\lt c\lt d 满足a^2+b^2+c^2+d^2=abcd
那么一定存在另一组a b c e满足a^2+b^2+c^2+e^2=abce（通过1元2次方程的另一个解可以解出）
而e \lt d，同理a b c e一定存在另一组a b f e 满足a^2+b^2+f^2+e^2=abfe
而f \lt c \dots
推到最后，w^2 + x^2 + y^2 + z^2 = wxyz 只有当w=x=y=z，才不存在另一组更小的解，而只有在w=x=y=z=2时，这个等式才成立，因此可以推出
2 2 2 2是所有解的唯一根。
再说一下，这种解法也许可以推出lz的第2题
2. n个不同自然数a_1\lt a_2\lt\dots\lt a_n 满足a_1^2+a_2^2+\dots+a_n^2=a_1a_2\dots a_n ，列出1亿内的所有组合。
在3个数的时候，3 3 3是所有解的唯一根，在5个数的时候，似乎无解。
但是随即发现对于5个数的情况的分析存在问题:
不好意思，上面的证明有些问题，5个数的时候存在1 1 3 3 4，这个最小解，可能是所有解的根，但这五个数并不相等.
准确点说，应当是 2\times a_5 \gt a_1a_2a_3a_4 时存在更小的一组整数解.
4个数时，当2\times a_4 \gt a_1a_2a_3时，存在更小的一组整数解
3个数时，当2a_3 \gt a_1a_2时，存在更小的一组整数解
但应当可以证明2 2 2 2是4个数中满足2a_4 \gt a_1a_2a_3 的唯一解（a_1\ge a_2\ge a_3\ge a_4），这样便可以证明所有解都是由2 2 2 2派生出的。
用穷举法可以，下面是一些穷举范围划定
2a_4 \lt a_1a_2a_3
=>
2a_4^2 \lt a_1a_2a_3a_4
=>
2a4^2 \lt a_1^2 + a_2^2 + a_3^2 + a_4^2
=>
a_4^2 \lt a_1^2 + a_2^2 + a_3^2
=>
a_1a_2a_3a_4 \lt 2(a_1^2 + a_2^2 + a_3^2)
=>
a_1a_2a_3a_3 \lt 2(3a_3^2)
=>
a_1a_2 \lt 6
穷举范围很小了
下面分2种情况分析
1、a_3 \lt a_4
2、a_3 = a_4
1、a_3 \lt a_4 可以从
a_4^2 \lt a_1^2 + a_2^2 + a_3^2
=>
(a_4-a_3)(a_4+a_3) \lt a_1^2 + a_2^2
(a_4-a_3)至少为1=>
a_4+a_3 \lt a_1^2 + a_2^2
穷举范围很小
2、a_3 = a_4 可以从 a_1^2 + a_2^2 + a_3^2 + a_4^2 = a_1a_2a_3a_4
=>
a_1^2 + a_2^2 + 2a_4^2 = a_1a_2a_4^2
=>
a_1^2 + a_2^2 = (a_1a_2 – 2)a_4^2
穷举范围很小
排除额外情况后，就可以推出2 2 2 2是唯一的满足2a_4 \lt a_1a_2a_3的整数解，因此所有解都是从2 2 2 2派生出的
3个数时的3 3 3也一样。
mathe指出:
litaoye的方法很好.
而对于更加一般的情况,我们只需要穷举所有
x_1x_2\dots x_{n-2}\le n的情况
而所有其它的解都可以通过上面的规则产生.
再加一个对x_{n-1}的起始约束,不然开始解还是太多:
x_{n-1}\le\sqrt{\frac{x_1^2+x_2^2+\dots+x_{n-2}^2}{x_1x_2\dots x_{n-2}-2}}
比如对于n=3我们得到方程
x_1^2+x_2^2+x_3^2=x_1x_2x_3
起始解必须有x_1\le 3.由于x_1\le 2显然无解,所以x_1=3.
这时我们可以得到起始解中x_2\le \sqrt{\frac{x_1^2}{x_1-2}}=3.
也就是所有解可以通过(3,3,3)和(3,3,6)来派生.(其实应该只用前一个就可以了,这个可以通过再对x_n加约束来达到)
同样对于n=4,第一个约束表明x_1x_2\le 4,使用前面我得到n=4时所有数都是偶数的结论可以知道x_1=x_2=2.
然后使用第二个约束得到x_3\le\sqrt{\frac8{4-2}}=2,所以得到x_3=2.
同样可以得到n=4的所有解由(2,2,2,x_4)派生.
并且他写了个程序搜索所有的初始解,其中n=6,9,11,12无解.对于其它13以内的n都只有唯一一个初始解.
如
n=3: 3,3,3
n=4: 2,2,2,2
n=5: 1,1,3,3,4
n=7: 1,1,1,2,2,2,3
n=8: 1,1,1,1,2,2,2,4
n=10:1,1,1,1,1,1,1,3,4,4
n=13:1,1,1,1,1,1,1,1,3,4,5
而第一个有两个以上初始解的是n=14
1,1,1,1,1,1,1,1,1,1,2,2,3,3
1,1,1,1,1,1,1,1,1,1,1,3,4,6
由此他继续算出了n=4的前10000组解，其中第10000组为:
1155707276902 52631648121718437290225329446159132818342 121653557459230956410906311942093212906353571240214806 7399794021243203937345243489590275923833855218950097547420488918995229934938733746100352534434654547982102
计算前10000个结果是瞬间完成的，点击下载他的C++代码
然后在数学研发论坛的对应帖子中 ,他给出哪些n在100以内有非平凡解，并提交的OEIS产生了A146974
而后来对于wayne提出的类似问题，hujunhua提供了一份Mathematica计算方案
f[x_] := {{x[[1]], x[[3]], 3 x[[1]] x[[3]]-x[[2]]},{x[[2]],x[[3]],3x[[2]] x[[3]]-x[[1]]}};
NestList[Flatten[f/@#,1] &,{{1, 2, 5}}, 4]//TableForm
f[x_] := {{x[[1]], x[[3]], 3 x[[1]] x[[3]] - x[[2]]}, {x[[2]], x[[3]],3 x[[2]] x[[3]] - x[[1]]}};
g[x_] := Flatten[f /@ x, 1];
h[x_] := Select[g[x], #[[3]] < 10^10 &]
Answer = NestWhileList[h, {{1, 2, 5}}, Length[#] > 0 &];
Flatten[Answer, 1]
(Flatten[Answer, 1] // Length) + 2
wayne把代码优化为
Union@Flatten[
NestList[Union@Sort@Flatten[Table[Union[
Map[Sort, {x, y, z, 4 x y z - t} /. Thread[Rule[{x, y, z, t}, #]] & /@
NestList[RotateLeft, ii, 4]]], {ii, #}], 1] &, {{1, 1, 1, 1}}, 5], 1]
数学星空找到了维基百科中对应的介绍
mathe做了总结:
回到一般性题目x_1^2+x_2^2+…+x_n^2=mx_1x_2…x_n
对于解x_1\le x_2\le\dots\le x_n,如果一组解不能够通过更加小的解通过二次方程的方法扩展而成，那么
x_n必然是方程X^2-mx_1x_2…x_{n-1}X+(x_1^2+…+x_{n-1}^2)=0较小的解，于是我们得出
x_{n-1}\le x_n\le \frac{2(x_1^2+…+x_{n-1}^2)}{mx_1x_2\dots x_{n-1}}\le\frac{2(n-1)x_{n-1}^2}{mx_1x_2…x_{n-1}}
由此我们得出
x_1x_2…x_{n-2}\le\frac{2(n-1)}m
也就是我们只需要先分析出满足上面情况的解
对应n=m=4的情况，也就是分析x_1x_2\le\frac32的解即可。也就是x_1=x_2=1
对应2+z^2+u^2=4zu
而同样，对于任意一组满足条件的x_1,x_2,…,x_{n-2},方程简化为
A+X^2+Y^2=CXY,
同样假设X\le Y,同样，如果这组解(X,Y)如果不能由更小的解产生，必然有
X\le Y\le\frac{2(A+X^2)}{CX}
得出CX^2\le 2X^2+2A
于是对于任意C\ge 3,我们直接得出X\le\sqrt{\frac{2A}{C-2}}
也就是同样，我们可以非常良好的确定x_{n-1}的范围。然后对于范围内的就可以很容易确定x_n,最后通过这些解可以构造出所有其它解。
对应到n=m=4的情况得出z\le\sqrt{2},所以必然x=y=z=1,3+u^2=4u,u=1或u=3.
进一步分析，我们可以得出如下算法:
i)穷举前面条件下所有x_1\le x_2\le\dots\le x_{n-2}.
ii)对于i)中每个组合，利用前面结果穷举所有x_{n-1}\le\sqrt{\frac{2A}{C-2}},而且要求x_{n-2}\le x_{n-1}.
iii)对于上面的每个x_1\le x_2\le\dots\le x_{n-2}\le x_{n-1},求解关于x_n的二次方程，如果两个解都不小于x_{n-1},我们就得出两个（或重根情况只有一个）基本解。
iv)对于所有的解，分别替换x_1,x_2,…,x_{n-1}得出所有的扩展解。 （注意对于小的基本解，替换x_n可以得出另外一组基本解.
hujunhua进一步指出:
当1\le x_1\lt x_2\lt\dots\lt x_n时，一个完整的递推公式共有(n-1)的单式，分别是
(x_1, x_2, \dots, x_n)\to(x_1, x_2,\dots, x_{i-1}, x_{i+1}, \dot, x_n, x^{\prime}_i), (i=1, 2, 3, \dots, n-1)
其中x^{\prime}_i=mx_1 x_2 \dots x_{(i-1)} x_{(i+1)} \dots x_n-x_i
也就是从表(x_1, x_2, \dots, x_n)中去掉x_i, 然后在表尾添上x^{\prime}_i
当相邻分量相等时，对应的单式相同，可缩并为一个单式。
在这样的递推关系下，从一个初解出发可以生成一棵树。如果这棵树不能囊括方程的全解，那就表明有多个初解，相应地可生成多棵树。
不同的树有不同的初解（根），不同的初解，即mathe所言基本解，是不会存在递推关系的。因为，存在递推关系的两个解，必有一个不是基本解。