立方数最小和问题

无心人

下面就是面对的56-92的庞大的组合数字了

我怀疑64或者80可能存在连续6次幂结果

无心人

郭：
打个商量，你做个源代码，不许用大数库，也应该用不到
要能保存状态，每10分钟保存一次，用文件下次能继续搜索
我挂我服务器上一个星期看下结果
从可能的下界搜索到92

如果可能，最好尽量汇编化

：）

gxqcn

不需要大数库，但要用到64bit数据类型（如在64bitOS下就好了）。
程序我还在进一步优化中，应该还不到要用服务器的地步。

无心人

用到了
服务器能连续开30天
你家机器不敢

服务器同样频率比你家机器快2-3倍

gxqcn

原帖由 gxqcn 于 2008-5-7 20:57 发表
...
我曾猜想：“连续 $2^{r+1}$ 个整数可 $r$ 次等幂和划分；且划分形式是唯一的”。
存在性容易证明，唯一性未证明。 ...

现在“唯一性”的猜想被推翻了！

N = 64  R = 5

No.1    1, 2, 7, 8, 10, 13, 15, 16, 17, 18, 19, 22, 25, 28, 31, 32, 33, 34, 37, 40, 43, 46, 47, 48, 49, 50, 52, 55, 57, 58, 63, 64
No.2    1, 4, 6, 7, 10, 11, 13, 16, 18, 19, 21, 24, 25, 28, 30, 31, 34, 35, 37, 40, 41, 44, 46, 47, 49, 52, 54, 55, 58, 59, 61, 64
No.3    1, 4, 6, 8, 10, 11, 13, 14, 16, 19, 22, 25, 28, 29, 30, 31, 34, 35, 36, 37, 40, 43, 46, 49, 51, 52, 54, 55, 57, 59, 61, 64

------ finished! ------

注：上面的结果仅给出了划分后的一半数据，另一半是其补集。

无心人

恭喜得到结果
现在就要看6的是否小于96了

mathe

想到一种计算将前N=2n个数(1~N)等分成两组,使得它们前r次幂和都相等,而要求r尽量大的方法.(可以同时判断这样的解是否存在)
我们知道如果两组数
$x_1,x_2,...,x_n$
$y_1,y_2,...,y_n$
它们的前r次幂之和都相等,那么我们将多项式
$(x-x_1)(x-x_2)....(x-x_n)$
和
$(x-y_1)(x-y_2)...(x-y_n)$
展开,那么除了首项均为1以外,它们其余高次的r项也都相等,也就是多项式
$(x-x_1)(x-x_2)....(x-x_n)-(x-y_1)(x-y_2)...(x-y_n)$的次数为n-r-1.
所以如果1~N存在一次前r次幂和都相同的划分
也就是多项式$\prod_{t=1}^{N}(x-t)$可以分解成两个n次多项式的乘积,而且这两个多项式的前1+r项系数相等.
于是我们可以非常容易计算出这两个n次多项式的前r+1项系数.
此后,我们可以通过待定系数法假设方程余下的系数,可以得出一组关于系数的方程组,然后确定方程组是否有整数解就可以了.
而实际上通常可以非常容易的判定.
比如现在以N=8为例子,我们可以得出
$(x-8)*(x-7)*(x-6)*(x-5)*(x-4)*(x-3)*(x-2)*(x-1)=x^8-36*x^7+546*x^6-4536*x^5+22449*x^4-67284*x^3+118124*x^2-109584*x+40320$
我们先构造一个辅助多项式$x^4-18*x^3+111*x^2-270*x+204$
使得$(x^4-18*x^3+111*x^2-270*x+204)^2-(x-8)*(x-7)*(x-6)*(x-5)*(x-4)*(x-3)*(x-2)*(x-1)=64*x^2-576*x+1296$
类似的,对于通常的N=2n,我们可以构造一个整多项式使得其平方同我们的这个目标多项式差的次数不高于n-2次. (容易证明最多n-1次,但是我试验了几个例子都正好是n-2次)
而对于这个例子中,后面的余项也是一个完全平方式即$(8*x-36)^2$,这样通过平方差公式,我们就可以将$(x-1)(x-2)...(x-8)$分解成两个需要的形式.

guxd

还隐藏什么答案啊，这问题好像以前做过