正整数A×颠倒数(A)=正整数B×颠倒数(B)

wayne

11位数, 我16核全开,内存占用38GB(主要是素数表就占用30GB)跑了1.5天的时间,而l4m2同学大力出奇迹,单核几个小时也给出了完全相同的答案, 统计数据 更新在28楼. 更多的数据也已经上传,347MB.

而我就干了这么一件事情, 就是穷举,从10^10到10^11-1,对当前的这个11位整数以及他的逆序数进行整数分解.挑选出其他的也是两个11位数相乘的因子对.
这里面有很多可以优化的地方,但我懒,没做(我没想到会跑这么久,看来要提前预判),,比如 已知乘积,算出多组的时候,那么其他组对应的整数,应该做一个标记,表示已经计算过,下次就别再整数分解了.但是因为标记本身特别占内存,所以我就没这么优化.

l4m2

wayne 发表于 2025-3-3 22:32
11位数, 我16核全开,内存占用38GB(主要是素数表就占用30GB)跑了1.5天的时间,而l4m2同学大力出奇迹,单核几个 ...

按mathe的分类做法，三个小时多核求出12的。只要仍然是所有数字计算出来，现在已经是算力瓶颈了。不过三十个小时求出13的好像也能接受

l4m2

wayne 发表于 2025-3-2 10:20
11位数的出现了7个5组解,2个6组,1个7组的, 1个8组的, 先发出来,尝鲜.

12位的（按乘积顺序）

1. 103144274352 112326257232 113447254032 122325627312 123546416112
   
2. 104155385562 112517548542 113427378342 114559364142 122533947522 123756815322 124757527122 134773742502
   
3. 110522653452 120361465332 121344276132 121562652132 132146437212 132384253212 133465236012
   
4. 103054462672 111328237552 113348471152 122448705232 123416486032
   
5. 111518438652 120471747732 122657905332 123517488132 135855528012
   
6. 111615746652 121551866532 122437369332 122764933332 133336838412 133693562412 134667517212
   
7. 104164494672 113437298352 114569383152 124768438032 134767707312
   
8. 112353584562 122355387342 123576473142 133247558322 134577346122 146557525302
   
9. 110523842772 120275077452 121563960252 132289236132 144039637212 145583184012
   
10. 121335842772 131077346652 133334892252 133455960252 144039745332 158427733212
    
11. 122413347972 132241359852 133310678652 135877320252 144013587732 147973224132 159853322412
    
12. 102250763464 112262459224 112464491224 203360684332 203726660332 212281476322
    
13. 103043463264 113233557024 113336373024 203056236432 213323933322 213517631322
    
14. 103246296384 123668618304 211823957532 213937924332 214348289232
    
15. 111517368264 122656728024 212528278242 214649274042 220815757332
    
16. 110533584384 120373369344 132397346304 210653396352 212755681152 230653596132
    
17. 121216705344 133324922304 212129234352 214036471152 230416813332
    
18. 111626677584 122776956144 212736598452 214859673252 231746689332
    
19. 112243772484 123343696044 123455692044 135664376004 203326833762 221186257542 223636950342
    
20. 113145763584 124334886144 124447782144 136754575104 213158536752
    
21. 113240536884 123321296844 125695612044 136885132404 205132447962 223150469742 227694510342
    
22. 113364976884 124688892444 136897576404 205357867962 223395689742
    
23. 120244814664 132255950424 133324956024 210428425662 231447913242 233318673042
    
24. 131171054544 132481440144 144014427504 145453117104 231842520252
    
25. 131067518544 132351984144 144159723504 145572493104 231615972252
    
26. 122317583184 132137906544 214055770572 231508933452 235437590052
    
27. 122318664384 146643962304 214057662672 230439626652 235439671152
    
28. 121430546784 132240387744 146785214304 212503456872 230521478652 231420678552 235876240152
    
29. 132039625464 133226783064 145228933224 231069344562 233146870362
    
30. 133344049464 134676143064 145214439624 146665117224 233352086562 235683250362 243962521452
    
