自缚数

medie2005

一些结果： 3909511 5 13177388 7 77399307003 15 419370838921 18 prime! 985992657240 19 835713473952 21 833904227332 21 1788320037373 31 3606012949057 23 5398293152472 24 3216829919793 21 1262490630568 22 4119883235101 25 15554976231978 27 24006899084988 27 60383799081932 30 81201761476956 35 27348457391264 31 15577274860798 29 49224383542158 33 19705624111111 30 79012333267736 35 26440542914024 31 46416694154062 33 121435625299344 34 203200576992435 36 662953283249375 41 426272853204829 42 101642736591110 36 165339712406465 38 407374116975631 42 165797451775676 38 165222360955311 38 2818515880970594 48 5018878986609952 49 1382570662371937 48 4858092352072852 55 3427807121982740 53 4775908548352426 55 1954704075000056 50 54437493967260773 67 48256683467919762 66 36609478778945537 64 prime! 42075899760411857 65 17918292835887535 59 15239584186060982 58 10930785525494522 56 31519849146311673 63 27303134872679943 62 31515851595913461 63 95077997111329717 66 29966838595339424 58 19927799784239897 53 10086092019043889 53 35091971237636597 61 35091919717031657 61 46901696550069505 63 21030861665054609 65 13769573575520817 62 85791557474770217 76 21363985727087121 65 35474647514756029 69 66540910111554226 74 335264351957009505 82 339377855106948363 82 216496089534704228 78 474198383494687086 85 137588955438285298 74 380638049039506528 83 191587695760413570 77 270155913667084962 80 133980511129661621 74 404331695392268961 80 563127991896725130 83 179862850798580394 73 579221581630271463 94 526129850165466770 93 189274617554437126 83 260424784229276373 86 189220664467312220 83 139251164815885201 80 prime! 269331745886541488 86 191445501680480046 83 520472561120936234 93 257363033454391563 86 520413045054926166 93 1260501040364295269 95 7036025605643951593 115 1845490340136980003 99 8287635131760043919 117 2209243168178007319 101 6035143058499257267 113 5571359353914741184 112 8033208539405974995 108 4407336128691989819 101 7371504976296298569 107 1543999715496995214 86 5490083550189959519 101 1566831669012240599 93 6535976150169498007 109 3302927389750318219 101 prime! 7074429476239359302 110 1416597491570626293 92 4144420369160277807 117 5606262537638424619 121 5606262563361475819 121 4826006075592303123 119 1230472098338175128 102 6601884735572840219 123 2422648658387709402 110 2872784436887110369 112 7572181762697312875 125 9224502473054552067 128

medie2005

代码：

