求把N表为最短幂和的快速方法
把任意大整数N表为`a^b+c^d+e^f`这样的幂和形式（幂指数b, d, f不小于2），加项越少越好。a,b,c,d,e,f等都为一定范围（暂定`2^{16}`以内）的整数,有没有快速的实现方法？
假如以表的形式返回最优结果，并以f(n)表示表的长度，例如
list(1)={(1,∞)}， f(1)=1
list(2)={(1,∞), (1,∞)}， f(2)=2
list(3)={(1,∞), (1,∞), (1,∞)}，f(3)=3
list(4)={(2,2)}， f(4)=1
那么list(12345678987654321)=？，f(12345678987654321)=? 由拉格朗日四平方数定理可知f(n)≤4.
现在允许加入更高次的幂，对于充分大以后的 n , 可否使得f(n)≤3?
用M10编一递归函数可计算至n=368，结果f(n)=4的有8个：
{7，15，23，87，111，119，167，335}，
单幂27个，f(n)=2的有179个，f(n)=3的有154个。
n= 50000
lab =Union@@Table, {a, 2, Sqrt}]
fList = {1, 2, 3}
Do[
If,
AppendTo,
AppendTo]],
{x, 4, n}]
fList
Tally@fList
Position
非递归程序，计算到n=50000的结果：
项数为1，2，3，4的频数：{{1, 262}, {2, 17574}, {3, 32149}, {4, 15}}
其中项数为4的：{7, 15, 23, 87, 111, 119, 167, 335, 1391, 1455, 1607, 1679, 1991, 25887, 26375} 那怎么快速求一个数N的4个数的平方呢，有什么妙法吗 4平方定理是包含了1^2,如果我们去除这个情况，就没有这么好的结论了 首先将所有冪列出有4,8,9,16,25,27,32,36,49,64,81,100,121,125,144,…
然后双幂之和有12,13,16,18,20,29,31,33,34,35,40,41,43,44,45,48,50,52,53,54,57,58,59,61,63,65,68,72,73,74,76,80,85,89,90,91,96,97,98,104,106,107,108,109,113,116,117,125,127,129,130,132,133,134,136,137,148
由以上俩数列相加可得三幂之和等
不可表示的数
首先，4是幂，对于n=4a，可以表为a个4同理，9是幂，对于n=9b，可以表为b个9
于是所有的n=4a+9b都是可表示的。漏网之鱼少而有限，不难穷举：
1） n=4m+1==4(m-2)+9， m<2例外:{1, 5}.
2） n=4m+2==4(m-4)+2·9，m<4例外:{2, 6, 10, 14}.
3） n=4m+3==4(m-6)+3·9，m<6例外:{3, 7, 11, 15, 19, 23}.
共计12个数。 4#的结果是允许1为底数的，算法基于以下公式：
对于非单幂的自然数`n`,有
`\D f(n)=\min_{i=1}^{n/2}\{f(i)+f(n-i)\}`
这个公式可以略加改进如下：
`\D f(n)=\min_{f(i)=1}^{n/4\le i\lt n} \{1+f(n-i)\}`
上述公式由`f(a+b)\le f(a)+f(b)`遍搜而成。第一式搜遍较小的和式，搜索规模为 `n`，第二式则只需要搜遍含单幂数的和式,搜索规模约为`\sqrt n`。
比如n=50000时，前者搜索规模为25000，后者为124。
能够表示的数中好像除了30,46,151,55,87,119,167,111,335,1679,1455,1607,26375,1991,1391,25887都可以表示为不超过3个数之和？
页:
[1]
2