2的幂同pi的相遇
通过计算机搜索容易知道 误差分析的典型案例\(2^5=32\\
2^{98}=316912650057057350374\cdots\\
2^{872}=314888078651228693933\cdots\\
2^{10871}=314110795831256855459\cdots\\
2^{55046}=314153078230082971872\cdots\)
它们分别是和\(\pi\)的前n位相匹配的最小的2的正整数幂。
请尽量找出更多项。 {1,5}
{2,98}
{3,872}
{4,10871}
{5,55046}
{6,267377}
{7,5073805}
{8,49773799} 寻找最小的2的幂的前n位和$\pi$的前n位相同。
我们假设$2^m$是一个$h$位整数，那么需要它满足条件\(\lfloor10^{n-1}\pi\rfloor\lt\frac{2^m}{10^{h-n}}\lt \lfloor10^{n-1}\pi\rfloor+1\)
也可以两边取对数，变成\(\lg(\lfloor10^{n-1}\pi\rfloor)-(n-1)\lt \{m\lg(2)\}\lt \lg(\lfloor10^{n-1}\pi\rfloor+1)-(n-1)\), 其中$\{x\}$代表$x$的小数部分。
也就是我们需要寻找一个整数m，使得\(m\lg(2)\)的小数部分正好落在某个很小的范围$(e_1,e_2)$之内。
记集合
\(S_2(r,e)=\{m \in Z| 1\le m \le r ; \{m\lg(2)\}\le e \} \cup \{m \in Z| 1\le m \le r ; \{m\lg(2)\}\ge 1-e \}\)
\(S_1(r,e)=\{m \in Z| 1\le m \le r ; e_1-e\le\{m\lg(2)\}\le e_1+e \} \)
如果\(S_2(r,e)\)中存在两个元素$m_1,m_2$,使得\(\{m_1\lg(2)\} \lt \frac12, \{m_2 \lg(2)\} \gt \frac12\), $m = \min\{m_1,m_2\}$
那么对于任意元素\( m \in S_2(r+\min\{m_1,m_2\},e)\), 必然要么\(m \in S_2(r,e)\),要么\(m -m_1 \in S(r,e)\)或\(m-m_2 \in S(r,e)\)
于是我们知道\(S_2(r+\min\{m_1,m_2\},e) \subset S_2(r,e) \cup S_2(r,e)+m_1\cup S_2(r,e)+m_2\)
同理可以知道\(S_1(r+\min\{m_1,m_2\},e) \subset S_1(r,e) \cup S_1(r,e)+m_1\cup S_1(r,e)+m_2\)
于是初始时我们可以选择合适的初始r,e,穷举$S_2(r,e),S_1(r,e)$.
然后每次迭代过程，从$S_2(r,e)$选择合适的$m_1,m_2$ ，那么然后就可以选择新的r为\(r+\min\{m_1,m_2\}\), 并且选择新的较小的e使得新的集合\(S_2(r,e)\)大小合适（选择较小的e可以减小集合的大小，但是要确保集合里面存在可选择的$m_1,m_2$;选择太小的e可能会导致某一边缺元素)
然后利用上面的包含关系得出对于\(S_2,S_1\)的候选元素，再利用实际值计算出两个集合。
实际计算中由于可能存在计算误差，可以对数据进行量化处理，比如一种比较好的方案可以事先将每个浮点数乘上一个非常大的整数M并且仅保留整数部分
比如假设\(\lfloor M\lg(2)\rfloor = a\),那么我们知道\(a\lt M \lg(2) \lt a+1\), \(ma \lt m M\lg(2) \lt ma+m\), \({ma \pmod M} \lt M\{m\lg(2)\} \lt {ma+m \pmod M}\)
所以如果我们发现对于某个m,(ma,ma+m)都落在我们期望的范围内，那么就是找到的一个合法解；但是如果全落在期望范围外，那么不是合法解；而如果和期望范围相交，那么说明计算精度不够，我们需要选择更大的M进行计算。
上面算法稍微修改一下，可以同时计算出A152561前面1000项。
而对于本题，比如前100项可以是
1 5
2 98
3 872
4 10871
5 55046
6 267377
7 5073805
8 49773799
9 937991810
10 58640001710
11 66333603030
12 66333603030
13 1801688025777
14 35602803793130
15 63205675650578
16 5548739667270910
17 72119846655391741
18 296928725312215371
19 7252366739066359510
20 16084305222148286266
21 453703419558932235202
22 10175272821206981727205
23 22336535636867457464619
24 126107684429916629691933
25 2138903877215688789739495
26 149655928531754487396199162
27 666161605884479207276201387
28 4314482908387894201682096888
29 27937023501595580552799437286
30 27937023501595580552799437286
31 4536510974652466790139020659348
32 74619415858626948200141315521373
33 311782703402299711456218031258100
34 5597220756123394037424045898739803
35 32902981265019582238877489804233201
36 238797902033598588188366699920282891
37 238797902033598588188366699920282891
38 229551909130685802912050849148287325882
39 229551909130685802912050849148287325882
40 606708590640696309452032468268226538343
41 59168821235734934575343765647257161057239
42 146428350139588135639056342890484230534255
43 10034285252406182505966148370388868551792527
44 39123494667266230069333837489786986030227209
45 761078991177212327594023869690820599553056548
46 1350279072151113224639122971099406737362693892
47 37584848069933235068616426821224016914615233264
48 139100561271820566321457387511713784024703307240
49 586862628430868026498247384656386583475786505289
50 22240774064117422642324423014598946760337225257448
51 606000858693336302349277585028758725936693905169643
52 5586155758260488591191626871839783873349593911116116
53 238583134589085218379409266423265815427799331763561648
54 436174893248931562108242492995322548419373417018315624
55 25209342537559844391349762071023209464294533225519539424
56 25209342537559844391349762071023209464294533225519539424
57 921775720533122561673197833415739151994359797447352242761
58 23051117839422112438562020454346281536988298905477376285227
59 110671094164727698865074488149404467538203460901382023044294
60 1926368547145816012373243892216094168746458169721038056501909
61 10769507926551222428270177319382644025209182675212939770605111
62 14948752032584121563722479756307303086017977003935709742117209
63 1699907614665767000908062729325174893585307785808573149701933897
64 1699907614665767000908062729325174893585307785808573149701933897
65 54122560671608850168309511345106537459618419023619021382357455773947
66 88968993677517137490612136325697902720478686187898761922647673116466
67 89743865307471932630545615233049182261923584215096610960168842109040
68 89789445991586920579953466933481610470243872334343543256493616755662
69 581557430760033378633908224824640623759523303389523998146801110389431
70 5253205148836901019310902906764245858330636962026185789641666782308715
71 153024778366120189158747946964987881139250036245795666724583535636992578
72 230844583506028088676037235465052781708451090543793921767362036883126451
73 7706463397252476504458525551569243312985915976453760846159964094737052772
74 28745103030754088939030601834504492467664745479790556719509867245177925188
75 68606423392386268501035285155004612534414646976388380510154547275815961803
76 1429150975596255776717837537122742507092581005236548588360411144105119424817
77 52736490415635350696444919297762515111924073311532492447732052499099880871303
78 972346411961173979445130002966657208795483435356065392588033405818640228665469
79 972346411961173979445130002966657208795483435356065392588033405818640228665469
80 345619676395827607671912721272924243012416693815979941998674657302029615492411836
81 345619676395827607671912721272924243012416693815979941998674657302029615492411836
82 8957173299571157628040510048475921842428301562776096356946392689188743219290976450
83 33238001848901292973988639139888315325221983126673252601017149555594667058663975997
84 460127529793472544465528702567911801100638393364878755578570657889760365591556708934
85 5480973403395687370776742991047206457618485982083771550723479516565703388207593592444
86 5480973403395687370776742991047206457618485982083771550723479516565703388207593592444
87 275390212926106389313125170168592081635104971702012097331933161912631460571789227537200
88 5830313906397283675952367023439082025044523289709994696673209301534069763530795950631406
89 26402009616725611636576409533376860474055002284515291134195266722526508985640150340059101
90 26402009616725611636576409533376860474055002284515291134195266722526508985640150340059101
91 1891535870136435103633411395557881517086760051854263738778393304757352237034875945432957481
92 56518577911803659660889716945333187161178733331796359695755395994988088398217010562258028829
93 97333431621344102287832209858829291006196654537622119292851131509491571708432841875285757475
94 3034759476134576165099693809639865764743078511324030311318647956528385819558606539216553621067
95 14029699716204426179330703562362004489333876513670148151616838182591987507341649988589794245214
96 705956170902621898838867881337454736968197421236676057162597825350586918534055735959112122736254
97 3289685497611617571297901288241330345039344915945602098113478337004504308196450514899197613953507
98 1199707355501193078587966790959674065787651169256354418299943304099108127251266345598752664148416112
99 1295762959923470173500719308130383284395028005324399237048519770958339712755563500795699717795573784
100 1302624074525061394565915916499719657152697779329259581244846661448284826005870440452624507341799332
前1000项： 类似还有和n!相遇的2的幂
其前面100项为：
0 0
1 0
2 1
3 6
4 81
5 80
6 56
7 7284
8 33889
9 2044921
10 8151937
11 127668791
12 258943304
13 19207561921
14 189815680859
15 2687562198191
16 75909586168557
17 512148453482307
18 5376323935222903
19 502774568129731130
20 1053338431686717460
21 122114339415457901831
22 2120280158164651048122
23 24295599496258126721517
24 1396210880036788184929402
25 1396210880036788184929400
26 25343081767253562060890601
27 2272389318478657196796868914
28 2538055936188205690585764610549
29 719526445215534406801202848806
30 294312848906727817756509986343899
31 10583147068673302112872600709850358
32 99877727198514710986890483815128509
33 8887621061935839424871526624423947995
34 891640411838709432577010999936107580919
35 11568904844423988214896902487640613857755
36 845105570115600692831846460599103445721479
37 12152094821898368586315236214075502975278644
38 1592922380829535673166461151872226318415323935
39 19232767668031700681465235839872703210813797266
40 1870097535154610737476040030726339937114503761295
41 41439609680903198176195478758243279336138750603043
42 2525079832709436633496752887249543564262344665280653
43 220339474371330365685812921232285302533020652465509197
44 51531779925626770433011076736554493386972754226510072387
45 120722606291443824716288233918130815252952270308435591115
46 45747691339069721863616088918881161444654261023470218956315
47 1030833443292551859554521432371749476221846044352195879168897
48 21970692989139375122941534717016973672980139742789149776399243
49 1761351058609172673086794501206369061813892431039231571514829517
50 22375522450885265612969403967487665298015927162793289047170094586735
51 114763786252275449882326043450951747878303113193875378593106150129238
52 7557780415110635899491185709206335943978800774620253565365566308998
53 4645775778031099646703478139251949282467902725740957677171962419369128
54 425364055069352222746063422097543159871764999843919760867277132119849295
55 39236722719931010513435517211500872355978124339235388432003878581952085986
56 1012419529495334120336069094468771437868640604202544541931213101614222809357
57 47786959706716076452178505376858113937170215348093622453559191570427846058366
58 2573397472606263295460586570262411872333883774212448957771800549388090414340473
59 378003225353739248513055935201460121354596678914015932520758507660897434264998211
60 31316062680174127613282880095856039880087598711862855776058575850350163179986935006
61 292872290299292660972277168603244979179586980021367197052225730689713168721549451893
62 57719181732746299211793800890347179807460766683395063874340113237073555215946080727849
63 61292881855965986204247391756545284658115765712195025710659068045864780947999885864099
64 165018440225098408048771642137323118116702883876743878983011969799963254507204885828664442
65 4174270891566111381738537542158833561343377092911452373840383156304577039325132088407440921
66 433221844741907409107690510489706273364881563248930110066621447668650916582635929958688147709
67 58570849861355501742350504710434033263373926719568179420588726369867473701455748244324803840139
68 1493870993488216291011573623527069369266102573517954657462399930022625956879503494807828263290479
69 1013945471766975681095680194949146501130100010255765253680852887388756350412452352494782865222077850
70 76767266446222143787820471943884806584393644841174177243511825468807952697524748390709878475999145461
71 125685424573854635287231552241446800871069964037284108997862284376937214332954791359145296167934507614
72 100144161029135337918565796285563515295969548537682247598038275383858815906728777122765569404138972449608
73 11785058476427991499027546213346045377363986360742286025468082154268661707510632100728640843397983717658835
74 554212109377510697859560022830988592204134315450259856411247416718528753296527814335598856208967093794744428
75 163798043674276882127678417301456806975414325098545154215259405656522198779512484883119276144005193063010791994
76 1897619964511331278269828874651636981585369707829960969076828549219935852426229067281915156527472816372515976880
77 79013214144519954308839159646731182158167510544317551706667712286837336923529971315105638807322203740024348077997
78 10540896447635444368110417785040434807175041115628771244101755143776641163614022829165957894220086920388526923065720
79 1207860281874230346273285055728541154948324961572323714765450148443630008512148298038496669482630567782591400378216140
80 77070032562974163716329842737151665596666949439739087183024344155905967675496843649536493303836485355017302751802701813
81 9155661577748783058755804614207442084665117235313589677398665479250209556547436205686423218020720391324872311249906131693
82 636180845090809916825551067739273699882636058996461881937471737909200254681811739854586426125028844871795930012021042896375
83 35414620684659699542999808601670167857618582502250934881828966654854247538127422707252495881952409584188317340606837137289880
84 9156093314320409565287903376238369509120975845426752184725287560806505020395899479657492422415270268223224814297516386582043003
87 4920096332840652311369323375109711588215412424040205585264722902076907764093755846608944277347695627561816275956351213123598221599874
88 853532638338042616026253881566842558493555959853387927892432232696547568846127220317829923913070383601283418212007189157341943767594813
89 13391046695384207945406369225943471605460691561364509112268099960471964597208486841850827267054328137950019199121783465358015165839196937
90 1229595859137934796793887137756600772009539396730419887677575147942522791943802708556941663410815502759209410653961841797567100837084476828
91 62115380824904457317077688057912792686101479518875000127450003886116923205160018669749461805884717151470283138400975601621708830709360040091
92 44574860819987004103638261278957964228283013199843800638228982621178836769800320784882313973106352909902467653129827905069764487899700508436605
93 246854148842645054275740695213247924155308431345663174652340176096230282517696916614749574578705370036942858429333562818824929358889777143716908
94 269185560043973492627104925775943886460511474095895799264702792496567364232966718581330946033362520987150423616109796018977267974101783395725120588
95 21868590646710522575376306196835845163627703874936612380112942127936112358819962524964063544760736062068784605451086871991058247731920836280088594093
96 9722604150628670367920952840243851869752144574920192175842454242836659933315316455275505164709314877332946127497367716802262948371486918844517331299992
97 134514624713790838117522237983168526353128206046710026992503894482322682927544220520890524415087280044513204826556307876257835681281260055343468180108884
98 7891571671690193027702010987870833895477168090867558338774877017003475995395873347101104582826800232093849208423297179019398728045912977034512893656643022
99 270484306588640551267066858018071668446522241930348526384603180718084288838878376094833748032462289784758589052561036656819860987712293960206638066434441959
100 8390953406129522152705086405803700986055275914442173937223426436997625848378454179961282742174811541771137509117536684015144277866820481888531017827600228113
前758项：
和n!相遇的3的幂
前100项为
0 0
1 0
2 3
3 8
4 5
5 805
6 1689
7 12317
8 197209
9 520852
10 4493819
11 16769097
12 2053077332
13 1110380591
14 39230711849
15 516641987008
16 62653098988435
17 398166000236882
18 7896283077809532
19 99956735615338266
20 5161719458617927763
21 63295038588725505792
22 659220983938327840981
23 18741443789015137945475
24 31407903592822606578249
25 46391489386483823834469694
26 3793216881406769379073090682
27 403605176594753406466859269062
28 465685673166697291272149831728
29 36591230974364102878618511096025
30 810415231911788111377651219003976
31 18801114953804077033947292115806130
32 39328579366851028905558779545946232
33 16573977732210622184389297186647883994
34 160059870193585417316370516153102559551
35 14745272543636954468350367390003212959750
36 115682951803175966028431596897666655500245
37 180531979575742198149601608824366310410152857
38 460629689665928219539416868635359283467811142
39 33196969453444409177231471916326559832651431666
40 2144035166650676947534220650137976300064223833799
41 11715255132654033668100148141549338707141145331514
42 2090526230380314632322241227264225705780343176922628
43 114904958462862446933186417998257293289587968077410250
44 2173059229669108761286523270074097052794857878342170304
45 233593701522132525903038004032943199470238305518768387753
46 7768291632448544793251458989058065116310856374483710852296
47 379037471398344443844433928698077675462789902805838760677695
48 24811687563950017839141782553094703874322229555782284499927662
49 712495299728146893246075841099139408448991090592441373366917666
50 15109746472807370045258048795410026788190556222636419351209641710
51 2225654840662105835959009378858635743998789684349601245114779956939
52 143864179007603159965228986745297707186564085785666649800068334823278
53 13637586409915340371667042895064008857373761940045442329115443793359386
54 167033744822976165000601921813277271842935845496433864699742203969854795
55 23656671630460039344092428785766813462995643873830249321533081106163992151
56 695706707693380105860469302846688185865625299848685069395426331180908979941
57 89102725243109777324443546143798031506754048423800575417427237158929334223916
58 230779823840900826246905518478675441923538451672788323027435752104009544385821
59 197803317024213303227520984021673571346522346003403853295578809868777637026022332
60 8938150288364662660647992563505395743897419367567348646771233175354438557644993202
61 911577751078110051930236759138908970719357539686526738871823966588522501243904297667
62 2365422520828887910543844377024633544057049429422996365306705227510815546964115276614081
63 2728655546518204219662635987300386189450975715441195624837273791348023177627059964275632
64 594354839179719434022278818214654397244949494968008865315285500344140815369095426545791267
65 41403057794174165805903019058335441888029514499484653954799116530448926886931061049814626858
66 1049779121880534872170762664462627916935501846702916691326619812028080824842487369316119453617
67 30954714881094098984725336648215825191382884222016021245326619185282932935559938807745817240297
68 5763913093234787880444024582145574974339131124763766746087495334622302710128923487545192557731264
69 45137454716750167373585891896631678542321592800078342604306701170953229830276815926463995242972148
70 6480344710757925276626303679576598636552497589619916799420084578473193911487777176766305754525951440
71 1500870726459501408752140498470234239390585932605018139211816837577542085098927309468998263250543153065
72 62823124052416818446989138032942505191227617305483657130689948904549109115152728967166221991677048752521
73 302967108534731055592253050547173946657121443239808857782111205836954041267515053892516418882780610482870
74 509506184773886581601670975370361836190808751479387000086058534811143316994113800580810077865560232166009776
75 93318850222267469220378193505738384251511184133416201605588597110010221594959988402335733519105960968970450965
76 5682929998966352314641557457350684637912082379118815482398091204424236559637184305491673703631404846402130107614
77 353033490077630841643338107783369682344854188820052543373154806317643779012742044197720694723130001897768657144869
78 3214782472991747801021065443731585213708166027689636585854831666360236128947234642022735271235912266630680543423054
79 523847275350268850722599520487365258741822899416995873803158216081250188049699656290143723676977313819417188091079731
80 57530432739629835039001996096371592441682382193732893431872417112656399870963519116725973128861303665948407101962150757
81 51927889657769748251572723630769362329950311285227607317590385470043200670305331092591931168837969103498187090582075557570
82 91963595070847321177761718919549264606338458061239285764543080012032992385565474958890594974577492995948933722386051368936
83 3816798961783743876125370816230341143813371932727150161373085188530715574959151076293549577446049141166361395837143031983560
84 1580078228810824325487976173560382965214207832916349367068987243437083305034754873151579208534548026975500867473798985938282735
85 3454285282637984686108383919640358638929883568630260319966231796329574152003167369975371815148475402966012802931749173950626039177
86 392871403373372307567062183463316215018949380768203297191021326534665870767782525822308432725337681317402495612035235386939642593061
87 6825290722437835599175818151143576455805466144451325029150614679717097484773944793386878734841417033212059484704571178409607669660922
88 321664336579998561447378027785402329331012118116172885608765813568585393966345491065916702760402389569885767793915665461977600073941235
89 7947233835122249073038674016837816673526544769590892924192961892223754024113169800343078681204290138421210278855199143842164928395808655
90 871665135887296671720506983347382163614829818900334947235728808279793627581476725031638064421376497253409698585201127004234353057526474623
91 233361113154750074086172177690587671769239338920951729677601270120059494615373826128051194724154558576770274241537036447570681766293197984160
92 14735917507660157369463511604234773756874070080275075779251653310575689325885781235557129255749586688176318409752508986830394981994212911964426
93 1948007075018816163634964917715693321252841642518976086579368562264258445837054750565163390710665434923900935078128816964919909576259263381564109
94 1032055217475139304091717639388710730145633852449817295981596385291695609908576975079836954748209408779791883548396696174642083741341986334850960717
95 157256384049801804235230703423272615921727741472255495889584659664653508450517104346149260578736867034679137496542481172226371151505408328700315761049
96 7408529516803940214014361167024289761860309016320549716885231857699666741872336078922754025184958000195858374394721947512924014963517235217743892450371
97 35418864772624409717121359595244523254938804569860189272786621965978409552254691422394896257738584991370520076355904254437190582114122139099240349071561
98 17277149481381292946889861261816988781831488916660464594210937353769504382013928456671038156262032520744219307554681653645644743021063486728513918070387989
99 1360504394176668762907257522052066949072305299823153672276636871574947829496177682710046804961987683754846803440285368766671671884854705180410007537869998301
100 136045541320034945436593508900132950237115671079795689880103371118620175782324164981176046207558000520681214904948391234424942406863056709490808136956113029022
前1000项: northwolves 发表于 2024-10-4 22:10
{1,5}
{2,98}
{3,872}
你是怎么计算的？ 我居然没看懂 花了点时间，写了python代码。不过，我不能讲明白算法原理。主要是，不能证明我的这个算法为什么不会漏掉某些解。但是，这个代码的计算结果和楼主给出的结果完全一致，从侧面说明了我的算法的有很高的可信度。或许以后，我的这个算法被证明或者证伪。下面是源代码。今年了python比较火，这是我第一次写数值计算的Python程序。
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import mpmath
from mpmath import mpf,exp,log,floor,pi
# 全局变量，常数
log10_2 = mpf(0) # will calc later
# 令 a* 10^d =2^n, (1<=a<10), 已知n，d,求a
def calc_a( n, d ):
global log10_2
# 令 a* 10^d = 2^n, (1<=a<10),
# 两边取常用对数，
# log10(a) + d = n*log10(2)
# d = n*log10(2) - log10(a) = floor(n*log10(2))
c2= mpf(2)
c10 = mpf(10)
v_2pn = c2 ** n # 2^n
d= mpmath.floor(n*log10_2)
a= v_2pn/ (c10 ** d)
return a
# 令 2^n = a*10^d , (0.1< a <= 1.0), 已知n，d,求a
def calc_a1( n, d ):
c2 = mpf(2)
c10 = mpf(10)
a = (c2 ** n) / (c10 ** d)
return a
def search_in_interval( base, pi_lo, pi_hi ,layer=0):
(n,d) = base
a= calc_a(n,d )
esp= (10 ** (-mpmath.mp.dps)) * mpf("4.0")# 精度误差
if a>= pi_lo and a < (pi_hi-esp):
return base
low= pi_lo / a # 放大倍数的下界
high = pi_hi / a # 放大倍数的下界
#print(f"\n2^{n} = {a} * 10^{d}")
l_lo=log(low); l_hi=log(high) # 取对数，方便计算，乘除变加减
# 定义一个区间 (start, end)c0
# 因为 2^3= 0.8 * 10^1, 2^4=1.6*10^1, 所以
# begin=(3,1,0.8),end=(4,1,1.6)
begin=(mpf(3),mpf(1),log(mpf("0.8")))
end=(mpf(4),mpf(1),log(mpf("1.6")))
iter_count=0
c0= mpf(0)
while True:
(n0,d0,v0)=begin ; (n1,d1,v1)=end
#print(f"v0:{v0}, v1:{v1}, mid_v:{mid_v}")
l_m = v0 + v1 # l_m=log(mid)
mid = (n0+n1,d0+d1,l_m)
if l_m < l_lo and l_m < c0 :
begin = mid # mid总是大于begin, begin 不断增大，但 begin.v0始终<=0
elif l_m > l_hi and l_m > c0 :
end = mid # mid总是小于end,end 不断减小，但end.v始终>=0
else:
break
iter_count +=1
#end while
(n0,d0,v0)=begin;(n1,d1,v1)=end
l_m = v0 + v1
if l_m >= l_lo and l_m<l_hi:
(n,d)= base
#print("layer:", layer, ",get an result:", n+(n0+n1))
return ( n+(n0+n1),d+(d0+d1))
if n0<n1:
base = (n+n0,d+d0)
else:
base = (n+n1,d+d1)
return search_in_interval( base, pi_lo, pi_hi,layer+1 ) # 递归调用
#end search_in_interval
def question_19684(MAX_N,debug=False ):
r0= (mpf(5.0), mpf(1.0) ) # 2^5/10^1=3.2
print(1, 5)
results=
c10 = mpf(10)
for i in range(2, MAX_N+1):
v_10p_i= c10 ** (i-1) # 10^(i-1)
tmp = floor(pi * v_10p_i)
pi_lo = tmp/v_10p_i # 圆周率的下界
pi_hi = (tmp+1)/v_10p_i # 圆周率的上界
if debug:
print(f"\n{i}:pi_lo={pi_lo},pi_hi = {pi_hi}")
base = results[-1]
res = search_in_interval(base, pi_lo, pi_hi )
(n,d)=res # 2^n/10^d是一个非常接近于1.0的数
a=calc_a(n,d)
if debug:
print(f"2^{n} = {a} * 10^{d}")
s=str(n)
if s.endswith(".0"):
s=s[:-2]
print(i, s)
results.append((n,d))
#end for
def main():
global log10_2
MAX_N=1000
mpmath.mp.dps = (MAX_N*2)+16
c2 = mpf(2)
c10 = mpf(10)
log10_2 = log(c2)/log(c10)
#question_19684(MAX_N,True)
question_19684(MAX_N,False)
main() 核心部分类似于二分查找。基本原理是，若a<1.0（ 但非常接近于1），b>1.0（也非常接近于1）,那么， a*b 的值 介于 a与b之间（a*b的值更加接近于1）
页:
[1]