1. #include <cstdlib>
2. #include <iostream>
3. #include <cmath>
4. #include "gmp.h"
6. using namespace std;
8. const int L=40000;
9. mpz_t Hash[L][10];
10. mpz_t number[L];
11. mpz_t POW10[100];
13. void Init( ){
14. mpz_init_set_ui( Hash[0][0], 0 );
15. for( unsigned i=1; i<L; ++i ) mpz_init_set_ui( Hash[i][0], 1 );
16. for( i=0; i<L; ++i ){
17. mpz_init_set_ui( number[i], 0 );
18. for( unsigned j=1; j<10; ++j ){
19. mpz_init( Hash[i][j] );
20. mpz_mul_ui( Hash[i][j], Hash[i][j-1], i );
21. }
22. }
23. mpz_init_set_ui( POW10[0], 1 );
24. for( i=1; i<100; ++i ){
25. mpz_init( POW10[i] );
26. mpz_mul_ui( POW10[i], POW10[i-1], 10 );
27. }
28. }
30. void Set_num_0( unsigned n ){
31. for( int i=0; i<L; ++i )
32. mpz_set_ui( number[i], n );
33. }
35. void Clean( ){
36. for( unsigned i=0; i<L; ++i ){
37. mpz_clear( number[i] );
38. for( unsigned j=0; j<10; ++j )
39. mpz_clear( Hash[i][j] );
40. }
41. for( i=0; i<100; ++i )
42. mpz_clear( POW10[i] );
43. }
45. bool check( mpz_t &n, int *list, int m ){
46. int c[10]={0}, d[10]={0};
47. for( int i=1; i<m+1; ++i ) c[list[i]]++;
48. char str[100];
49. mpz_get_str( str, 10, n );
50. for( i=0; str[i]!='\0'; ++i ) d[str[i]-'0']++;
51. for( i=0; i<10; ++i ) if( c[i]!=d[i] ) return false;
52. return true;
53. }
55. void combination( unsigned n, unsigned m ){
56. int *c=new int[m+2], j, *num=new int[m+2], g;
57. for( j=1; j<=m; ++j ) c[j]=j-1, num[j]=c[j]-j+1;
58. c[m+1]=n;
59. int start=int(pow(10, (m-1)/9.0)/pow(m,1/9.0)), t=start;
60. R2: //copy( num+1, num+m+1, ostream_iterator<int>(cout," ") ),cout<<endl;
61. if( c[m-1]>m-1 ){
62. if( mpz_cmp( number[2*t-1], POW10[m] )>0 ){
63. for( start=t; start<2*t; ++start ){
64. if( mpz_cmp( number[start], POW10[m] )>0 ) start=2*t+1;
65. else
66. if( check( number[start], num, m ) ){
67. mpz_out_str( stdout, 10, number[start] );
68. printf(" %d",start);
69. if( mpz_probab_prime_p( number[start], 10 ) )
70. printf(" prime!");
71. printf("\n");
72. }
73. }
74. }
75. }
76. if( m&1 )
77. if( c[1]+1<c[2] ){
78. for( g=t; g<2*t; ++g ){
79. mpz_sub( number[g], number[g], Hash[g][num[1]] );
80. }
81. ++c[1], ++num[1];
82. for( g=t; g<2*t; ++g ){
83. mpz_add( number[g], number[g], Hash[g][num[1]] );
84. }
85. goto R2;
86. }
87. else{
88. j=2; goto R4;
89. }
90. else
91. if( c[1]>0 ){
92. for( g=t; g<2*t; ++g ){
93. mpz_sub( number[g], number[g], Hash[g][num[1]] );
94. }
95. --c[1], --num[1];
96. for( g=t; g<2*t; ++g ){
97. mpz_add( number[g], number[g], Hash[g][num[1]] );
98. }
99. goto R2;
100. }
101. else{
102. j=2; goto R5;
103. };
104. R4: if( c[j]>=j ){
105. for( g=t; g<2*t; ++g ){
106. if( j<=m )
107. mpz_sub( number[g], number[g], Hash[g][num[j]] );
108. if( j-1<=m )
109. mpz_sub( number[g], number[g], Hash[g][num[j-1]] );
110. }
111. c[j]=c[j-1], num[j]=c[j]-j+1; c[j-1]=j-2, num[j-1]=c[j-1]-(j-1)+1;
112. for( g=t; g<2*t; ++g ){
113. if( j<=m )
114. mpz_add( number[g], number[g], Hash[g][num[j]] );
115. if( j-1<=m )
116. mpz_add( number[g], number[g], Hash[g][num[j-1]] );
117. }
118. goto R2;
119. }
120. else
121. ++j;
122. R5: if( c[j]+1<c[j+1] ){
123. for( g=t; g<2*t; ++g ){
124. if( j<=m )
125. mpz_sub( number[g], number[g], Hash[g][num[j]] );
126. if( j-1<=m )
127. mpz_sub( number[g], number[g], Hash[g][num[j-1]] );
128. }
129. c[j-1]=c[j], num[j-1]=c[j-1]-(j-1)+1; c[j]=c[j]+1, num[j]=c[j]-j+1;
131. for( g=t; g<2*t; ++g ){
132. if( j<=m )
133. mpz_add( number[g], number[g], Hash[g][num[j]] );
134. if( j-1<=m )
135. mpz_add( number[g], number[g], Hash[g][num[j-1]] );
136. }
138. goto R2;
139. }
140. else{
141. ++j;
142. if( j<=m ) goto R4;
143. }
144. delete []c;
145. delete []num;
146. }
148. int main(int argc, char *argv[])
149. {
150. Init();
151. for( unsigned i=3; i<=18; ++i ){
152. Set_num_0( i );
153. cout<<i<<" digits search start!\n";
154. combination( i+9, i );
155. }
156. Clean( );
157. cout<<"press any key to continue...\n";
158. cin.get();
159. return EXIT_SUCCESS;
160. }

复制代码

无心人

如果考虑9..0的单调递减序列 也许能得到全部解

medie2005

