x^2 + y^3 + z^5 =w^7,GCD(x,y,z)=1的高效算法
A387127 a(n) is the smallest integer w such that the Diophantine equation x^2 + y^3 + z^5 = w^7 where GCD(x,y,z)=1 has exactly n positive integer solutions.DATA
2, 21, 13, 41, 8, 73, 145, 113, 201, 393, 377
OFFSET
1,1
COMMENTS
a(12) > 1000, a(13) = 793.
我是先采用了9个幂进行初筛。效率一般
mod_bases = [ 81, 121,169,289, 343, 361, 512, 625, 729]
供测试：
w=113有8 组解：
(8859268,53921,2),(14955543,22632,20),(12269184,43921,70),(10325543,50480,98),(14489415,28548,290),(10889614,46613,434),(13366807,32440,468),(4384745,4056,736)
w=793有13 组解：
(6441306721,5379898,344),(13190361675,2852775,217),(2590399209,5748670,3486),(10382024943,4451026,4152),(7560163574,5171724,4437),(10304516015,4159986,7176),(5891612458,5101373,7846),(1704806884,5401353,8184),(11740904109,758120,8996),(10608526025,2381550,9342),(3640941879,4685006,9590),(5590859050,1793629,10988),(4319721892,1419180,11193) 1489 12
61817918600^2+23148209^3+4870^5=1489^7
62916280855^2+23062284^3+5070^5=1489^7
121908563916^2+11081313^3+5596^5=1489^7
66451403155^2+22770034^3+5780^5=1489^7
122083986058^2+10889877^3+7962^5=1489^7
126845042699^2+2263534^3+10484^5=1489^7
40021824704^2+24200254^3+13529^5=1489^7
68989139093^2+22188486^3+14034^5=1489^7
124498764781^2+1536789^3+14859^5=1489^7
35714772873^2+24068768^3+15878^5=1489^7
105925863269^2+4902382^3+21770^5=1489^7
31496204963^2+19342562^3+24022^5=1489^7
793 13
13190361675^2+2852775^3+217^5=793^7
6441306721^2+5379898^3+344^5=793^7
2590399209^2+5748670^3+3486^5=793^7
10382024943^2+4451026^3+4152^5=793^7
7560163574^2+5171724^3+4437^5=793^7
10304516015^2+4159986^3+7176^5=793^7
5891612458^2+5101373^3+7846^5=793^7
1704806884^2+5401353^3+8184^5=793^7
11740904109^2+758120^3+8996^5=793^7
10608526025^2+2381550^3+9342^5=793^7
3640941879^2+4685006^3+9590^5=793^7
5590859050^2+1793629^3+10988^5=793^7
4319721892^2+1419180^3+11193^5=793^7
1097 14
38198406622^2+7678384^3+645^5=1097^7
43535169171^2+2545891^3+1381^5=1097^7
25031955387^2+10868132^3+4326^5=1097^7
28493861769^2+9842162^3+10794^5=1097^7
34809881883^2+8134724^3+11010^5=1097^7
30909866125^2+8232367^3+13185^5=1097^7
5609289163^2+11342308^3+13332^5=1097^7
11644170699^2+11008089^3+13463^5=1097^7
24814745436^2+8826073^3+14350^5=1097^7
31569381051^2+4255317^3+15299^5=1097^7
9882408027^2+9890444^3+15330^5=1097^7
26583954601^2+4327642^3+16224^5=1097^7
3774656862^2+3458157^3+17936^5=1097^7
4329390648^2+3181344^3+17945^5=1097^7
1657 15
110493131588^2+28057865^3+874^5=1657^7
184075397967^2+7442234^3+4100^5=1657^7
179995828887^2+12357022^3+6516^5=1657^7
122215261649^2+26821898^3+9160^5=1657^7
137774749037^2+24616747^3+13181^5=1657^7
82965872499^2+29799748^3+15690^5=1657^7
92295729337^2+28991147^3+16981^5=1657^7
176053527763^2+9813260^3+18814^5=1657^7
107934759575^2+26228539^3+21509^5=1657^7
56299199709^2+29162908^3+22920^5=1657^7
62580873897^2+27970069^3+24315^5=1657^7
95633292841^2+25051046^3+24826^5=1657^7
146417245222^2+14049053^3+25162^5=1657^7
98467324287^2+488330^3+30074^5=1657^7
77354979681^2+9061385^3+30767^5=1657^7
这个题目里面\(w^7\)其实是不必要的，可以考虑计算每个整数表示为\(x^2+y^3+z^5\)的方案数目。
不过这个题目优化机会不多。
我们可以选定一个模M，比如120120，
可以事先计算关于模M所有平方剩余和三次剩余的集合，以及对于每个三次剩余，对应的三次立方根集合。
然后对于每个\(w^7-z^5\),先计算\((w^7-z^5)%M\), 并且对于M的每个平方剩余s, 判断\((w^7-z^5-s)%M\)是否是三次剩余，如果是我们选择对应的可用范围内所有三次立方根y,再判断\(w^7-z^5-y^3\)是否完全平方数 A387127 已更新:handshake
页:
[1]