立方数最小和问题

mathe

我先将k=2,3,4的结果贴出来，看看能否找出一些规律。
显然，根据上面的结论，对于任意k,我们只要找出对于$2^{k+1}-2<=n<2^{k+2}-2$情况下和为0和1的方案就可以了。
对于k=2,我们有:
-6^2+5^2-4^2+3^2+2^2+1^2
-7^2+6^2-5^2+4^2+3^2+2^2+1^2
-8^2+7^2-6^2+5^2+4^2+3^2+2^2-1^2
-9^2+8^2-7^2+6^2+5^2+4^2-3^2-2^2+1^2
-10^2+9^2+8^2-7^2+6^2-5^2-4^2+3^2+2^2-1^2
-11^2+10^2-9^2+8^2-7^2+6^2+5^2+4^2+3^2+2^2-1^2
-12^2+11^2-10^2-9^2+8^2+7^2+6^2+5^2+4^2+3^2+2^2+1^2
-13^2+12^2-11^2+10^2-9^2+8^2+7^2-6^2+5^2+4^2+3^2+2^2-1^2

mathe

对于k=3,我们有
        -14^3+13^3+12^3-11^3+10^3-9^3-8^3+7^3+6^3-5^3-4^3+3^3-2^3+1^3
        -15^3-14^3+13^3+12^3+11^3-10^3+9^3+8^3+7^3+6^3+5^3-4^3+3^3-2^3-1^3
        -16^3+15^3-14^3+13^3+12^3-11^3+10^3-9^3+8^3+7^3-6^3-5^3+4^3+3^3-2^3+1^3
        -17^3+16^3-15^3-14^3+13^3+12^3+11^3+10^3-9^3+8^3+7^3+6^3+5^3+4^3+3^3+2^3+1^3
        -18^3+17^3-16^3+15^3-14^3+13^3+12^3+11^3-10^3+9^3-8^3-7^3+6^3+5^3-4^3-3^3+2^3-1^3
        -19^3-18^3+17^3+16^3+15^3-14^3+13^3+12^3-11^3+10^3-9^3+8^3-7^3+6^3-5^3-4^3-3^3+2^3+1^3
        -20^3-19^3-18^3+17^3+16^3+15^3+14^3+13^3+12^3-11^3+10^3+9^3+8^3+7^3+6^3+5^3-4^3+3^3+2^3+1^3
        -21^3+20^3-19^3-18^3+17^3-16^3+15^3+14^3+13^3+12^3+11^3+10^3+9^3-8^3+7^3+6^3-5^3+4^3+3^3+2^3+1^3
        -22^3-21^3-20^3+19^3+18^3+17^3+16^3-15^3+14^3+13^3+12^3+11^3+10^3-9^3+8^3+7^3+6^3+5^3+4^3+3^3+2^3+1^3
        -23^3-22^3-21^3+20^3+19^3+18^3-17^3+16^3+15^3+14^3+13^3+12^3+11^3-10^3+9^3+8^3+7^3+6^3-5^3+4^3+3^3+2^3+1^3
        -24^3-23^3-22^3+21^3+20^3+19^3-18^3+17^3+16^3+15^3+14^3+13^3-12^3+11^3+10^3-9^3+8^3+7^3+6^3-5^3+4^3+3^3+2^3+1^3
        -25^3-24^3-23^3-22^3+21^3+20^3+19^3+18^3+17^3+16^3+15^3+14^3+13^3+12^3+11^3+10^3+9^3-8^3+7^3+6^3+5^3-4^3+3^3+2^3+1^3
        -26^3-25^3-24^3+23^3-22^3+21^3+20^3+19^3+18^3+17^3+16^3+15^3+14^3-13^3+12^3-11^3+10^3+9^3+8^3-7^3+6^3+5^3-4^3+3^3+2^3+1^3
        -27^3-26^3-25^3-24^3+23^3+22^3+21^3+20^3+19^3+18^3+17^3-16^3+15^3+14^3+13^3+12^3+11^3+10^3+9^3-8^3+7^3-6^3+5^3+4^3+3^3+2^3+1^3
        -28^3-27^3-26^3-25^3+24^3+23^3+22^3+21^3+20^3+19^3+18^3+17^3-16^3+15^3+14^3-13^3+12^3+11^3-10^3+9^3+8^3-7^3+6^3+5^3+4^3+3^3+2^3+1^3
        -29^3-28^3-27^3-26^3+25^3+24^3+23^3+22^3+21^3-20^3+19^3+18^3+17^3+16^3+15^3+14^3+13^3-12^3+11^3+10^3-9^3+8^3-7^3+6^3-5^3-4^3-3^3+2^3+1^3

