x^2 + y^3 + z^5 =w^7,GCD(x,y,z)=1的高效算法

northwolves

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]

northwolves

供测试：

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)

mathe

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

mathe

这个题目里面\(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\)是否完全平方数

northwolves

A387127 已更新