87624375 - 第2页 - 编程擂台 - 数学研发论坛

无心人 发表于 2008-11-27 15:31:30

求那个smith数字实在郁闷
换换手，做这个试试吧
呵呵

无心人 发表于 2008-11-27 16:38:52

import Array
import List
import Time

readInt :: IO Int
readInt = readLn

digitsCount n = map (\x -> x - 1) \$ map length \$ group \$ sort \$ (show n) ++ "1234567890"

media n = , let ns = n'^3, map (*3)(digitsCount n') == digitsCount ns]

main = do
      putStrLn "Input Max n:"
      n <- readInt
      let filename = "media" ++ show(n) ++ ".TXT"
      t1 <- getClockTime
      writeFile filename \$ show \$ media n
      t2 <- getClockTime
      appendFile filename "\n"
      appendFile filename \$ showt1
      appendFile filename "\n"
      appendFile filename \$ showt2
============================
估计运行10^8是700秒多点

medie2005 发表于 2008-11-27 22:56:44

说一下目前的思路.
1<=x<10^8,x的数字组成(前导0是允许的)为a,a,...,a.统计a,a,...,a中0,1,2,...,9出现的次数,填入数组b,b,...,b.
考虑x^3 mod 10^8,记录其结果中的8个数字(前导0是允许的)d,d,...,d.
统计d,d,...,d中0,1,2,...,9出现的次数,填入数组c,c,...,c.
int ds=0;
for( int i=0; i<10; ++i ){
   if( c>3*b ){
         说明x前面的数字组成还有c/3-b个i.
         ds+=/c/3\-b;(/c/3\表示c/3的上取整)
         if( ds>4 )超过12位,说明这个数不符合要求
}
}
这样,我们可以部分确定x的前部数字组成的形式以减少计算量.
另外,
若x是8位数,则10^24>x^3>=10^23=> x>46415888
若x是9位数,则10^27>x^3>=10^26=> x> 464158883
若x是10位数,则10^30>x^3>=10^29=> x> 4641588833
若x是11位数,则10^33>x^3>=10^32=> x> 46415888336
若x是12位数,则10^36>x^3>=10^35=> x> 464158883361
因此,我们可以确定x的第一位是5,6,7,8,9中的一个.

[ 本帖最后由 medie2005 于 2008-11-28 09:21 编辑 ]

mathe 发表于 2008-11-28 08:55:17

第一位还可以是4.
另外一个特点是x是3的倍数.
所以medie的方法对于某个x的末8尾,如果能够完全确定最高4位数的构成,那么马上可以检测x是否3的倍数(而不需要先排列前4位);而如果完全确定了3位,那么余下一位只有3种或4种可能了.

无心人 发表于 2008-11-28 11:50:45

继续优化
呵呵

KeyTo9_Fans 发表于 2010-3-5 22:28:38

http://www.research.att.com/~njas/sequences/index.html?q=87624375&language=english&go=Search

给出了$10^9$以内的解。

不知道这个数列是不是楼主建立的。

10^10以内的解为

000087624375: 000000000000672782675854638427734375
000088236519: 000000000000686981591125828823386359

000516473892: 000000000137766973511455269432948288
000569784132: 000000000184982673134619523527547968
000576283194: 000000000191384985523942177766265384
000623837409: 000000000242780746383933673463008929
000652319574: 000000000277575564351196433995651224
000726918453: 000000000384111297639829428356545677
000751396842: 000000000424236563727511983954179688
000865917402: 000000000649276079127044592151568808
000876243750: 000000000672782675854638427734375000
000882365190: 000000000686981591125828823386359000
000908714352: 000000000750381574940393412517982208
000984052317: 000000000952915880827425374740139013
000996302784: 000000000988949309679704837296226304

