求把N表为最短幂和的快速方法

qianyb

把任意大整数N表为`a^b+c^d+e^f`这样的幂和形式（幂指数b, d, f不小于2），加项越少越好。
a,b,c,d,e,f等都为一定范围（暂定`2^{16}`以内）的整数,有没有快速的实现方法？

aimisiyou

假如以表的形式返回最优结果，并以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)=?

hujunhua

由拉格朗日四平方数定理可知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个。

hujunhua

1. n= 50000
   
2. lab =Union@@Table[PowerRange[a^2, n, a], {a, 2, Sqrt[n]}]
   
3. fList = {1, 2, 3}
   
4. Do[
   
5. If[MemberQ[lab, x],
   
6. AppendTo[fList, 1],
   
7. AppendTo[fList, Min[fList + Reverse@fList]]],
   
8. {x, 4, n}]
   
9. fList
   
10. Tally@fList
    
11. Position[fList,4]

复制代码

非递归程序，计算到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}

qianyb

那怎么快速求一个数N的4个数的平方呢，有什么妙法吗

mathe

4平方定理是包含了1^2,如果我们去除这个情况，就没有这么好的结论了

mathe

首先将所有冪列出有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

由以上俩数列相加可得三幂之和等

mathe

首先，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个数。

hujunhua

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。

mathe

能够表示的数中好像除了30,46,151,55,87,119,167,111,335,1679,1455,1607,26375,1991,1391,25887都可以表示为不超过3个数之和？