数学研发论坛

 找回密码
 欢迎注册
123
返回列表 发新帖
楼主: medie2005

[讨论] 自缚数

[复制链接]
 楼主| 发表于 2008-12-24 12:26:19 | 显示全部楼层
一些结果:
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-24 15:13:32 | 显示全部楼层
代码:
  1. #include   <cstdlib>
  2. #include   <iostream>
  3. #include   <cmath>
  4. #include   "gmp.h"

  5. using   namespace   std;

  6. const      int  L=40000;
  7. mpz_t      Hash[L][10];
  8. mpz_t      number[L];
  9. mpz_t      POW10[100];

  10. void     Init( ){
  11.         mpz_init_set_ui( Hash[0][0], 0 );
  12.     for( unsigned i=1; i<L; ++i ) mpz_init_set_ui( Hash[i][0], 1 );
  13.         for( i=0; i<L; ++i ){       
  14.                 mpz_init_set_ui( number[i], 0 );
  15.                 for( unsigned j=1; j<10; ++j ){
  16.                         mpz_init( Hash[i][j] );
  17.                         mpz_mul_ui( Hash[i][j], Hash[i][j-1], i );                       
  18.                 }
  19.         }
  20.         mpz_init_set_ui( POW10[0], 1 );
  21.         for( i=1; i<100; ++i ){
  22.                 mpz_init( POW10[i] );
  23.                 mpz_mul_ui( POW10[i], POW10[i-1], 10 );
  24.         }               
  25. }

  26. void  Set_num_0( unsigned n ){
  27.         for( int i=0; i<L; ++i )
  28.                 mpz_set_ui( number[i], n );               
  29. }

  30. void  Clean( ){
  31.         for( unsigned i=0; i<L; ++i ){       
  32.                 mpz_clear( number[i] );
  33.                 for( unsigned j=0; j<10; ++j )
  34.                         mpz_clear( Hash[i][j] );
  35.         }
  36.         for( i=0; i<100; ++i )
  37.                 mpz_clear( POW10[i] );
  38. }

  39. bool   check( mpz_t &n, int *list, int m ){
  40.         int c[10]={0}, d[10]={0};
  41.         for( int i=1; i<m+1; ++i ) c[list[i]]++;
  42.         char str[100];
  43.         mpz_get_str( str, 10, n );       
  44.         for( i=0; str[i]!='\0'; ++i )  d[str[i]-'0']++;
  45.         for( i=0; i<10; ++i ) if( c[i]!=d[i] ) return false;
  46.         return true;
  47. }

  48. void     combination(   unsigned   n,   unsigned   m   ){
  49.     int  *c=new int[m+2], j, *num=new int[m+2], g;
  50.     for( j=1; j<=m; ++j )  c[j]=j-1, num[j]=c[j]-j+1;
  51.     c[m+1]=n;
  52.         int start=int(pow(10, (m-1)/9.0)/pow(m,1/9.0)), t=start;       
  53. R2: //copy( num+1, num+m+1, ostream_iterator<int>(cout," ") ),cout<<endl;       
  54.         if( c[m-1]>m-1 ){
  55.                 if( mpz_cmp( number[2*t-1], POW10[m] )>0 ){
  56.                         for( start=t; start<2*t; ++start ){               
  57.                                 if( mpz_cmp( number[start], POW10[m] )>0 )  start=2*t+1;
  58.                                 else
  59.                                         if( check( number[start], num, m ) ){                               
  60.                                                 mpz_out_str( stdout, 10, number[start] );
  61.                                                 printf("  %d",start);
  62.                                                 if( mpz_probab_prime_p( number[start], 10 ) )
  63.                                                         printf("  prime!");
  64.                                                 printf("\n");                               
  65.                                         }                       
  66.                         }
  67.                 }
  68.         }          
  69.     if( m&1 )
  70.         if( c[1]+1<c[2] ){
  71.                         for( g=t; g<2*t; ++g ){
  72.                                 mpz_sub( number[g], number[g], Hash[g][num[1]] );
  73.                         }
  74.             ++c[1], ++num[1];
  75.                         for( g=t; g<2*t; ++g ){
  76.                                 mpz_add( number[g], number[g], Hash[g][num[1]] );
  77.                         }
  78.                         goto R2;
  79.         }
  80.         else{
  81.             j=2;  goto R4;
  82.         }
  83.                 else
  84.                         if( c[1]>0 ){
  85.                                 for( g=t; g<2*t; ++g ){
  86.                                         mpz_sub( number[g], number[g], Hash[g][num[1]] );
  87.                                 }
  88.                                 --c[1], --num[1];
  89.                                 for( g=t; g<2*t; ++g ){
  90.                                         mpz_add( number[g], number[g], Hash[g][num[1]] );
  91.                                 }
  92.                                 goto R2;
  93.                         }
  94.                         else{
  95.                                 j=2;  goto R5;
  96.                         };
  97. R4:    if( c[j]>=j ){
  98.                    for( g=t; g<2*t; ++g ){
  99.                            if( j<=m )
  100.                                    mpz_sub( number[g], number[g], Hash[g][num[j]] );
  101.                            if( j-1<=m )
  102.                                    mpz_sub( number[g], number[g], Hash[g][num[j-1]] );
  103.                    }                  
  104.                    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;                    
  105.                    for( g=t; g<2*t; ++g ){
  106.                            if( j<=m )
  107.                                    mpz_add( number[g], number[g], Hash[g][num[j]] );
  108.                            if( j-1<=m )
  109.                                    mpz_add( number[g], number[g], Hash[g][num[j-1]] );
  110.                    }
  111.                    goto R2;
  112.            }
  113.            else
  114.                    ++j;
  115. R5:    if( c[j]+1<c[j+1] ){                  
  116.                    for( g=t; g<2*t; ++g ){
  117.                            if( j<=m )
  118.                                    mpz_sub( number[g], number[g], Hash[g][num[j]] );
  119.                            if( j-1<=m )
  120.                                    mpz_sub( number[g], number[g], Hash[g][num[j-1]] );
  121.                    }
  122.                    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;
  123.                   
  124.                    for( g=t; g<2*t; ++g ){
  125.                            if( j<=m )
  126.                                    mpz_add( number[g], number[g], Hash[g][num[j]] );
  127.                            if( j-1<=m )
  128.                                    mpz_add( number[g], number[g], Hash[g][num[j-1]] );
  129.                    }
  130.                   
  131.                    goto R2;
  132.            }
  133.            else{
  134.                    ++j;
  135.                    if( j<=m )    goto R4;
  136.            }
  137.            delete []c;
  138.            delete []num;
  139. }

  140. int   main(int   argc,   char   *argv[])
  141. {
  142.         Init();
  143.     for( unsigned i=3; i<=18; ++i ){  
  144.                 Set_num_0( i );
  145.                 cout<<i<<" digits search start!\n";        
  146.                 combination( i+9, i );
  147.     }
  148.     Clean( );
  149.     cout<<"press any key to continue...\n";
  150.     cin.get();   
  151.     return EXIT_SUCCESS;
  152. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-24 19:45:06 | 显示全部楼层
如果考虑9..0的单调递减序列
也许能得到全部解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-12-24 20:33:09 | 显示全部楼层
那你做做看啊。
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-12-24 21:03:23 | 显示全部楼层
我前面不是求出所有的9位以下的来了么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-1-12 08:50:26 | 显示全部楼层
一个35位的结果:
30603954306110352540554064206779403  6285
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-26 00:36 , Processed in 0.045031 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表