两个立方体的边长问题

lulijie

X和Y 都在100317以内   无解，费时6分7秒时间。

金眼睛

虽然数不是很大，还是动用了我的大数计算程序，呵呵！

思路：让z从1至无穷。设x大于y，则x在[(17/2)^(1/3)*z]与[17^(1/3)*z]之间。
用x，z推算y，并使y圆整为整数，计算p=x^3+y^3-17*z^3，以p最小作为限定，可以保存最佳结果。

p=0，则满足题意。

给出其中一个结果，耗时2分钟左右：

x=104940;y=11663;z=40831。

比较有意思的是，这三个数都是合数，但两两互质。

lulijie

用X和Y求z，有个问题 ，就是每次都要规定一个范围，若寻找不到，把范围扩大后，又要从头算起。
而金眼睛的方法，从z来找x和y，最大的好处就是不需要规定z的范围，就算规定了范围，若寻找不到，下次还可以从这个范围开始寻找，不用重复工作。还有他规定X大于Y，来优化算法，比规定X小于Y，来优化算法速度快的多。
速度比等于2^（1/3）-1  =1：4。
很好，考虑的很全面。

yang_bigarm

原帖由 金眼睛 于 2009-3-29 21:57 发表
虽然数不是很大，还是动用了我的大数计算程序，呵呵！

思路：让z从1至无穷。设x大于y，则x在[(17/2)^(1/3)*z]与[17^(1/3)*z]之间。
用x，z推算y，并使y圆整为整数，计算p=x^3+y^3-17*z^3，以p最小作为限定，可以 ...

两分钟？那么快啊，牛

[ 本帖最后由 yang_bigarm 于 2009-3-29 23:37 编辑 ]

tonylmd

我也觉得 这题的解决靠算法的优化…
各位能否都发布一下算法？学习学习…

ggglgq

　　
　　　　
　　
　　这个题目应该是比较难的数论问题！ 比如 歌德巴赫猜想就是数论问题。
　　
　　　　
　　楼主的题目是数论问题中比较棘手的不定方程问题！比如 费尔马大定理
  
就是很棘手的不定方程问题！
  
  
    关于楼主的 不定方程 问题，大家可对照一下《三元三次不定方程》
  
    http://www.docin.com/p-102258.html
　　
　　
　　
　　　　
　　

lulijie

用金眼睛的算法精神，我设计了一下，发现算出结果要20分钟。
而金眼睛只需要2分钟，不知如何实现的。
我估计一下时间。
金眼睛的算法，z没有优化，x优化后节约时间约4倍。
所以总共节约时间4倍。
我的算法，按理论讲，应该节约34倍时间，应该速度更快，但苦于事先需设定搜索范围，范围设小了，搜寻不到结果，范围设大了，又浪费时间。
我想了一个办法，改变循环进行的次序，既能理论上节约34倍时间，又不用事先设定范围。大家看看有没道理。
原先：
         X=17*i+p   ，  Y=17*j-p        p=0 to 8
      两个嵌套for 循环
             for i=0 to  m               m为事先设定的范围。
                   for j=1 to m
                         ......
                   next j
             next  i
-------------------------------------------
修改为：
        X=17*i+p   ，  Y=17*j+17-p        p=0 to 8

       m=0                                    ‘m为i和j之间的最大值
       do  while true
                i=m                            ’i先固定为m
                for j=0 to m
                         ......                   ‘j 从小到大循环
                next j  


                 j=m                             ’j再固定为m
                for i=0 to m-1
                         ......                    ‘i从小到大循环
                next i  


                m=m+1                       ’m逐渐增加
       loop
-------------------------------------------------------------------------
重新运行程序，  花费407秒得出结果，不到7分钟时间。

金眼睛

呵呵，借工作之便用工作站算的，办公电脑5~6分钟也应该搞定了。

周日匆忙，没来得及说一个规律，这就是x，y，z对3求余结果互不相同。

原因如下：任何一个正整数的3次方对9求余的结果有三种：0，1，8。

考虑x^3+y^3=17*z^3的尾数情况，可以得到前面的结论。

当然，x，y，z也可以同时对3求余余零，但这样等式两边可以约掉27，也就是说解已经存在（正整数倍的都算一个解）。

再补充一个结果，z直到88000也还只有40831及其2倍81662两个解，有兴趣的朋友可以接着这个结果继续算。

yang_bigarm

原帖由 ggglgq 于 2009-3-30 02:59 发表
　　
　
　　这个题目应该是比较难的数论问题！

如果你把他看做是一个纯粹的数论问题，那么你可以考虑不用编程，直接用纸和笔再加上一个科学计算器
来解决这个问题，当然这样做会很难。因此我希望的是大家从算法的优化角度来攻克这个问题，我今天就
看到这个版上的几位朋友提出了很多优化的方法，很佩服你们的勤于思考的精神。

金眼睛

lulijie的想法很好，可以跟我的想法结合一下么，这样就更好了，呵呵！每次来得匆忙，别人的观点都没仔细看。

lulijie注意到x，y的和为17的整数倍，这不难证明，很好，我想这样就可以把原方程转化一下了。

设x+y=A=17*m，x-y=B

原方程变为：(A+B)^3+(A-B)^3=8*17*z^3    ->   A^3+3*A*B^2=4*17*z^3  ->  289*m^3+3*m*B^2=4*z^3

由于B<17m，得到m的范围为：ceil(17^(1/3)/17*z)<=m<=floor(68^(1/3)/17*z)，这样程序运行就快多了 ：）