004680215379: 000000102517384602327906545167884939
004721985066: 000000105286776088241591696450267496
004752360918: 000000107331759078841289462659540632
004765380219: 000000108216298065465737327981043459
004780620591: 000000109257896057262144480609085071
004816217505: 000000111716745518470254580185062625
004823206911: 000000112203829460992186142184236031
004857619623: 000000114622667941862894389565357367
004902138867: 000000117803129848649828407728960363
004902857961: 000000117854979022907496608552994681
004915280637: 000000118753100269752896627409434853
004980521937: 000000123544828809194970771599203953
005063248197: 000000129803872805295961407646541373
005108514369: 000000133316485995850611518146505409
005140687236: 000000135851220783764366684174600256
005143226097: 000000136052601097242435292957214673
005162109375: 000000137556655012071132659912109375
005162968731: 000000137625365189376161768252961891
005164738920: 000000137766973511455269432948288000
005289479016: 000000147992155502299481690487876096
005382417906: 000000155930920888203446772967513416
005426370189: 000000159782147738463045208395061269
005429013678: 000000160015778029845493668293341752
005497686021: 000000166165094742590207468986587261
005628130974: 000000178275879003943616358291650424
005679321048: 000000183184725991700563446370862592
005697841320: 000000184982673134619523527547968000
005731250688: 000000188255735033011888558725660672
005762831940: 000000191384985523942177766265384000
005783610492: 000000193462640368077557991032215488
005786430129: 000000193745730180246815952247036689
005804321799: 000000195548481032073108299779245399
005903467821: 000000205741357445083299379160828661
005923803477: 000000207874839507947423537705892333
006016832742: 000000217823041047067666236312262488
006019285734: 000000218089561356773491420573826904
006021314589: 000000218310162906143554320158918469
006038190525: 000000220150885693095351686000953125
006053147982: 000000221790976927361545340843850168
006072798135: 000000223957976610970762887853110375
006095721483: 000000226503724063419981314690785587
006118204299: 000000229019216486199101082246142899
006131290284: 000000230491882236942111189201626304
006135264039: 000000230940325536024636653641691319
006143720958: 000000231896634970802853417605457912
006158723094: 000000233599567236412697708008114584
006178534032: 000000235861105331732705643432480768
006238374090: 000000242780746383933673463008929000
006270841539: 000000246591146337269450807528073819
006295873401: 000000249555967631483789816274300201
006320184579: 000000252458086230711049786479136539
006325130982: 000000253051298500863992212333326168
006337214058: 000000254504303770824563331667883112
006351072984: 000000256177693125418674830832059904
006402861759: 000000262495810210916668657057468479
006403259118: 000000262544684393980511118610591032
006403859217: 000000262618506598709843247490571313
006429053817: 000000265730364744211996502878089513
006482357019: 000000272394816524617040013985637859
006487213905: 000000273007548310819469673458192625
006523195740: 000000277575564351196433995651224000
006523710849: 000000277641326426118559853387090049
006705293418: 000000301476427957892890158561430632
006718097532: 000000303206783727111975869970552768
006735048795: 000000305507755479643876843679059875
006751201368: 000000307711116216756612835686508032
006783201249: 000000312107429360622738678298041249
006804793512: 000000315097424841032955860166793728
006829053147: 000000318479496416328085256791007523
006835274091: 000000319350648728229109468460735571
006857023419: 000000322408808179453561763471269059
006892704357: 000000327468064708609555329477787293
007103895462: 000000358500433996867492267041751128
007105368294: 000000358723461092090632914758756184
007138509642: 000000363766458009995724112541037288
007233951846: 000000378553129148649381392765243736
007251639804: 000000381336760082477558252199190464
007257324186: 000000382234224723258677111757746856
007260486315: 000000382734078640616656126421305875
007269184530: 000000384111297639829428356545677000
007295106438: 000000388235190564058267907134419672
007304291685: 000000389703515126463707298609844125
007403591286: 000000405814262831237989374509701656
007409658231: 000000406812725937271856608345940391
007459102386: 000000415011093065239367872974288456
007495816821: 000000421169482197745892881818755661
007513968420: 000000424236563727511983954179688000
007538194206: 000000428353150920976672107458493816
007586621349: 000000436661825893396786165242771549
007596214803: 000000438320427681539067980541159627
007610925084: 000000440871821209607561850560992704
007614590829: 000000441509155899627697140608292789
007619523048: 000000442367651405031288977319086592
007648130925: 000000447369056342887107691985203125
007695415086: 000000455717966845619070854918656056
007785901443: 000000471983379775841445040471985307
007868055942: 000000487082265445557290890756956888
007869423135: 000000487336223167128453163949985375
007891406235: 000000491431739055662361894082027875
007912308456: 000000495347104586299327103075682816
007945163082: 000000501543316946402919772802587368
007964025813: 000000505123968951416462870833042797
007980154263: 000000508199063158341202673758269447
008092146573: 000000529896708213689714653004234517
008269417305: 000000565489734821030873199012647625
008330016975: 000000578013070636933389010106859375
008349570621: 000000582093067486314794278512593061
008356492185: 000000583541885198698298556342431625
008378604915: 000000588186613905093431494887760875
008381605728: 000000588818820680260735713618788352
008397436521: 000000592161528348333793793465248761
008417560929: 000000596429074199197687582201645089
008446905231: 000000602688445031829446595230441391
008469257031: 000000607485533231788156290424960791
008579462103: 000000631509925325148088904734166727
008656172004: 000000648601028072770165186504256064
008659174020: 000000649276079127044592151568808000
008705645193: 000000659785685914536751383194004057
008759274063: 000000672054269859377237458039768047
008762437500: 000000672782675854638427734375000000
008769350412: 000000674376259010958126843709134528
008787054963: 000000678469030788057978857659834347
008823651900: 000000686981591125828823386359000000
008940741621: 000000714694817811920491748042426061
008967711342: 000000721181971493976427717634213688
009017624313: 000000733291100176436303414911632297
009047813256: 000000740680455415372399389627081216
009061248783: 000000743984972200818931863801264687
009075346128: 000000747462816900031495378352689152
009084371562: 000000749695091302873045614125876328
009087143520: 000000750381574940393412517982208000
009164080752: 000000769602947514702086850514219008
009170682357: 000000771267361757890298578600153293
009216385407: 000000782855997035746210382669014143
009245170314: 000000790214052155023713434174919144
009253741689: 000000792413958354136924189297865769
009267019854: 000000795829952197046060592191847864
009267083541: 000000795846360180827552471363909421
009285440712: 000000800585212499457147924247024128
009306125487: 000000805947427194116559826320876303
009456840327: 000000845742526724394690304968045783
009470156823: 000000849320315782045965896021413767
009483672015: 000000852961791896342244010758603375
009502148376: 000000857956804354219836402792101376
009526251048: 000000864502129185408425656591022592
009563714028: 000000874741526831528000636719349952
009568042317: 000000875929720418864570326513469013
009670854042: 000000904470665744082600295975442088
009752325846: 000000927522835448325562286974595736
009754012836: 000000928004256739811421977648533056
009806438157: 000000943048180687748107563198655893
009840523170: 000000952915880827425374740139013000
009863527104: 000000959614334952878506710173220864
009879652431: 000000964328492362413989517657578991
009956108298: 000000986890199288581601990286959592
009963027840: 000000988949309679704837296226304000

