论文部分内容阅读
在Python的学习过程中，通过编写程序来解决一些实际问题，也是一种乐趣。在数学史上，关于数论的著名世界难题很多，了解数学家们如何破解这些难题让人深受启发和鼓舞。今天我们就用Python来简单地验证费马大定理。
费马大定理，又称费马问题，是数论中最著名的世界难题之一。
概括来说就是当整数n>2时，关于x，y，z的方程xn+yn=zn，无正整数解。
你看这个方程是不是和求勾股数的类似，只是2次方变成了n次方，我们后面的验证，也是根据这个思路进行的。
看到这个定理内容，就想到了勾股数，我们用Python编写程序，在一定取值范圍内验证费马大定理。
如果想了解更深入的知识，大家可以参考相关资料。今天我们利用Python只做简单的验证。
根据《趣味数学——勾股数》一文的分析，勾股数是平方，这里就变成了大于2的正整数，程序设计不难，验证的范围越大，幂次越高，时间复杂度会几何级数增大，大家可以自行测试。
1. 费马大定理：
根据勾股数的例子，我们不难写出Python程序。代码如图1。
程序中有三重for循环，外层循环，即是输入的最大范围，然后再确定指数幂，在1～n整数范围内逐个验证，如果有满足条件的x，y，标记s=1，然后输出屏幕，否则继续验证，如果s=0的值没有改变，即没找到任何满足条件的数，则输出无整数解（图2）。
2. 时间复杂度（等级考试四级内容）
在循环的开始和结束，加上计时器，测试发现，指数为3时，在100范围内耗时大约0.28秒，200范围内耗时1.94秒，500范围内耗时36.28秒。而指数为4时，100、200、500范围内分别耗时0.39秒、1.92秒、60.62秒。随着数值的增大，需要的时间也更长（图3）。
时间复杂度就要根据你输入的范围决定了。比如100，那时间复杂度即为100万。
如果范围再增大，则时间复杂度也会增大，需要的时间就会更长。
通过测试，在一定范围内，均得到了验证，但数值过大时，用时较长。当然我们要证明一个定理，不可能把所有值都验证，还需要理论上的证明。
因此费马大定理程序，可以利用pow（）函数进行改进，减小时间复杂度（图4）。
pow（x，y）函数表示的是xy，0<y<1，即是开方运算。开n次方根的值取整与其相等，则说明这个值为整数的n次方。将程序修改为pow（pow（x，n）+pow（y，n），1/n）。运行结果是一样的（图5）。
历经多年，经过多位数学家的研究和证明，费马大定理得到了一步步的成果。《中国数学会通讯》1987年第2期据国外消息报道，费马猜想近年来取得了惊人的研究成果：格朗维尔和希思·布龙证明了「对几乎所有的指数，费马大定理成立」。即若命N（x）表示在不超过x的整数中使费马猜想不成立的指数个数，则证明中用到了法尔廷斯（Faltings）的结果。另外一个重要结果是：费马猜想若有反例，即存在x>0，y>0，z>0，n>2，使xn+yn=zn，则x>101800000。直到1994年10月英国数学家安德鲁·怀尔斯（Andrew Wiles）终于证明了费马大定理，为这个从1637年至今的数学谜题画上了圆满的句号。
我们这里只是做个简单的、基本的验证，希望大家能发挥自己的智慧和力量，进一步研究和探讨，找到一个更好的算法，来证明费马大定理！
一、费马大定理简介
费马大定理，又称费马问题，是数论中最著名的世界难题之一。
概括来说就是当整数n>2时，关于x，y，z的方程xn+yn=zn，无正整数解。
你看这个方程是不是和求勾股数的类似，只是2次方变成了n次方，我们后面的验证，也是根据这个思路进行的。
二、创意来源
看到这个定理内容，就想到了勾股数，我们用Python编写程序，在一定取值范圍内验证费马大定理。
如果想了解更深入的知识，大家可以参考相关资料。今天我们利用Python只做简单的验证。
三、设计思路
根据《趣味数学——勾股数》一文的分析，勾股数是平方，这里就变成了大于2的正整数，程序设计不难，验证的范围越大，幂次越高，时间复杂度会几何级数增大，大家可以自行测试。
四、程序设计
1. 费马大定理：
根据勾股数的例子，我们不难写出Python程序。代码如图1。
程序中有三重for循环，外层循环，即是输入的最大范围，然后再确定指数幂，在1～n整数范围内逐个验证，如果有满足条件的x，y，标记s=1，然后输出屏幕，否则继续验证，如果s=0的值没有改变，即没找到任何满足条件的数，则输出无整数解（图2）。
2. 时间复杂度（等级考试四级内容）
在循环的开始和结束，加上计时器，测试发现，指数为3时，在100范围内耗时大约0.28秒，200范围内耗时1.94秒，500范围内耗时36.28秒。而指数为4时，100、200、500范围内分别耗时0.39秒、1.92秒、60.62秒。随着数值的增大，需要的时间也更长（图3）。
时间复杂度就要根据你输入的范围决定了。比如100，那时间复杂度即为100万。
如果范围再增大，则时间复杂度也会增大，需要的时间就会更长。
五、测试与改进
通过测试，在一定范围内，均得到了验证，但数值过大时，用时较长。当然我们要证明一个定理，不可能把所有值都验证，还需要理论上的证明。
因此费马大定理程序，可以利用pow（）函数进行改进，减小时间复杂度（图4）。
pow（x，y）函数表示的是xy，0<y<1，即是开方运算。开n次方根的值取整与其相等，则说明这个值为整数的n次方。将程序修改为pow（pow（x，n）+pow（y，n），1/n）。运行结果是一样的（图5）。
历经多年，经过多位数学家的研究和证明，费马大定理得到了一步步的成果。《中国数学会通讯》1987年第2期据国外消息报道，费马猜想近年来取得了惊人的研究成果：格朗维尔和希思·布龙证明了「对几乎所有的指数，费马大定理成立」。即若命N（x）表示在不超过x的整数中使费马猜想不成立的指数个数，则证明中用到了法尔廷斯（Faltings）的结果。另外一个重要结果是：费马猜想若有反例，即存在x>0，y>0，z>0，n>2，使xn+yn=zn，则x>101800000。直到1994年10月英国数学家安德鲁·怀尔斯（Andrew Wiles）终于证明了费马大定理，为这个从1637年至今的数学谜题画上了圆满的句号。
我们这里只是做个简单的、基本的验证，希望大家能发挥自己的智慧和力量，进一步研究和探讨，找到一个更好的算法，来证明费马大定理！