31. 132481585584 144275198544 145597248144 158558427504 231842774772 252481597452
    
32. 146520049464 159721215624 235450133982 243721215972 256410086562
    
33. 123364128848 124596524048 223471085864 256114658804 258673218404
    

复制代码

northwolves

使用因子5465466随机搜到了一个8组解13位的：
{8,2705213125552759376591862,{{1023173493462,2643943713201},{1105319447442,2447449135011},{1114257187242,2427817524111},{1125377283042,2403827735211},{1203715837422,2247385173021},{1215728715222,2225178275121},{1225559237022,2207329555221},{1323953823402,2043283593231}}}

wayne

l4m2 发表于 2025-3-4 06:02
12位的（按乘积顺序）

数据已经挺多的了，可以向OEIS提交好几个数列了。
1）比如分别是 n位数乘积的 2元组，3元 组，4元组,，5元组,，6元组,，7元组,，8元组的统计情况
2）至少二组的全部统计个数...
反正可以变着花样描述。

mathe

还有奇数非常稀少，可以统计一下奇数

l4m2

northwolves 发表于 2025-3-4 08:17
使用因子5465466随机搜到了一个8组解13位的：
{8,2705213125552759376591862,{{1023173493462,264394371320 ...

强制尾数为2，另找到一组1323603638532 1334306449332 1336826305332 1441431855612 1455831614412 2316306367431 2522505747321 2547705325221


补充内容 (2025-3-5 05:06):
尾数为4另外有两组

northwolves

14位8组解（103843854的倍数）找到2组：

{8,{{10213354572462,26427545331201},{11033338436442,24463483333011},{11122555276242,24267255522111},{11233556472042,24027465533211},{12015534736422,22463743551021},{12135447714222,22241774453121},{12233576336022,22063367533221},{13215754632402,20423645751231}},269913890947368513543986862},

{8,{{11143576885662,26658867534111},{12135586697442,24479668553121},{12245578795242,24259787554221},{12256697773242,24237779665221},{13335689667222,22276698653331},{13347798465222,22256489774331},{13468777565022,22056577786431},{14667778535202,20253587776641}},297075140051044458931816482}

l4m2

l4m2 发表于 2025-3-4 16:18
强制尾数为2，另找到一组1323603638532 1334306449332 1336826305332 1441431855612 1455831614412 23163 ...

尾数为4另外有两组
1344134656704 2306424375732 2352235649232 2532253683612 2557550642412 4036242657531 4431443946321 4475713624221
1122336816444 1132427656044 1234445932404 1245544736004 2051364852342 2211663726522 2231548616322 2454455803302
尾数为6的没找到

mathe

可以检验3是\(10^n\)的原根，也就是\(3^m \pmod {10^n}\)的周期达到模\(10^n\)的最大周期\(2^{n-2}5^{n-1}\)
而且3关于模\(10^n\)的数论倒数是\(u=\frac{2\times10^n+1}3\).
所以一种可行的方案对于乘积结果末n位为\(m 2^s\pmod {10^n}, 0\le s\lt n\)的情况，我们只需要穷举
\(3^x 2^a \pmod{10^n}, m\times u^x 2^{s-a} \pmod {10^n}\)，其中\(0\le a \le \frac s2 , 0\le x \le 2^{n-a-2}5^{n-1}\).
这可以通过一个二次循环来解决。这样可以节省内存，但是缺点是还需要求模\(10^n\)的运算，在计算上效率不太高.
而对于\(s=n\)的特殊情况，我们需要穷举\(3^x 2^a \pmod{10^n}, m\times u^x 2^b \pmod {10^n}\)，其中\( a+b\ge s , 0\le x \le 2^{n-\min\{a,b\}-2}5^{n-1}\).

如果为了计算完整，我们还需要考虑乘积结果末n位含因子5的情况，不过如果仅仅想找数目多的解，含因子5的情况就可以忽略了。
对于同时含因子2和5的，由于因子5和2必须分离到不同整数，穷举范围会小很多