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

mathe

我们首先有结论 http://bbs.emath.ac.cn/forum.php ... D%CA%FD%D6%AE%BA%CD
所以在包含1的时候，不能用三个平方数之和表示的整数形如$4^a(8k+7)$
所以如果要查看充分大整数是否都是3个幂之和，之需要查看上面类型的数即可

hujunhua

mathe 发表于 2016-4-9 21:03
能够表示的数中好像除了30,46,151,55,87,119,167,111,335,1679,1455,1607,26375,1991,1391,25887都可以表示 ...

将4#程序中的初表改为fList={∞,∞,∞},即可计算加数不为1的结果，50000以内如下：
各种项数的频数分布：{{∞, 12}, {1, 261}, {2, 17485}, {3, 32226}, {4, 16}}

4#不拒1的频数分布： {{∞, 0}, {1, 262}, {2, 17574}, {3, 32149}, {4, 15}},

两相对比，频数分布变化不大

mathe

数值验证4000000以内需要4项以上都只有这么多项

1. #include <math.h>
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. #include <list>
   
6. using namespace std;
   
7. #define N 4000000
   
8. char cc[N];
   
9. list<int> nlist[8];
   
10. 
    
11. int main()
    
12. {
    
13.     int i,j,k,maxk=0;
    
14.     for(i=2;N>i*i;i++) cc[i*i]=1;
    
15.     for(i=2;N>i*i*i;i++)cc[i*i*i]=1;
    
16.     for(i=2;N>i*i*i*i*i;i++)cc[i*i*i*i*i]=1;
    
17.     for(i=2;N>i*i*i*i*i*i*i;i++)cc[i*i*i*i*i*i*i]=1;
    
18.     for(i=4;i<N;i*=2)cc[i]=1;
    
19.     for(i=9;i<N;i*=3)cc[i]=1;
    
20.     for(i=0;i<N;i++)if(cc[i]==1)nlist[0].push_back(i);
    
21. 
    
22.     for(k=1;k<=7;k++){
    
23.      list<int>::iterator it1;
    
24.      for(it1=nlist[0].begin();it1!=nlist[0].end();++it1){
    
25.         list<int>::iterator it2;
    
26.         for(it2=nlist[k-1].begin();it2!=nlist[k-1].end();++it2){
    
27.            int sum= *it1 + *it2;
    
28.            if(sum<N&&cc[sum]==0){
    
29.               cc[sum]=k+1;
    
30.            }
    
31.         }
    
32.      }
    
33.      for(i=0;i<N;i++)if(cc[i]==k+1){
    
34.         nlist[k].push_back(i);
    
35.      }
    
36.      if(k>=3){
    
37.         for(it1=nlist[k].begin();it1!=nlist[k].end();++it1){
    
38.           printf("cc[%d]=%d\n", *it1, k+1);
    
39.         }
    
40.      }
    
41.      if(nlist[k].size()==0)break;
    
42.     }
    
43.     return 0;
    
44. }
    

复制代码

mathe

我做了另外一种试验，我们可以查看有多少整数可以表示为最多两个平方数和一个幂的和（这个幂也可以是平方数).稍微修改上面就可以算出4000000以内只有下面数不满足条件（其中要求平方数和幂都不包含1）
1
2
3
5
6
7
10
11
14
15
19
23
30
39
46
51
55
71
87
103
111
119
135
151
167
335
559
783
895
951
1231
1391
1455
1551
1559
1607
1679
1775
1903
1991
2015
2127
2135
3023
3719
5340
5655
7503
7951
9519
16391
25887
26375
65311
190807
如果上面结果成立，那么对于给定整数N来说，就可以有比较方便的方法了
i) 如果在上面列表里面，利用预先分解的四个数的方法表达或者输出不能表达
ii)计算出所有不超过N的幂（sqrt(N)的复杂度），
iii)对于上面每个幂m,判断N-m是否也在上面列表中，如果是找到一个解，总时间复杂度sqrt(N)*log(N)
iv）对于上面所有每个幂m，判断 N-m是否两个平方数之和，这个可以通过判断N-m是否只有2和4k+1形式的素因子，如果找到一个结果，那么就可以得出分解为最多3个数的表达方案总复杂度O(N/log(N)) (可事先找出所有不超过sqrt(N)的素数)
但是如果计算大量数据的分解方案，还是没有找出比前面更加有效的方法

mathe

上面算法改进一下，对于充分大的N，可以将时间复杂度按概率控制在时间复杂度$O(sqrt(N)*log(N))$，只是算法会非常复杂。
i)先判断N是否幂或两个幂之和（这部分时间复杂度$O(sqrt(N)*log(N))$),如果是就结束并输出结果
ii)判断N是否可以是三个平方数之和，如果是，利用链接中方法构造对应幺模矩阵，并且将其对角化然后得出三平方和结果,结束
iii)对于所有充分接近N的立方数m使得N-m比较小（大概为$O(N^(2/3)log(N))$)
   判断N-m是否两个平方数之和 复杂度$O(N^(1/3)log^2(N))$
按概率，这部分需要判断$O(sqrt(log(N)))$次会成功。而对于较大的N,这样的数有$O(N^(1/3))$个，必然足够。
计算总复杂度为$O(sqrt(N)log(N))$