立方数最小和问题

gxqcn

原帖由 无心人 于 2008-5-12 21:22 发表 ... 现在我猜测存在28的6次划分，32的7次划分

如果不是从和、平方和、立方和。。。起，连续等幂和对应相等， 则得到的数组不具备可平移特性，应用价值将大打折扣。

无心人

只能过1次幂

mathe

不是连续幂很容易计算的

无心人

好吧 我先把4的从20到28的都计算一遍 5的从24到44都计算一遍 看有收获么

gxqcn

将前 N 个正整数平分成两组，使每组 R 次方和相等，有如下结果：

N	R	count
20	4	4
24	5	3
28	5	2
32	6	7
36	5	16
40	5	215
44	6	36
48	8	3
52	7	94
56	8	28
60	9	1

例如：

N = 60 R = 9 No.1 60, 57, 55, 54, 50, 49, 48, 45, 44, 43, 42, 39, 38, 37, 35, 32, 30, 28, 27, 23, 20, 19, 13, 9, 8, 7, 6, 5, 4, 3

更全面的结果请见附件压缩包。

mathe

原帖由 gxqcn 于 2008-5-13 08:14 发表 将前 N 个正整数平分成两组，使每组 R 次方和相等，有如下结果： NRcount204424532852326736516405215446364883 例如： 有参考价值的数据更全面的结果请见附件压缩包。

你是用动态规划还是穷举的方法？

gxqcn

我不知道该算法的术语名称（因为非科班出身）， 感觉是回溯法，可保证穷举（运用了些数学知识进行加速）。 另，刚才又增加了 N=52,56,60 三种情形的最佳结果，请重新下载附件更新。

gxqcn

刚才又试着运行了一下 N=64 的情形， 其中 R=10 和 R=9 均无解； R = 8 时运行了 10min 左右，产生了 2965 组结果， 考虑到解可能太多，提前终止了运行。

无心人

小于32，4次幂无连续等幂和的序列 刚才搜索完的 To GxQ 5次的，从32到44你都搜索过么？

gxqcn

我搜索过，从32到44不存在5次等幂和划分。 这里的5次要求：个数、和、平方和、立方和、4次方和、5次方和对应相等。 （即划分后的两组数从0次到5次等幂和对应相等）