mathe

对于k=4
        -30^4-29^4-28^4+27^4+26^4-25^4+24^4+23^4+22^4+21^4+20^4+19^4+18^4+17^4-16^4+15^4-14^4+13^4+12^4+11^4+10^4-9^4+8^4-7^4-6^4+5^4-4^4+3^4+2^4+1^4
        -31^4-30^4-29^4+28^4-27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4+19^4+18^4-17^4+16^4+15^4+14^4-13^4+12^4-11^4+10^4+9^4+8^4+7^4+6^4+5^4+4^4+3^4+2^4+1^4
        -32^4-31^4-30^4-29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4+19^4+18^4-17^4+16^4+15^4+14^4-13^4+12^4-11^4+10^4+9^4-8^4-7^4+6^4+5^4-4^4-3^4-2^4-1^4
        -33^4-32^4-31^4-30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4-19^4+18^4-17^4+16^4+15^4+14^4-13^4+12^4+11^4+10^4+9^4-8^4+7^4-6^4+5^4-4^4+3^4+2^4+1^4
        -34^4+33^4+32^4-31^4+30^4-29^4-28^4+27^4+26^4-25^4-24^4+23^4-22^4+21^4+20^4-19^4+18^4-17^4-16^4+15^4-14^4+13^4+12^4-11^4-10^4+9^4+8^4-7^4+6^4-5^4-4^4+3^4+2^4-1^4
        -35^4-34^4-33^4-32^4+31^4+30^4+29^4+28^4+27^4+26^4-25^4+24^4+23^4+22^4+21^4+20^4+19^4-18^4+17^4+16^4+15^4-14^4+13^4+12^4-11^4-10^4+9^4+8^4-7^4-6^4-5^4+4^4-3^4+2^4+1^4
        -36^4-35^4-34^4-33^4+32^4+31^4+30^4+29^4-28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4+19^4+18^4-17^4+16^4-15^4+14^4+13^4+12^4-11^4+10^4-9^4+8^4+7^4-6^4-5^4+4^4+3^4+2^4+1^4
        -37^4+36^4-35^4+34^4-33^4+32^4-31^4+30^4-29^4+28^4+27^4-26^4+25^4+24^4-23^4+22^4-21^4+20^4-19^4+18^4+17^4-16^4-15^4+14^4+13^4-12^4-11^4+10^4+9^4-8^4-7^4+6^4+5^4-4^4+3^4+2^4+1^4
        -38^4-37^4-36^4-35^4+34^4-33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4+19^4+18^4-17^4+16^4+15^4-14^4+13^4+12^4+11^4+10^4+9^4-8^4-7^4+6^4+5^4+4^4-3^4+2^4+1^4
        -39^4-38^4-37^4-36^4+35^4-34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4-21^4+20^4+19^4+18^4-17^4+16^4+15^4+14^4+13^4-12^4-11^4+10^4-9^4+8^4+7^4-6^4-5^4+4^4-3^4-2^4-1^4
        -40^4-39^4-38^4-37^4-36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4-21^4+20^4+19^4+18^4-17^4+16^4-15^4+14^4-13^4+12^4-11^4+10^4+9^4-8^4-7^4+6^4+5^4+4^4+3^4+2^4+1^4
        -41^4-40^4-39^4-38^4-37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4-27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4+19^4+18^4+17^4-16^4+15^4+14^4-13^4+12^4+11^4-10^4-9^4+8^4-7^4+6^4-5^4+4^4+3^4+2^4+1^4
        -42^4-41^4-40^4-39^4-38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4-26^4+25^4-24^4+23^4+22^4+21^4+20^4+19^4-18^4+17^4-16^4+15^4+14^4+13^4+12^4+11^4+10^4+9^4-8^4+7^4+6^4+5^4+4^4+3^4+2^4+1^4
        -43^4-42^4-41^4-40^4-39^4+38^4+37^4+36^4+35^4+34^4+33^4-32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4-20^4+19^4+18^4+17^4-16^4+15^4-14^4+13^4+12^4-11^4+10^4-9^4-8^4+7^4-6^4+5^4+4^4+3^4+2^4+1^4
        -44^4-43^4-42^4-41^4-40^4+39^4+38^4+37^4+36^4-35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4-20^4+19^4+18^4+17^4-16^4+15^4+14^4-13^4+12^4-11^4+10^4-9^4+8^4-7^4+6^4+5^4+4^4-3^4-2^4-1^4
        -45^4-44^4-43^4-42^4-41^4+40^4+39^4+38^4+37^4-36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4-24^4+23^4-22^4+21^4+20^4+19^4+18^4+17^4+16^4+15^4-14^4+13^4+12^4+11^4+10^4+9^4-8^4+7^4+6^4+5^4+4^4-3^4+2^4+1^4
        -46^4-45^4-44^4-43^4-42^4+41^4-40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4-20^4+19^4+18^4+17^4-16^4-15^4+14^4+13^4-12^4+11^4-10^4-9^4+8^4+7^4-6^4+5^4-4^4-3^4-2^4-1^4
        -47^4-46^4-45^4-44^4-43^4-42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4-22^4+21^4+20^4+19^4-18^4+17^4+16^4-15^4+14^4-13^4+12^4+11^4-10^4+9^4-8^4-7^4+6^4+5^4-4^4-3^4-2^4-1^4
        -48^4-47^4-46^4-45^4-44^4-43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4-27^4+26^4+25^4+24^4+23^4+22^4-21^4+20^4+19^4-18^4+17^4+16^4+15^4+14^4-13^4-12^4+11^4+10^4-9^4-8^4+7^4-6^4-5^4+4^4-3^4+2^4-1^4
        -49^4-48^4-47^4-46^4-45^4-44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4-32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4-21^4+20^4+19^4+18^4-17^4+16^4-15^4+14^4-13^4+12^4-11^4+10^4-9^4+8^4+7^4-6^4-5^4-4^4-3^4-2^4-1^4
        -50^4-49^4-48^4-47^4-46^4-45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4-34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4-26^4+25^4+24^4+23^4+22^4-21^4+20^4+19^4+18^4+17^4+16^4-15^4+14^4+13^4+12^4+11^4-10^4+9^4+8^4-7^4-6^4+5^4-4^4+3^4+2^4+1^4
        -51^4-50^4-49^4-48^4-47^4-46^4+45^4+44^4+43^4+42^4+41^4+40^4+39^4-38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4-24^4+23^4+22^4+21^4-20^4+19^4+18^4-17^4+16^4-15^4+14^4-13^4-12^4+11^4+10^4-9^4+8^4-7^4+6^4-5^4-4^4-3^4-2^4-1^4
        -52^4-51^4-50^4-49^4-48^4-47^4+46^4+45^4+44^4+43^4+42^4-41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4-27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4-19^4+18^4+17^4-16^4+15^4+14^4+13^4-12^4+11^4-10^4-9^4+8^4+7^4-6^4+5^4-4^4-3^4-2^4-1^4
        -53^4-52^4-51^4-50^4-49^4-48^4+47^4+46^4-45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4-24^4+23^4+22^4+21^4+20^4+19^4+18^4+17^4-16^4+15^4+14^4+13^4-12^4+11^4-10^4+9^4+8^4+7^4+6^4+5^4+4^4+3^4+2^4+1^4
        -54^4-53^4-52^4-51^4-50^4-49^4+48^4-47^4+46^4+45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4-24^4+23^4+22^4-21^4+20^4+19^4+18^4-17^4+16^4-15^4+14^4+13^4-12^4-11^4+10^4-9^4+8^4+7^4-6^4+5^4+4^4+3^4-2^4-1^4
        -55^4-54^4-53^4-52^4-51^4-50^4-49^4+48^4+47^4+46^4+45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4-27^4+26^4+25^4+24^4+23^4-22^4+21^4+20^4+19^4-18^4+17^4-16^4+15^4-14^4+13^4-12^4+11^4-10^4+9^4+8^4-7^4+6^4+5^4-4^4+3^4-2^4-1^4
        -56^4-55^4-54^4-53^4-52^4-51^4-50^4+49^4+48^4+47^4+46^4+45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4-33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4-23^4+22^4-21^4+20^4+19^4+18^4-17^4+16^4-15^4+14^4-13^4-12^4+11^4+10^4-9^4-8^4+7^4-6^4+5^4+4^4+3^4+2^4+1^4
        -57^4-56^4-55^4-54^4-53^4-52^4-51^4+50^4+49^4+48^4+47^4+46^4+45^4+44^4+43^4+42^4+41^4+40^4-39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4-22^4+21^4+20^4+19^4-18^4-17^4+16^4-15^4+14^4+13^4-12^4-11^4+10^4+9^4-8^4+7^4-6^4+5^4+4^4+3^4+2^4-1^4
        -58^4-57^4-56^4-55^4-54^4-53^4-52^4+51^4+50^4+49^4+48^4+47^4+46^4+45^4-44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4+21^4+20^4-19^4+18^4+17^4+16^4+15^4-14^4+13^4+12^4+11^4-10^4-9^4+8^4+7^4-6^4+5^4+4^4+3^4+2^4+1^4
        -59^4-58^4-57^4-56^4-55^4-54^4-53^4+52^4+51^4+50^4+49^4+48^4+47^4-46^4+45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4-23^4+22^4-21^4+20^4-19^4+18^4+17^4+16^4-15^4+14^4-13^4+12^4-11^4+10^4-9^4-8^4+7^4+6^4-5^4-4^4+3^4-2^4-1^4
        -60^4-59^4-58^4-57^4-56^4-55^4-54^4+53^4+52^4+51^4+50^4-49^4+48^4+47^4+46^4+45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4-24^4+23^4+22^4-21^4+20^4-19^4+18^4-17^4+16^4-15^4+14^4+13^4-12^4-11^4+10^4+9^4-8^4-7^4+6^4-5^4+4^4+3^4+2^4+1^4
        -61^4-60^4-59^4-58^4-57^4-56^4-55^4+54^4-53^4+52^4+51^4+50^4+49^4+48^4+47^4+46^4+45^4+44^4+43^4+42^4+41^4+40^4+39^4+38^4+37^4+36^4+35^4+34^4+33^4+32^4+31^4+30^4+29^4+28^4+27^4+26^4+25^4+24^4+23^4+22^4-21^4+20^4+19^4+18^4+17^4-16^4+15^4+14^4+13^4+12^4-11^4-10^4+9^4+8^4-7^4+6^4-5^4+4^4+3^4+2^4+1^4

