87624375

无心人 · 发表于 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 = [n' | n' <- [1..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 \$ show t1 appendFile filename "\n" appendFile filename \$ show t2 ============================ 估计运行10^8是700秒多点

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

说一下目前的思路.
1<=x<10^8,x的数字组成(前导0是允许的)为a[0],a[1],...,a[7].统计a[0],a[1],...,a[7]中0,1,2,...,9出现的次数,填入数组b[0],b[1],...,b[9].
考虑x^3 mod 10^8,记录其结果中的8个数字(前导0是允许的)d[0],d[1],...,d[7].
统计d[0],d[1],...,d[7]中0,1,2,...,9出现的次数,填入数组c[0],c[1],...,c[9].
int ds=0;
for( int i=0; i<10; ++i ){
if( c[i]>3*b[i] ){
说明x前面的数字组成还有c[i]/3-b[i]个i.
ds+=/c[i]/3\-b[i]; (/c[i]/3\表示c[i]/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/~nja ... e=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$以内的结果出来了，可以提交到上述链接里的网页，并标明一下这是我们数学研发论坛的研究成果

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

3_copies.txt (334.74 KB, 下载次数: 4) 这里只给出了$10^11$到$10^12$之间的解。如果某个解的末尾是$0$，则可以去掉，作为$10^10$到$10^11$之间的解。只要稍作处理就可以交到OIES上了。

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

源代码如下：

#include<cstdio>
unsigned char d02[100000000],d13[100000000];
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[i]++; //如果是0，则统计到d02的低位
if(k==1)d13[i]++; //如果是1，则统计到d13的低位
if(k==2)d02[i]+=16; //如果是2，则统计到d02的高位
if(k==3)d13[i]+=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[d1]&15)+(d13[d0]&15); //根据d13的低位直接得到原数中1的个数
t=(d13[a4]&15)+(d13[a3]&15)+(d13[a2]&15)+(d13[a1]&15)+(d13[a0]&15); //根据d13的低位直接得到立方数中1的个数
if((s<<1)+s!=t)continue; //如果个数不符，则跳过以下操作
s=(d02[d1]&240)+(d02[d0]&240); //根据d02的高位直接得到原数中2的个数
t=(d02[a4]&240)+(d02[a3]&240)+(d02[a2]&240)+(d02[a1]&240)+(d02[a0]&240); //根据d02的高位直接得到立方数中2的个数
if((s<<1)+s!=t)continue; //如果个数不符，则跳过以下操作
s=(d13[d1]&240)+(d13[d0]&240); //根据d13的高位直接得到原数中3的个数
t=(d13[a4]&240)+(d13[a3]&240)+(d13[a2]&240)+(d13[a1]&240)+(d13[a0]&240); //根据d13的高位直接得到立方数中3的个数
if((s<<1)+s!=t)continue; //如果个数不符，则跳过以下操作
s=(d02[d1]&15)+(d02[d0]&15); //根据d02的低位直接得到原数中0的个数
t=8+(d02[a4]&15)+(d02[a3]&15)+(d02[a2]&15)+(d02[a1]&15)+(d02[a0]&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$个解。

3_copies_b.txt (143.92 KB, 下载次数: 2) 上述文件可以作为OEIS中A114259的b-file，发给njas@research.att.com。

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

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

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

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

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 87624375

评分