扫描速度：约$(8e+6)$/秒。

扫描完$10^12$估计需要18小时。

不知道楼主的效率如何？

等$10^12$以内的结果出来了，可以提交到上述链接里的网页，并标明一下这是我们数学研发论坛的研究成果:lol

KeyTo9_Fans 发表于 2010-3-6 15:22:57

扫描速度：$(1.1e+7)$/秒。

扫描完$10^12$用了14小时。

结果如下：

464773002189 100397449064821477702130643488077269
465030789621 100564598779892425630628061364730061
465103512087 100611785651223087715580445031642503
465117967203 100621166790231759566734973115674427
465130758291 100629468487984373052515159551236171
465138073227 100634216247737822625277733351548083
465174380271 100657783547421648870377132144642511
465198020730 100673130805829846429425750963017000
465201977085 100675699402518275057845760747089125
465204978816 100677648254840691725968154868842496
．．．．．．．　．．．．．．．．．．．．．．．．．．．．．．．．
．．．．．．．　．．．．．．．．．．．．．．．．．．．．．．．．
．．．．．．．　．．．．．．．．．．．．．．．．．．．．．．．．
998365340721 995104034127884289699379353307625361
998413925034 995249318013409525433948998241939304
998435076312 995312572061971353997643694480803328
998520137460 995566979118523079014480237284936000
998532469071 995603864993539091698879775222044911
998861437245 996588199234493688742643578497481125
998946772053 996843642857990735296095749903792877
999015263748 997048699405553863192071929783164992
999643178205 998929916534948970207098671334965125
999713620410 999141107246321779190693990634921000