无心人

能解释下你的结果么？

mathe

上面这些表达是计算结果都应该是0,1或-1,也就是对于$k=2,3,4,2^{k+1}-2<=n<2^{k+2}-2$,我们都找到了k次幂和差绝对值为0和1的方案。
按照26#的推导方法我们知道，对于k次幂情况$n+2^{k+1}$情况下和差绝对值的最小值不大于$n$情况下的和差最小值。所以我们可以得出对于$n>=2^{k+1}-2$均有对应k次幂和差的绝对值最小值不大于1（所以就是0或1）。也就是说30#的猜想对于$k<=4$都成立。
上面的结果都是用计算机算出来的。当然如果要证明k=5成立，我们就要对于$62<=n<126$的情况都构造一个结果为0或1的方案，越大的k，需要构造的范围越大，所以难度越大。而且这种方法不能证明对于所有的k结果30#猜想都成立。

无心人

排列组合数量是否是二的方幂？

mathe

原帖由 无心人 于 2008-5-4 09:28 发表


排列组合数量是否是二的方幂？

不懂，啥叫排列组合数量？组合数？

无心人

我的意思是你说的k=5需要检测多少例子？

mathe

一一检查应该是不可行的。对于k<=4,我采用的是动态规划的方法。对于K>=5,不仅仅时间复杂度，主要是空间复杂度也会出现问题。不过根据k<=4结果来看，如果只需要找到任意一个解，应该不需要检查所有情况，只需要看一部分特殊数据，所以我们应该可以设计一些特殊算法解决比较小的K(如K=5等），但是我们还是不能证明对所有的K都成立

gxqcn

可否请你罗列出 N=160, k=5 的所有情形？
本想自己写程序的，如果你那里方便改代码测试的话，请将：
　　前 160 个正整数 5 次方代数和为零的情形全部罗列出来。