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

mathe

对于2n-1位或2n位A和B, 我们可以将它们前n位分别记为a,b;而它们颠倒数的前n位分别记为c,d, 要求(\(a\le c, b\le d, a\le b\))
于是对于奇数位情况，要求a,c的末尾相同；b,d的末尾相同，但是对于偶数位没有这个额外要求。另外a,b,c,d都是首位不为0（尾位可以是0）的n位数。
假设a,b,c,d的颠倒数分别位a',b',c',d'(可以首位为0）
于是我们要求
\(a'c'\equiv b'd'\pmod {10^n}\)
\(ac\lt (b+1)(d+1), bd\lt (a+1)(c+1)\).
我们可以先遍历所有满足条件的n位数，应该有数万种
然后可以从这数万种开始（完全可以多线程并行处理），对每组符合条件的情况的(a,b,c,d)
各自再添加1位产生n+1位的候选解并且检查它们是否符合n+1位的情况。
对于每个符合候选情况的候选解，末尾相同的数可以用来查看是否可以凑出符合条件的2n-1位情况解；而每个都可以查看是否是符合条件的2n位情况解。而得到的乘积结果是4n-3到4n位。

mathe

写了个程序，搜索乘积16位以内，只输出三组以上重复的结果

1. 1024553546227008:12157248~23196144:12157248~21275184
   
2. 1024553546227008:12157248~23196144:12157248~25239504
   
3. 1024553546227008:12157248~23196144:21275184~23196144
   
4. 1024553546227008:12157248~23196144:21275184~25239504
   
5. 1024553546227008:12157248~23196144:23196144~25239504
   
6. 1026761738613156:27327573~27573273:15615756~15756156
   
7. 1026761738613156:27327573~27573273:15615756~27327573
   
8. 1026761738613156:27327573~27573273:15615756~27573273
   
9. 1026761738613156:27327573~27573273:15756156~27327573
   
10. 1026761738613156:27327573~27573273:15756156~27573273
    
11. 1033559135533008:24124824~24481224:12242448~21424284
    
12. 1033559135533008:24124824~24481224:12242448~24124824
    
13. 1033559135533008:24124824~24481224:12242448~24481224
    
14. 1033559135533008:24124824~24481224:21424284~24124824
    
15. 1033559135533008:24124824~24481224:21424284~24481224
    
16. 10358850853008:2416824~2449224:1226448~2146284
    
17. 10358850853008:2416824~2449224:1226448~2416824
    
18. 10358850853008:2416824~2449224:1226448~2449224
    
19. 10358850853008:2416824~2449224:2146284~2416824
    
20. 10358850853008:2416824~2449224:2146284~2449224
    
21. 1038778073198208:21468384~25468704:12267648~21468384
    
22. 1038778073198208:21468384~25468704:12267648~25468704
    
23. 10394766926208:2148384~2548704:1227648~2148384
    
24. 10394766926208:2148384~2548704:1227648~2548704
    
25. 1042418529479808:12344448~22361664:12344448~23656044
    
26. 1042418529479808:12344448~22361664:12344448~24325824
    
27. 1042418529479808:12344448~22361664:22361664~23656044
    
28. 1042418529479808:12344448~22361664:22361664~24325824
    
29. 1042418529479808:12344448~22361664:23656044~24325824
    
30. 104645899008:123648~232944:123648~216384
    
31. 104645899008:123648~232944:123648~256704
    
32. 104645899008:123648~232944:216384~232944
    
33. 104645899008:123648~232944:216384~256704
    
34. 104645899008:123648~232944:232944~256704
    
35. 1053160943607808:23442944~23846144:12443648~23442944
    
36. 1053160943607808:23442944~23846144:12443648~23846144
    
37. 1062768961050048:25129224~26318304:23075064~25129224
    
38. 1062768961050048:25129224~26318304:23075064~26318304
    
39. 10781522545248:1336608~2339064:1336608~2633904
    
40. 10781522545248:1336608~2339064:2339064~2633904
    
41. 10789383647848:1220488~2210884:1220488~2694004
    
42. 10789383647848:1220488~2210884:2210884~2694004
    
43. 1083163569127848:13464408~22536084:13464408~24390444
    
44. 1083163569127848:13464408~22536084:13464408~26532804
    
45. 1083163569127848:13464408~22536084:22536084~24390444
    
46. 1083163569127848:13464408~22536084:22536084~26532804
    
47. 1083163569127848:13464408~22536084:24390444~26532804
    
48. 1086086201396248:12224888~22218884:12224888~26984204
    
49. 1086086201396248:12224888~22218884:22218884~26984204
    
50. 1095191446714848:23391864~23759064:13576608~23391864
    
51. 1095191446714848:23391864~23759064:13576608~23759064
    
52. 1095191446714848:23391864~23759064:13576608~26753904
    
53. 1095191446714848:23391864~23759064:23391864~26753904
    
54. 1095191446714848:23391864~23759064:23759064~26753904
    
55. 1103644900971648:23948064~25780824:13684608~23948064
    
56. 1103644900971648:23948064~25780824:13684608~25780824
    
57. 1115545658508288:23165184~25129344:13237248~23165184
    
58. 1115545658508288:23165184~25129344:13237248~25129344
    
59. 1115892288:13248~23184:13248~27504
    
60. 1115892288:13248~23184:23184~27504
    
61. 11202338786688:1323648~2316384:1323648~2763504
    
62. 11202338786688:1323648~2316384:2316384~2763504
    
63. 1121491586991888:13344048~23352084:13344048~24371064
    
64. 1121491586991888:13344048~23352084:23352084~24371064
    
65. 11230389209088:2333184~2511744:1333248~2333184
    
66. 11230389209088:2333184~2511744:1333248~2511744
    
67. 1134871023647088:13442448~23524284:13442448~24350664
    
68. 1134871023647088:13442448~23524284:13442448~26631624
    
69. 1134871023647088:13442448~23524284:23524284~24350664
    
70. 1134871023647088:13442448~23524284:23524284~26631624
    
71. 1134871023647088:13442448~23524284:24350664~26631624
    
72. 1137462800807088:13466448~23566284:13466448~24493464
    
73. 1137462800807088:13466448~23566284:13466448~26536824
    
74. 1137462800807088:13466448~23566284:23566284~24493464
    
75. 1137462800807088:13466448~23566284:23566284~26536824
    
76. 1137462800807088:13466448~23566284:24493464~26536824
    
77. 1147980114425088:25552944~25671744:13563648~23736384
    
78. 1147980114425088:25552944~25671744:13563648~25552944
    
79. 1147980114425088:25552944~25671744:13563648~25671744
    
80. 1147980114425088:25552944~25671744:23736384~25552944
    
81. 1147980114425088:25552944~25671744:23736384~25671744
    
82. 1166152618830528:24132384~25105464:24132384~27613224
    
83. 1166152618830528:24132384~25105464:25105464~27613224
    
84. 1178897181251328:25595064~26319744:13356288~25595064
    
85. 1178897181251328:25595064~26319744:13356288~26319744
    
86. 119391618528:134688~243984:134688~279624
    
87. 119391618528:134688~243984:243984~279624
    
88. 1201562515299328:24553984~25975264:13554688~24553984
    
89. 1201562515299328:24553984~25975264:13554688~25975264
    
90. 1214048648530368:14413248~25223184:14413248~27504144
    
91. 1214048648530368:14413248~25223184:25223184~27504144
    
92. 1221624174048768:14427648~25248384:14427648~27648144
    
93. 1221624174048768:14427648~25248384:25248384~27648144
    
94. 12241494111168:1453248~2543184:1453248~2750544
    
95. 12241494111168:1453248~2543184:2543184~2750544
    
96. 1224976765441968:25494084~28707624:14568048~25494084
    
97. 1224976765441968:25494084~28707624:14568048~28707624
    
98. 1226819950671168:14557248~25475184:14557248~27518544
    
99. 1226819950671168:14557248~25475184:25475184~27518544
    
100. 12427516378368:1467648~2568384:1467648~2764944
     
101. 12427516378368:1467648~2568384:2568384~2764944
     
102. 1244465038752768:25550784~25853184:14773248~25550784
     
103. 1244465038752768:25550784~25853184:14773248~25853184
     
104. 1244465038752768:25550784~25853184:14773248~27831744
     
105. 1244465038752768:25550784~25853184:25550784~27831744
     
106. 1244465038752768:25550784~25853184:25853184~27831744
     
107. 1248528019979968:26781664~27852844:14784448~26781664
     
108. 1248528019979968:26781664~27852844:14784448~27852844
     
109. 1269373829296608:26339184~27539064:15736608~26339184
     
110. 1269373829296608:26339184~27539064:15736608~27539064
     
111. 12812870423808:2630784~2783064:1452288~2630784
     
112. 12812870423808:2630784~2783064:1452288~2783064
     
113. 1289775414590208:26438784~27876264:14546688~26438784
     
114. 1289775414590208:26438784~27876264:14546688~27876264
     
115. 1292707500916608:26760384~27603864:14652288~26760384
     
116. 1292707500916608:26760384~27603864:14652288~27603864
     
117. 1296134716540608:26796384~27639864:26796384~28947744
     
118. 1296134716540608:26796384~27639864:27639864~28947744
     
119. 1309742715179808:26763984~27963864:14774688~26763984
     
120. 1309742715179808:26763984~27963864:14774688~27963864
     
121. 1330735585995648:27516384~27635184:15723648~27516384
     
122. 1330735585995648:27516384~27635184:15723648~27635184
     
123. 1335411836394048:27505584~27743184:15853248~27505584
     
124. 1335411836394048:27505584~27743184:15853248~27743184
     
125. 1340188899115248:15866448~27766284:15866448~28837464
     
126. 1340188899115248:15866448~27766284:27766284~28837464
     
127. 1343622465416448:27649584~27768384:15867648~27649584
     
128. 1343622465416448:27649584~27768384:15867648~27768384
     
129. 13461527878848:2751984~2795184:1597248~2751984
     
130. 13461527878848:2751984~2795184:1597248~2795184
     
131. 1348247277574848:27519984~27995184:15997248~27519984
     
132. 1348247277574848:27519984~27995184:15997248~27995184
     
133. 1412230497885792:21338166~23237706:21338166~33549024
     
134. 1412230497885792:21338166~23237706:23237706~33549024
     
135. 1416082902970392:23552106~30511464:21413166~23552106
     
136. 1416082902970392:23552106~30511464:21413166~30511464
     
137. 1462434833657448:29429694~29694294:16816968~16968168
     
138. 1462434833657448:29429694~29694294:16816968~29429694
     
139. 1462434833657448:29429694~29694294:16816968~29694294
     
140. 1462434833657448:29429694~29694294:16968168~29429694
     
141. 1462434833657448:29429694~29694294:16968168~29694294
     
142. 1475888438567452:22314166~24543106:22314166~36512404
     
143. 1475888438567452:22314166~24543106:24543106~36512404
     
144. 1521342697841892:22332186~34570044:22332186~31430484
     
145. 1521342697841892:22332186~34570044:31430484~34570044
     
146. 1564048900490832:25478316~35078544:23185476~25478316
     
147. 1564048900490832:25478316~35078544:23185476~35078544
     
148. 1564048900490832:25478316~35078544:23185476~38547504
     
149. 1564048900490832:25478316~35078544:25478316~38547504
     
150. 1564048900490832:25478316~35078544:35078544~38547504
     
151. 1599870193348752:25752126~37721424:23413386~25752126
     
152. 1599870193348752:25752126~37721424:23413386~37721424
     
153. 1632273493463872:25861136~33502784:23512496~25861136
     
154. 1632273493463872:25861136~33502784:23512496~33502784
     
155. 1701426323612232:26798436~36279864:24386796~26798436
     
156. 1701426323612232:26798436~36279864:24386796~36279864
     
157. 1701426323612232:26798436~36279864:24386796~39867624
     
158. 1701426323612232:26798436~36279864:26798436~39867624
     
159. 1701426323612232:26798436~36279864:36279864~39867624
     
160. 1749116423979792:27744036~39624144:25224396~27744036
     
161. 1749116423979792:27744036~39624144:25224396~36025584
     
162. 1749116423979792:27744036~39624144:25224396~39624144
     
163. 1749116423979792:27744036~39624144:27744036~36025584
     
164. 1749116423979792:27744036~39624144:36025584~39624144
     
165. 1829563724425752:26305596~39743064:26305596~28933236
     
166. 1829563724425752:26305596~39743064:28933236~39743064
     
167. 1835678214590976:21728448~40934844:21728448~22756608
     
168. 1835678214590976:21728448~40934844:21728448~42817824
     
169. 1835678214590976:21728448~40934844:22756608~40934844
     
170. 1835678214590976:21728448~40934844:22756608~42817824
     
171. 1835678214590976:21728448~40934844:40934844~42817824
     
172. 1875177765804672:27627876~27876276:27627876~38438784
     
173. 1875177765804672:27627876~27876276:27627876~38784384
     
174. 1875177765804672:27627876~27876276:27876276~38438784
     
175. 1875177765804672:27627876~27876276:27876276~38784384
     
176. 1875177765804672:27627876~27876276:38438784~38784384
     
177. 1878343575655456:21228488~40085864:21228488~22128848
     
178. 1878343575655456:21228488~40085864:22128848~40085864
     
179. 19574767691136:2328048~2438208:2328048~4074084
     
180. 19574767691136:2328048~2438208:2438208~4074084
     
181. 1974271018661136:22424088~24664008:22424088~40620684
     
182. 1974271018661136:22424088~24664008:24664008~40620684
     
183. 1982890719625536:23380848~24592608:23380848~40916484
     
184. 1982890719625536:23380848~24592608:24592608~40916484
     
185. 2094344787652416:23668488~24788448:23668488~42874884
     
186. 2094344787652416:23668488~24788448:24788448~42874884
     
187. 2141391973504588:23783009~30810596:21623099~23783009
     
188. 2141391973504588:23783009~30810596:21623099~30810596
     
189. 2150302188698496:25584048~44772084:24372288~25584048
     
190. 2150302188698496:25584048~44772084:24372288~44772084
     
191. 22563208958976:2556288~4685184:2556288~2677248
     
192. 22563208958976:2556288~4685184:2677248~4685184
     
193. 2409800338663858:26756009~39804506:24326099~26756009
     
194. 2409800338663858:26756009~39804506:24326099~39804506
     
195. 278793178274772:11052252~13236012:11052252~12036132
     
196. 278793178274772:11052252~13236012:12036132~13236012
     
197. 2789695766966544:31614288~34772208:31614288~40712586
     
198. 2789695766966544:31614288~34772208:34772208~40712586
     
199. 2949369464420704:33416288~36754208:33416288~48723506
     
200. 2949369464420704:33416288~36754208:36754208~48723506
     
201. 307687892430492:12168252~14449212:11173572~12168252
     
202. 307687892430492:12168252~14449212:11173572~14449212
     
203. 312232056776892:12265452~14546412:12265452~13357332
     
204. 312232056776892:12265452~14546412:13357332~14546412
     
205. 340011357444612:13238652~14676132:12254772~13238652
     
206. 340011357444612:13238652~14676132:12254772~14676132
     
207. 340011357444612:13238652~14676132:12254772~15854412
     
208. 340011357444612:13238652~14676132:13238652~15854412
     
209. 340011357444612:13238652~14676132:14676132~15854412
     
210. 343959861049812:13489452~15867612:12386772~13489452
     
211. 343959861049812:13489452~15867612:12386772~15867612
     
212. 4234434613671976:42616399~60723796:42616399~46873309
     
213. 4234434613671976:42616399~60723796:46873309~60723796
     
214. 462232147978944:10417344~21372612:10417344~11344704
     
215. 462232147978944:10417344~21372612:11344704~21372612
     
216. 467876177304444:10518444~20727522:10518444~11454804
     
217. 467876177304444:10518444~20727522:11454804~20727522
     
218. 489065671075464:10519464~20729532:10519464~21839322
     
219. 489065671075464:10519464~20729532:20729532~21839322
     
220. 4929015795984:1116144~1215504:1116144~2127132
     
221. 4929015795984:1116144~1215504:1215504~2127132
     
222. 493567754665284:11212044~12332004:11212044~20310342
     
223. 493567754665284:11212044~12332004:12332004~20310342
     
224. 497024673186384:11162544~12255504:11162544~21447132
     
225. 497024673186384:11162544~12255504:12255504~21447132
     
226. 512478631552104:11041464~12015624:11041464~21027342
     
227. 512478631552104:11041464~12015624:12015624~21027342
     
228. 527365570997304:11347464~12357624:11347464~20555652
     
229. 527365570997304:11347464~12357624:11347464~22385532
     
230. 527365570997304:11347464~12357624:12357624~20555652
     
231. 527365570997304:11347464~12357624:12357624~22385532
     
232. 527365570997304:11347464~12357624:20555652~22385532
     
233. 534918830572224:11064384~12049344:11064384~21086352
     
234. 534918830572224:11064384~12049344:12049344~21086352
     
235. 539305912694304:11549664~12577824:11549664~21758742
     
236. 539305912694304:11549664~12577824:11549664~22759632
     
237. 539305912694304:11549664~12577824:12577824~21758742
     
238. 539305912694304:11549664~12577824:12577824~22759632
     
239. 539305912694304:11549664~12577824:21758742~22759632
     
240. 542333486875824:13359504~23197332:11173584~13359504
     
241. 542333486875824:13359504~23197332:11173584~23197332
     
242. 543243185700124:11214484~12114844:11214484~20314762
     
243. 543243185700124:11214484~12114844:12114844~20314762
     
244. 546920672687424:12231744~23043732:12231744~13562304
     
245. 546920672687424:12231744~23043732:12231744~21405552
     
246. 546920672687424:12231744~23043732:13562304~21405552
     
247. 546920672687424:12231744~23043732:13562304~23043732
     
248. 546920672687424:12231744~23043732:21405552~23043732
     
249. 549403549738524:11336484~22339542:11336484~13576404
     
250. 549403549738524:11336484~22339542:11336484~20535762
     
251. 549403549738524:11336484~22339542:13576404~20535762
     
252. 549403549738524:11336484~22339542:13576404~22339542
     
253. 549403549738524:11336484~22339542:20535762~22339542
     
254. 555065306785024:11427584~13685504:11427584~21528752
     
255. 555065306785024:11427584~13685504:13685504~21528752
     
256. 562411024867944:12156264~13238424:12156264~21273462
     
257. 562411024867944:12156264~13238424:12156264~23167242
     
258. 562411024867944:12156264~13238424:13238424~21273462
     
259. 562411024867944:12156264~13238424:13238424~23167242
     
260. 562411024867944:12156264~13238424:21273462~23167242
     
261. 568919772619744:12311264~13541024:12311264~22301552
     
262. 568919772619744:12311264~13541024:13541024~22301552
     
263. 568992308855544:12253464~13465224:12253464~21443562
     
264. 568992308855544:12253464~13465224:12253464~23564142
     
265. 568992308855544:12253464~13465224:13465224~21443562
     
266. 568992308855544:12253464~13465224:13465224~23564142
     
267. 568992308855544:12253464~13465224:21443562~23564142
     
268. 5750892433944:1237464~1347624:1237464~2165562
     
269. 5750892433944:1237464~1347624:1237464~2358342
     
270. 5750892433944:1237464~1347624:1347624~2165562
     
271. 5750892433944:1237464~1347624:1347624~2358342
     
272. 5750892433944:1237464~1347624:2165562~2358342
     
273. 579899832100344:12375864~13587624:12375864~21657762
     
274. 579899832100344:12375864~13587624:12375864~23778342
     
275. 579899832100344:12375864~13587624:13587624~21657762
     
276. 579899832100344:12375864~13587624:13587624~23778342
     
277. 579899832100344:12375864~13587624:21657762~23778342
     
278. 585359054817264:14427504~23184252:13248144~14427504
     
279. 585359054817264:14427504~23184252:13248144~23184252
     
280. 587944983082464:14558304~21273672:12156384~14558304
     
281. 587944983082464:14558304~21273672:12156384~21273672
     
282. 587944983082464:14558304~21273672:12156384~23077452
     
283. 587944983082464:14558304~21273672:14558304~23077452
     
284. 587944983082464:14558304~21273672:21273672~23077452
     
285. 5918942844864:1466304~2142672:1224384~1466304
     
286. 5918942844864:1466304~2142672:1224384~2142672
     
287. 5918942844864:1466304~2142672:1224384~2306652
     
288. 5918942844864:1466304~2142672:1466304~2306652
     
289. 5918942844864:1466304~2142672:2142672~2306652
     
290. 5954604398064:1467504~2318652:1324944~1467504
     
291. 5954604398064:1467504~2318652:1324944~2318652
     
292. 596410911314064:12277584~23398452:12277584~21485772
     
293. 596410911314064:12277584~23398452:21485772~23398452
     
294. 6011342752464:1237584~1336944:1237584~2165772
     
295. 6011342752464:1237584~1336944:1237584~2339652
     
296. 6011342752464:1237584~1336944:1336944~2165772
     
297. 6011342752464:1237584~1336944:1336944~2339652
     
298. 6011342752464:1237584~1336944:2165772~2339652
     
299. 610687106376984:14532024~23121462:13212264~14532024
     
300. 610687106376984:14532024~23121462:13212264~23121462
     
301. 610687106376984:14532024~23121462:13212264~24013452
     
302. 610687106376984:14532024~23121462:14532024~24013452
     
303. 610687106376984:14532024~23121462:23121462~24013452
     
304. 621631023436584:14559624~23396562:13369464~14559624
     
305. 621631023436584:14559624~23396562:13369464~23396562
     
306. 621631023436584:14559624~23396562:13369464~24397452
     
307. 621631023436584:14559624~23396562:14559624~24397452
     
308. 621631023436584:14559624~23396562:23396562~24397452
     
309. 623987609046984:14773224~23316762:13323864~14773224
     
310. 623987609046984:14773224~23316762:13323864~23316762
     
311. 623987609046984:14773224~23316762:13323864~24135852
     
312. 623987609046984:14773224~23316762:14773224~24135852
     
313. 623987609046984:14773224~23316762:23316762~24135852
     
314. 637316872479504:15723504~23161572:13235184~15723504
     
315. 637316872479504:15723504~23161572:13235184~23161572
     
316. 642044561117904:14414544~14544144:14414544~25225452
     
317. 642044561117904:14414544~14544144:14544144~25225452
     
318. 643853345549904:15867504~23186772:13249584~15867504
     
319. 643853345549904:15867504~23186772:13249584~23186772
     
320. 645125317087104:23352672~25227552:13344384~14415744
     
321. 645125317087104:23352672~25227552:13344384~23352672
     
322. 645125317087104:23352672~25227552:13344384~25227552
     
323. 645125317087104:23352672~25227552:14415744~23352672
     
324. 645125317087104:23352672~25227552:14415744~25227552
     
325. 655859245091904:23545872~25347852:13454784~14785344
     
326. 655859245091904:23545872~25347852:13454784~23545872
     
327. 655859245091904:23545872~25347852:13454784~25347852
     
328. 655859245091904:23545872~25347852:14785344~23545872
     
329. 655859245091904:23545872~25347852:14785344~25347852
     
330. 6628869866304:2377872~2559852:1358784~1479744
     
331. 6628869866304:2377872~2559852:1358784~2377872
     
332. 6628869866304:2377872~2559852:1358784~2559852
     
333. 6628869866304:2377872~2559852:1479744~2377872
     
334. 6628869866304:2377872~2559852:1479744~2559852
     
335. 663636114127224:24121572~25013562:15721224~24121572
     
336. 663636114127224:24121572~25013562:15721224~25013562
     
337. 670341346809624:24361572~25471362:14555064~15723624
     
338. 670341346809624:24361572~25471362:14555064~24361572
     
339. 670341346809624:24361572~25471362:14555064~25471362
     
340. 670341346809624:24361572~25471362:15723624~24361572
     
341. 670341346809624:24361572~25471362:15723624~25471362
     
342. 6752984808024:1597224~2333982:1597224~2415972
     
343. 6752984808024:1597224~2333982:2333982~2415972
     
344. 698627190938544:15840144~25202772:14401584~15840144
     
345. 698627190938544:15840144~25202772:14401584~25202772
     
346. 6993759722544:1584144~2522772:1441584~1584144
     
347. 6993759722544:1584144~2522772:1441584~2522772
     
348. 699962850692586:10237386~20195643:10237386~11148726
     
349. 699962850692586:10237386~20195643:11148726~20195643
     
350. 705683190232944:15984144~25227972:14415984~15984144
     
351. 705683190232944:15984144~25227972:14415984~25227972
     
352. 706254154696944:15854544~25454772:14545584~15854544
     
353. 706254154696944:15854544~25454772:14545584~25454772
     
354. 706722242680944:15724944~25681572:14675184~15724944
     
355. 706722242680944:15724944~25681572:14675184~25681572
     
356. 70687000944:158544~254772:145584~158544
     
357. 70687000944:158544~254772:145584~254772
     
358. 7127829367344:1598544~2547972:1455984~1598544
     
359. 7127829367344:1598544~2547972:1455984~2547972
     
360. 713374293031344:15998544~25479972:14559984~15998544
     
361. 713374293031344:15998544~25479972:14559984~25479972
     
362. 776243190162384:15855984~27747972:15855984~15985584
     
363. 776243190162384:15855984~27747972:15985584~27747972
     
364. 808045828612596:12047076~13119516:12047076~21082383
     
365. 808045828612596:12047076~13119516:13119516~21082383
     
366. 814253092104096:23069253~25369023:21183483~23069253
     
367. 814253092104096:23069253~25369023:21183483~25369023
     
368. 860426716976316:12373596~13597236:12373596~21653793
     
369. 860426716976316:12373596~13597236:12373596~23795163
     
370. 860426716976316:12373596~13597236:13597236~21653793
     
371. 860426716976316:12373596~13597236:13597236~23795163
     
372. 860426716976316:12373596~13597236:21653793~23795163
     
373. 909936112971366:13274586~14587326:13274586~26158743
     
374. 909936112971366:13274586~14587326:13274586~28745613
     
375. 909936112971366:13274586~14587326:14587326~26158743
     
376. 909936112971366:13274586~14587326:14587326~28745613
     
377. 909936112971366:13274586~14587326:26158743~28745613
     
378. 913672379225088:11332608~21717024:11332608~22331904
     
379. 913672379225088:11332608~21717024:21717024~22331904
     
380. 939371872829728:11124448~21118444:11124448~20151664
     
381. 939371872829728:11124448~21118444:20151664~21118444
     
382. 944847751292928:23176704~23295504:11163648~23176704
     
383. 944847751292928:23176704~23295504:11163648~23295504
     
384. 949922356872528:11246448~22459224:11246448~20372664
     
385. 949922356872528:11246448~22459224:11246448~23348604
     
386. 949922356872528:11246448~22459224:20372664~22459224
     
387. 949922356872528:11246448~22459224:20372664~23348604
     
388. 949922356872528:11246448~22459224:22459224~23348604
     
389. 961824395998116:15733116~25032483:14304276~15733116
     
390. 961824395998116:15733116~25032483:14304276~25032483
     
391. 9713360964528:1144848~2376804:1144848~2073864
     
392. 9713360964528:1144848~2376804:2073864~2376804
     
393. 976614697896526:15743026~26014573:14313286~15743026
     
394. 976614697896526:15743026~26014573:14313286~26014573
     
395. 976614697896526:15743026~26014573:14313286~28613143
     
396. 976614697896526:15743026~26014573:15743026~28613143
     
397. 976614697896526:15743026~26014573:26014573~28613143
     
398. 990603807526368:11174688~23199624:11174688~24399504
     
399. 990603807526368:11174688~23199624:23199624~24399504
     
400. 992718536062968:20332884~22118844:11224488~20332884
     
401. 992718536062968:20332884~22118844:11224488~22118844
     
402. 992718536062968:20332884~22118844:11224488~24776004
     
403. 992718536062968:20332884~22118844:20332884~24776004
     
404. 992718536062968:20332884~22118844:22118844~24776004
     
405. 995932985187168:21617064~24341904:12352608~21617064
     
406. 995932985187168:21617064~24341904:12352608~24341904
     
407. 999088058982636:15852036~25221693:14412396~15852036
     
408. 999088058982636:15852036~25221693:14412396~25221693
     
409. 999088058982636:15852036~25221693:14412396~27741063
     
410. 999088058982636:15852036~25221693:15852036~27741063
     
411. 999088058982636:15852036~25221693:25221693~27741063
     

复制代码

northwolves

我这里侥幸找了一个八组解的，用杜老师的方法似乎会漏掉：
{340006497569227044612, 8, {{12253574772, 27747535221}, {13237358652, 25685373231}, {13344397452, 25479344331}, {13477572252, 25227577431}, {14415758532, 23585751441}, {14559625332, 23352695541}, {14677356132, 23165377641}, {15855734412, 21443755851}}}

mathe

fr.tgz (113.35 KB, 下载次数: 3)

2025-3-2 18:00 上传

点击文件名下载附件

不超过10位的数相乘（乘积不超过20位）结果也出来了，在附件中，仅包含至少3组的。
wayne计算到多少位了？是否可以提交一个oeis序列，包含3组以上的，4组以上的。

mathe

这个代码MAXD定义为4的时候计算8位以内数字的乘法，5是10位以内，6是12位以内。
不过从4->5计算时间增长了100倍，感觉好像优势也不是特别大。这样一估算是不是比wayne的直接计算优势也不大？
感觉6花费时间会太长了，就不准备继续计算了

1. #include <stdio.h>
   
2. #include <vector>
   
3. #include <iostream>
   
4. #include <map>
   
5. 
   
6. #define MAXD 4
   
7. 
   
8. struct cand{
   
9.   int a,b,c,d;
   
10.   int ap,bp,cp,dp;
    
11. };
    
12. 
    
13. std::vector<cand> cands;
    
14. typedef __int128_t longint;
    
15. typedef std::map<longint, cand> CMAP;
    
16. CMAP valcand;
    
17. 
    
18. int revers2(int a)
    
19. {
    
20.   int u=a%10,v=a/10;
    
21.   return u*10+v;
    
22. }
    
23. 
    
24. void init2()
    
25. {
    
26.   int a,b,c,d;
    
27.   for(a=10;a<=99;a++){
    
28.     for(b=a;b<=99;b++){
    
29.       for(c=a;c<=99;c++){
    
30.         for(d=b;d<=99;d++){
    
31.           if(a*c>=(b+1)*(d+1)||b*d>=(a+1)*(c+1))continue;
    
32.           int aa,bb,cc,dd;
    
33.           aa=revers2(a),bb=revers2(b),cc=revers2(c),dd=revers2(d);
    
34.           if((aa*cc)%100==(bb*dd)%100){
    
35.             cand cd;
    
36.             cd.a=a,cd.b=b,cd.c=c,cd.d=d;
    
37.             cd.ap=aa,cd.bp=bb,cd.cp=cc,cd.dp=dd;
    
38.             cands.push_back(cd);
    
39.           }
    
40.         }
    
41.       }
    
42.     }
    
43.   }
    
44. }
    
45. 
    
46. void outlongint(longint x)
    
47. {
    
48.   long r=1000000000000000000L;
    
49.   printf("%ld%018ld",(long)(x/r),(long)(x%r));
    
50. }
    
51. long gtp[18];
    
52. void process(const cand& cd, int length)
    
53. {
    
54.   long tp=1,i;
    
55.   tp=gtp[length];
    
56.   if((cd.a!=cd.b||cd.c!=cd.d)&&(cd.a!=cd.d||cd.c!=cd.b)){
    
57.   if(cd.a%10==cd.c%10&&cd.b%10==cd.d%10){
    
58.     longint v=(cd.a/10)*tp+cd.cp;
    
59.     longint vr=(cd.c/10)*tp+cd.ap;
    
60.     longint w=(cd.b/10)*tp+cd.dp;
    
61.     longint wr=(cd.d/10)*tp+cd.bp;
    
62.     if(v*vr==w*wr){
    
63. #pragma omp critical
    
64.       {
    
65.         longint r=v*vr;
    
66.         CMAP::iterator cit = valcand.find(r);
    
67.         if(cit == valcand.end()){
    
68.           valcand[r]=cd;
    
69.         }else{
    
70.           long v1=(cit->second.a/10)*tp+(cit->second.cp);
    
71.           long w1=(cit->second.b/10)*tp+(cit->second.dp);
    
72.           outlongint(r);
    
73.           std::cout<<":"<<(long)v1<<"~"<<w1<<":"<<(long)v<<"~"<<(long)w<<std::endl;
    
74.         }
    
75.       }
    
76.     }
    
77.   }
    
78.   {
    
79.     longint v=cd.a*tp+cd.cp;
    
80.     longint vr=cd.c*tp+cd.ap;
    
81.     longint w=cd.b*tp+cd.dp;
    
82.     longint wr=cd.d*tp+cd.bp;
    
83.     if(v*vr==w*wr){
    
84. #pragma omp critical
    
85.       {
    
86.         longint r=v*vr;
    
87.         CMAP::iterator cit = valcand.find(r);
    
88.         if(cit==valcand.end()){
    
89.           valcand[r]=cd;
    
90.         }else{
    
91.           long v1=(cit->second.a)*tp+(cit->second.cp);
    
92.           long w1=(cit->second.b)*tp+(cit->second.dp);
    
93.           outlongint(r);
    
94.           std::cout<<":"<<(long)v1<<"~"<<w1<<":"<<(long)v<<"~"<<(long)w<<std::endl;
    
95.         }
    
96.       }
    
97.     }
    
98.   }
    
99.   }
    
100.   if(length>=MAXD)return;
     
101. 
     
102.   int j,m,n;
     
103.   int ntp = tp;
     
104.   for(i=0;i<10;i++)for(j=0;j<10;j++){
     
105.     int a=cd.a*10+i; int b=cd.b*10+j;
     
106.     if(a>b)continue;
     
107.     for(m=0;m<10;m++){
     
108.       int c=cd.c*10+m;
     
109.       if(a>c)continue;
     
110.       for(n=0;n<10;n++){
     
111.       int d=cd.d*10+n;
     
112.     if(b>d)continue;
     
113.     int ap=i*ntp+cd.ap, bp=j*ntp+cd.bp, cp=m*ntp+cd.cp, dp=n*ntp+cd.dp;
     
114.     if((((long)ap*cp)-(long)bp*dp)%ntp!=0)continue;
     
115.     long v1=a*c,v2=b*d;
     
116.     if(v1>=v2+b+d+1||v2>=v1+c+a+1)continue;
     
117.     cand nc;
     
118.     nc.a=a;nc.b=b;nc.c=c;nc.d=d;
     
119.     nc.ap=ap;nc.bp=bp;nc.cp=cp;nc.dp=dp;
     
120.     process(nc,length+1);
     
121.       }
     
122.   }
     
123.   }
     
124. 
     
125. }
     
126. 
     
127. int main()
     
128. {
     
129.   int i;
     
130.   gtp[0]=1;
     
131.   for(i=1;i<18;i++)gtp[i]=gtp[i-1]*10;
     
132.   init2();
     
133.   std::cout<<"Total "<<cands.size()<<" cands\n";
     
134. #pragma omp parallel for
     
135.   for(i=0;i<cands.size();i++){
     
136.     process(cands[i],2);
     
137.   }
     
138.   return 0;
     
139. }
     

复制代码

wayne

我是rust写的，且开了多线程并发，https://nestwhile.com/res/b117282/primes.rs
10位数的情况下还可以用u64类型。而且也很快全部算完。
但是11位数的时候，两个u64相乘就是22位数了，这个碰巧刚好超出了u64的最大表达，9,223,372,036,854,775,807 =19位数。
相乘是为了已知乘积，计算其他的所有可能组合，不过，幸好 rust自带了一个u128的类型，才得以继续沿用以前的代码而不需要换成高精度计算库。
与此同时，内存占用也飙升到了30GB， 普通的32GB内存电脑根本扛不住，还好，出于好奇，我又给电脑增加了48GB内存，加上原先的32GB，就是80GB内存。
只是，这个速度，有点慢，我是老老实实的一个for循环，跑完所有的11位数的整数因式分解,以及22位数的因子组合，静等结果了。

===================
经mathe提醒，10位数存在部分溢出现象，然后重新生成了一遍， 确实多出了很多二元组的解，已经在28#楼更新

l4m2

wayne 发表于 2025-3-2 20:43
我是rust写的，且开了多线程并发，https://nestwhile.com/res/b117282/primes.rs
10位数的情况下还可以用u6 ...

我在跑11位的，应该几个小时能完成

l4m2

把乘数11位及以内求出来了 https://github.com/837951602/ReversedMultiplyEqual 求比较

wayne

你这个输出很简洁,能减少文件大小. 只是三元组,四元组,五元组的情况,还需要单独统计.

l4m2

wayne 发表于 2025-3-3 15:08
你这个输出很简洁,能减少文件大小. 只是三元组,四元组,五元组的情况,还需要单独统计. ...

有没有人把N=12搞了？需要3TB硬盘，内存不用很多；或者分段处理
时间一天应该足够。可能有更多的优化