那你做做看啊。 23 digits search start! 72374194476756069205463 321 prime! 26422727075326705619519 287 23369275182001540983167 283 15307891248046600369714 270 81156000928437353043779 325 88150077514629769451546 328 36083215428634110977759 297 prime! 24122609017228438923562 284 74658900958504521623135 322 41930548255879225151204 302 18120785812809735496103 275 66927307822924784608184 318 83684819395021675123823 326 14343996440308686746138 268 18088196614511100077279 275 95819846877371720464703 331 prime! 21270792708795826504283 280 14832743436587440945891 269 59630841033488437373952 314 19942323847352038835072 278 39562832189446281361201 300 39562832918446281360602 300 11305333082883943259543 261 66612933025012790825133 318 14778011952046745065439 269 72486576766263162199063 321 prime! 22597217327585752660759 282 prime! 22597217823373667296734 282 26468759137170309661725 287 81031149661447601291327 325 49621103054709073136959 285 21038524308930890572199 259 46697261888319509272709 283 24940929768415003677579 264 67737789499145056223291 295 29779858296577179839939 253 51289949659697722608041 279 31146577799502195931297 264 13219073586947696543725 254 31773554298759363406961 280 59246050891868100090607 300 18758609226422112396890 264 28976651734884860990843 277 33994888681644746414952 282 38497141929504440682503 286 19383469040737282336967 265 44994080613434557855793 291 15195003646025564342799 258 14673312466007735691799 257 34930339660070335619147 283 31735639651530947406962 280 25269054459617449066407 273 18595637250571325410214 298 27305844273903773420543 311 13257556274267026251839 287 22915753760002786215463 305 16467047928613571262541 294 49153322466355208662117 332 18720020685302595548726 298 19880487560462427270304 300 19880050160446200181207 300 14758304773867785198871 290 88536834649328820157363 354 88536834649360183744580 354 29202388044817616004815 313 18782211348680297544005 298 35404621236372898100163 320 67849604431150484346035 344 29863275425252576001768 314 10317338106477745928753 279 20416186535341030584923 301 24 digits search start! 354665532646065133929216 383 112124135925391604401320 337 437129646972257352317456 392 457614941054750379432060 394 153624554507256393112296 349 260625983192005163033814 370 869207861507614975320762 423 214096790127681751538226 362 481365058252096019045884 396 602418694082816615582049 406 373619668262400209873688 385 104074634608850692978080 334 189440085796550586624800 357 835875118623844438193904 421 853907714843460879808003 422 891001198761584541082827 424 125601692898807378284264 341 281391262593836556856884 373 686569533864055104764958 412 686569533828413462621097 412 189177722863461132693648 357 701715859696534378782704 413 987793576087832632011040 429 225284713459648685607129 364 198925685231354810406004 359 490563597202315131711768 397 273214976200075100892641 372 266676559020729517682164 371 273214973571355911836352 372 121613620033947657895422 340 170459239740545110164856 353 416509403411192994103344 361 171259769006513093829846 327 818465606798425929922808 389 484109499266774059048278 367 673077926439106993196394 364 299377962806202991779926 327 589574000759254953914529 366 929699742411420632623896 385 807999509087938024311156 379 214139475445969926198288 327 548385999937603819238150 363 295992663487794453856960 339 131955343102113915185529 328 312672096972930846551424 361 297425941174237756260598 359 197329230129436210502826 343 213415300822299791566344 346 155645946809864524680396 334 213827889675779026113129 346 243290721689808771936674 351 297976981853466442478164 359 100284905958118051935688 318 754898065391888177417927 398 807649291192283188846424 401 922344381918387870921216 407 243519789801901381758524 351 430269109280353116849750 374 719633244899261740204874 396 182509718964663492772161 340 255810773797545967582936 353 390589621617690427333812 370 400191853859024097755434 371 532001906706327956933372 383 439951424937660070453504 375 124762017212135136459299 326 924203678225011567566522 460 837645433609376463653402 455 214146750636487497611274 391 214148137075756507593474 391 205536325655808734937480 389 427462727286409805674866 422 661556409574358048281334 443 844985028324148811426146 455 878985830807357626347576 457 880875863245518508316976 457 562834694540208845445078 435 718858147491516762158014 447 967225587818513520207482 462 264768729088102400480406 400 537525851206744973400648 433 127524720914542447686856 369 454505698184624560143352 425 25 digits search start! 3025216251120602469400295 486 3906265672000000125750509 500 4426954045326617954277571 507 1314209631413466095537215 443 2814190134354195006286005 482 7316849305193311275583650 536 2117448637932319016845101 467 6282759081625457026336229 527 2762100801984442967241625 481 9227510487495164483356651 550 3575664876941654284577295 495 6176318761915529057285725 526 7954440288905470517110465 541 7954440288905470517402065 541 5866452931050248239675321 523 5106676592341262086028933 515 5877659134522951648864801 523 1402778368491403502886695 446 3151995316860483408471458 488 6408959745854602858648322 528 2083674691647868743819850 466 2332850714164805299661386 472 5293044387569112788460673 517 7961805448437229773176185 541 6846372801964862914427737 532 7323687410797225985156850 536 9235883825922671215514701 550 4765327260188591166849535 511 3266810694818614794172141 490 5575870286920338693434122 520 5013270646112938402004092 514 4353275191840931731733425 506 7947102357042166103849665 541 2657697566123323235189275 479 5375504891695201474725055 518 1163767927486677676616209 437 3637511924712914820341410 496 5210902707965600997557635 478 2907794705234332299051460 448 1850363349196017093792825 426 1496040389891087292583140 416 9521328973269586981684225 511 5028453892938441682976925 476 1931144935680979048228342 428 8405838430939254393635907 504 1098767943059501806557892 402 2011541998633439730526093 430 7404347169346108395192921 497 4921894643929380658591957 454 3939200103996394322311680 452 7997037699867041571593601 489 1826474602229179979234911 415 9598947267154104843261499 499 5454414169009546822055395 496 2182467796906349613102403 448 5356259201179166308179033 495 6187596352112953467354159 503 5259670321807937215559603 494 5969684437944314577310525 501 6195791806000314987803041 503 3237891133492583476242984 468 1479964127080277913484841 429 2614068904346069852287129 457 8810869493918143318746211 523 5377885985882495392884225 495 3178425468995208984341555 467 6089851294146058012468915 502 8207040798131666291927361 519 9744787529574271296140857 529 2413495872938562070790337 453 4544074697713811287469695 486 1170581208491910912501754 418 6073759375320471445370929 502

无心人

我前面不是求出所有的9位以下的来了么？

medie2005

一个35位的结果: 30603954306110352540554064206779403 6285