这里只给出了$10^11$到$10^12$之间的解。

如果某个解的末尾是$0$，则可以去掉，作为$10^10$到$10^11$之间的解。

只要稍作处理就可以交到OIES上了。

KeyTo9_Fans 发表于 2010-3-6 16:34:07

源代码如下：#include<cstdio>

unsigned char d02,d13;
unsigned int i,j,k,l,p,s,t,a4,a3,a2,a1,a0,b3,b2,b1,b0,c1,c0,d1,d0;

int main()
{
FILE *f=fopen("d:\\3_copies.txt","w"); //创建一个文件
p=100000000; //每8位数作为一个整体计算
for(i=0;i<p;i++) //预处理10^8以内的数
{
j=i; //对i这个数进行处理
for(l=0;l<8;l++) //一共处理8个数位
{
k=j%10; //取个位数字
if(k==0)d02++; //如果是0，则统计到d02的低位
if(k==1)d13++; //如果是1，则统计到d13的低位
if(k==2)d02+=16; //如果是2，则统计到d02的高位
if(k==3)d13+=16; //如果是3，则统计到d13的高位
j/=10; //把下一位数字移到个位
}
}
a4=999; //对原数的立方赋初值
a3=99999997; //对原数的立方赋初值
a2=88140051; //对原数的立方赋初值
a1=27422222; //对原数的立方赋初值
a0=74318712; //对原数的立方赋初值
b3=1; //对立方数的一阶差赋初值
b2=93899122; //对立方数的一阶差赋初值
b1=9887767; //对立方数的一阶差赋初值
b0=54354837; //对立方数的一阶差赋初值
c1=250645; //对立方数的二阶差赋初值
c0=79701170; //对立方数的二阶差赋初值
d1=4641; //对原数赋初值
d0=58883358; //对原数赋初值
while(d1<10000) //计算到10^12
{
d0+=3; //原数一次增加3
if(d0>=p) //满10^8就进位
{
d0-=p;
d1++;
}
c0+=162; //立方数的二阶差每次增加162
if(c0>=p) //满10^8就进位
{
c0-=p;
c1++;
}
b0+=c0; //把二阶差累加到一阶差中
b1+=c1; //把二阶差累加到一阶差中
if(b0>=p) //满10^8就进位
{
b0-=p;
b1++;
}
if(b1>=p) //满10^8就进位
{
b1-=p;
b2++;
}
if(b2>=p) //满10^8就进位
{
b2-=p;
b3++;
}
a0+=b0; //累加一阶差，得到下一个立方数
a1+=b1; //累加一阶差，得到下一个立方数
a2+=b2; //累加一阶差，得到下一个立方数
a3+=b3; //累加一阶差，得到下一个立方数
if(a0>=p) //满10^8就进位
{
a0-=p;
a1++;
}
if(a1>=p) //满10^8就进位
{
a1-=p;
a2++;
}
if(a2>=p) //满10^8就进位
{
a2-=p;
a3++;
}
if(a3>=p) //满10^8就进位
{
a3-=p;
a4++;
}
s=(d13&15)+(d13&15); //根据d13的低位直接得到原数中1的个数
t=(d13&15)+(d13&15)+(d13&15)+(d13&15)+(d13&15); //根据d13的低位直接得到立方数中1的个数
if((s<<1)+s!=t)continue; //如果个数不符，则跳过以下操作
s=(d02&240)+(d02&240); //根据d02的高位直接得到原数中2的个数
t=(d02&240)+(d02&240)+(d02&240)+(d02&240)+(d02&240); //根据d02的高位直接得到立方数中2的个数
if((s<<1)+s!=t)continue; //如果个数不符，则跳过以下操作
s=(d13&240)+(d13&240); //根据d13的高位直接得到原数中3的个数
t=(d13&240)+(d13&240)+(d13&240)+(d13&240)+(d13&240); //根据d13的高位直接得到立方数中3的个数
if((s<<1)+s!=t)continue; //如果个数不符，则跳过以下操作
s=(d02&15)+(d02&15); //根据d02的低位直接得到原数中0的个数
t=8+(d02&15)+(d02&15)+(d02&15)+(d02&15)+(d02&15); //根据d02的低位直接得到立方数中0的个数
if((s<<1)+s!=t)continue; //如果个数不符，则跳过以下操作
for(i=4;i<10;i++) //检查4到9的个数是否符合条件
{
s=0;
j=d1;
for(l=0;l<8;l++) //统计原数中数字i的个数
{
k=j%10;
if(k==i)s+=3;
j/=10;
}
j=d0;
for(l=0;l<8;l++) //统计原数中数字i的个数
{
k=j%10;
if(k==i)s+=3;
j/=10;
}
j=a4;
for(l=0;l<8;l++) //统计立方数中数字i的个数
{
k=j%10;
if(k==i)s--;
j/=10;
}
j=a3;
for(l=0;l<8;l++) //统计立方数中数字i的个数
{
k=j%10;
if(k==i)s--;
j/=10;
}
j=a2;
for(l=0;l<8;l++) //统计立方数中数字i的个数
{
k=j%10;
if(k==i)s--;
j/=10;
}
j=a1;
for(l=0;l<8;l++) //统计立方数中数字i的个数
{
k=j%10;
if(k==i)s--;
j/=10;
}
j=a0;
for(l=0;l<8;l++) //统计立方数中数字i的个数
{
k=j%10;
if(k==i)s--;
j/=10;
}
if(s)break; //如果数字i的个数不符，则退出循环
}
if(i>9) //如果4到9的个数都符合条件，中途没有退出循环
{
printf("%04d%08d %04d%08d%08d%08d%08d\n",d1,d0,a4,a3,a2,a1,a0); //把结果输出到屏幕
fprintf(f,"%04d%08d %04d%08d%08d%08d%08d\n",d1,d0,a4,a3,a2,a1,a0); //把结果输出到文件
}
}
fclose(f); //关闭文件
return 0;
}工作原理：

从$\root{3}{10^35}$开始，只需检查3的倍数。

每8位数作为一个整体，进行运算时就不用逐个数位进行处理了，直接8位8位地处理。

预处理10^8以内的数中0到3的个数（因为内存不够用，不然4到9也一并预处理了），以后就不用逐位统计了，直接8位8位地统计。

加法运算比乘法运算快，求立方数时，用加法代替乘法。

根据0到3的个数已经淘汰了大量的数，只有少量的数要进行4到9的统计，所以4到9可以逐位统计，对效率影响不大。

得到的3_copies.txt是$10^11$到$10^12$之间的解。

对3_copies.txt稍作处理（去掉末尾0），就得到10^12以内的全部解了。

一共$7886$个解。

上述文件可以作为OEIS中A114259的b-file，发给njas@research.att.com。

keeya0416 发表于 2010-3-18 08:48:47

左边出现一次，右边就出现两次是么
好有难度哦

keeya0416 发表于 2010-3-18 08:49:32

说错了
是左边几次
右边就3的几倍次

页: 1 [2]

数学研发论坛's Archiver