数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 2的幂同pi的相遇
返回列表 发新帖
查看: 475|回复: 11

[原创] 2的幂同pi的相遇

[复制链接]
mathe
发表于 2024-10-4 16:13:08 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
通过计算机搜索容易知道
精华

\(2^5=32\\
2^{98}=316912650057057350374\cdots\\
2^{872}=314888078651228693933\cdots\\
2^{10871}=314110795831256855459\cdots\\
2^{55046}=314153078230082971872\cdots\)
它们分别是和\(\pi\)的前n位相匹配的最小的2的正整数幂。
请尽量找出更多项。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

northwolves
发表于 2024-10-4 22:10:51 | 显示全部楼层
{1,5}
{2,98}
{3,872}
{4,10871}
{5,55046}
{6,267377}
{7,5073805}
{8,49773799}
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2024-10-5 10:51:49 | 显示全部楼层
寻找最小的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进行计算。


点评

liangbch
赞一个，不过，这个算法分析对我来说太难了  发表于 5 天前
northwolves
妙哉！  发表于 2024-10-5 15:02

评分

参与人数 1威望 +8 金币 +8 贡献 +8 经验 +8 鲜花 +8 收起 理由
northwolves + 8 + 8 + 8 + 8 + 8 赞一个!

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2024-10-5 10:58:49 | 显示全部楼层
上面算法稍微修改一下，可以同时计算出A152561前面1000项 tn0.tgz (221.61 KB, 下载次数: 0) 。
而对于本题，比如前100项可以是

  2. 1 5
  3. 2 98
  4. 3 872
  5. 4 10871
  6. 5 55046
  7. 6 267377
  8. 7 5073805
  9. 8 49773799
  10. 9 937991810
  11. 10 58640001710
  12. 11 66333603030
  13. 12 66333603030
  14. 13 1801688025777
  15. 14 35602803793130
  16. 15 63205675650578
  17. 16 5548739667270910
  18. 17 72119846655391741
  19. 18 296928725312215371
  20. 19 7252366739066359510
  21. 20 16084305222148286266
  22. 21 453703419558932235202
  23. 22 10175272821206981727205
  24. 23 22336535636867457464619
  25. 24 126107684429916629691933
  26. 25 2138903877215688789739495
  27. 26 149655928531754487396199162
  28. 27 666161605884479207276201387
  29. 28 4314482908387894201682096888
  30. 29 27937023501595580552799437286
  31. 30 27937023501595580552799437286
  32. 31 4536510974652466790139020659348
  33. 32 74619415858626948200141315521373
  34. 33 311782703402299711456218031258100
  35. 34 5597220756123394037424045898739803
  36. 35 32902981265019582238877489804233201
  37. 36 238797902033598588188366699920282891
  38. 37 238797902033598588188366699920282891
  39. 38 229551909130685802912050849148287325882
  40. 39 229551909130685802912050849148287325882
  41. 40 606708590640696309452032468268226538343
  42. 41 59168821235734934575343765647257161057239
  43. 42 146428350139588135639056342890484230534255
  44. 43 10034285252406182505966148370388868551792527
  45. 44 39123494667266230069333837489786986030227209
  46. 45 761078991177212327594023869690820599553056548
  47. 46 1350279072151113224639122971099406737362693892
  48. 47 37584848069933235068616426821224016914615233264
  49. 48 139100561271820566321457387511713784024703307240
  50. 49 586862628430868026498247384656386583475786505289
  51. 50 22240774064117422642324423014598946760337225257448
  52. 51 606000858693336302349277585028758725936693905169643
  53. 52 5586155758260488591191626871839783873349593911116116
  54. 53 238583134589085218379409266423265815427799331763561648
  55. 54 436174893248931562108242492995322548419373417018315624
  56. 55 25209342537559844391349762071023209464294533225519539424
  57. 56 25209342537559844391349762071023209464294533225519539424
  58. 57 921775720533122561673197833415739151994359797447352242761
  59. 58 23051117839422112438562020454346281536988298905477376285227
  60. 59 110671094164727698865074488149404467538203460901382023044294
  61. 60 1926368547145816012373243892216094168746458169721038056501909
  62. 61 10769507926551222428270177319382644025209182675212939770605111
  63. 62 14948752032584121563722479756307303086017977003935709742117209
  64. 63 1699907614665767000908062729325174893585307785808573149701933897
  65. 64 1699907614665767000908062729325174893585307785808573149701933897
  66. 65 54122560671608850168309511345106537459618419023619021382357455773947
  67. 66 88968993677517137490612136325697902720478686187898761922647673116466
  68. 67 89743865307471932630545615233049182261923584215096610960168842109040
  69. 68 89789445991586920579953466933481610470243872334343543256493616755662
  70. 69 581557430760033378633908224824640623759523303389523998146801110389431
  71. 70 5253205148836901019310902906764245858330636962026185789641666782308715
  72. 71 153024778366120189158747946964987881139250036245795666724583535636992578
  73. 72 230844583506028088676037235465052781708451090543793921767362036883126451
  74. 73 7706463397252476504458525551569243312985915976453760846159964094737052772
  75. 74 28745103030754088939030601834504492467664745479790556719509867245177925188
  76. 75 68606423392386268501035285155004612534414646976388380510154547275815961803
  77. 76 1429150975596255776717837537122742507092581005236548588360411144105119424817
  78. 77 52736490415635350696444919297762515111924073311532492447732052499099880871303
  79. 78 972346411961173979445130002966657208795483435356065392588033405818640228665469
  80. 79 972346411961173979445130002966657208795483435356065392588033405818640228665469
  81. 80 345619676395827607671912721272924243012416693815979941998674657302029615492411836
  82. 81 345619676395827607671912721272924243012416693815979941998674657302029615492411836
  83. 82 8957173299571157628040510048475921842428301562776096356946392689188743219290976450
  84. 83 33238001848901292973988639139888315325221983126673252601017149555594667058663975997
  85. 84 460127529793472544465528702567911801100638393364878755578570657889760365591556708934
  86. 85 5480973403395687370776742991047206457618485982083771550723479516565703388207593592444
  87. 86 5480973403395687370776742991047206457618485982083771550723479516565703388207593592444
  88. 87 275390212926106389313125170168592081635104971702012097331933161912631460571789227537200
  89. 88 5830313906397283675952367023439082025044523289709994696673209301534069763530795950631406
  90. 89 26402009616725611636576409533376860474055002284515291134195266722526508985640150340059101
  91. 90 26402009616725611636576409533376860474055002284515291134195266722526508985640150340059101
  92. 91 1891535870136435103633411395557881517086760051854263738778393304757352237034875945432957481
  93. 92 56518577911803659660889716945333187161178733331796359695755395994988088398217010562258028829
  94. 93 97333431621344102287832209858829291006196654537622119292851131509491571708432841875285757475
  95. 94 3034759476134576165099693809639865764743078511324030311318647956528385819558606539216553621067
  96. 95 14029699716204426179330703562362004489333876513670148151616838182591987507341649988589794245214
  97. 96 705956170902621898838867881337454736968197421236676057162597825350586918534055735959112122736254
  98. 97 3289685497611617571297901288241330345039344915945602098113478337004504308196450514899197613953507
  99. 98 1199707355501193078587966790959674065787651169256354418299943304099108127251266345598752664148416112
  100. 99 1295762959923470173500719308130383284395028005324399237048519770958339712755563500795699717795573784
  101. 100 1302624074525061394565915916499719657152697779329259581244846661448284826005870440452624507341799332
复制代码


前1000项： tnpi.tgz (218.35 KB, 下载次数: 5)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2024-10-5 11:03:10 | 显示全部楼层
类似还有和n!相遇的2的幂
其前面100项为：

  2. 0 0
  3. 1 0
  4. 2 1
  5. 3 6
  6. 4 81
  7. 5 80
  8. 6 56
  9. 7 7284
  10. 8 33889
  11. 9 2044921
  12. 10 8151937
  13. 11 127668791
  14. 12 258943304
  15. 13 19207561921
  16. 14 189815680859
  17. 15 2687562198191
  18. 16 75909586168557
  19. 17 512148453482307
  20. 18 5376323935222903
  21. 19 502774568129731130
  22. 20 1053338431686717460
  23. 21 122114339415457901831
  24. 22 2120280158164651048122
  25. 23 24295599496258126721517
  26. 24 1396210880036788184929402
  27. 25 1396210880036788184929400
  28. 26 25343081767253562060890601
  29. 27 2272389318478657196796868914
  30. 28 2538055936188205690585764610549
  31. 29 719526445215534406801202848806
  32. 30 294312848906727817756509986343899
  33. 31 10583147068673302112872600709850358
  34. 32 99877727198514710986890483815128509
  35. 33 8887621061935839424871526624423947995
  36. 34 891640411838709432577010999936107580919
  37. 35 11568904844423988214896902487640613857755
  38. 36 845105570115600692831846460599103445721479
  39. 37 12152094821898368586315236214075502975278644
  40. 38 1592922380829535673166461151872226318415323935
  41. 39 19232767668031700681465235839872703210813797266
  42. 40 1870097535154610737476040030726339937114503761295
  43. 41 41439609680903198176195478758243279336138750603043
  44. 42 2525079832709436633496752887249543564262344665280653
  45. 43 220339474371330365685812921232285302533020652465509197
  46. 44 51531779925626770433011076736554493386972754226510072387
  47. 45 120722606291443824716288233918130815252952270308435591115
  48. 46 45747691339069721863616088918881161444654261023470218956315
  49. 47 1030833443292551859554521432371749476221846044352195879168897
  50. 48 21970692989139375122941534717016973672980139742789149776399243
  51. 49 1761351058609172673086794501206369061813892431039231571514829517
  52. 50 22375522450885265612969403967487665298015927162793289047170094586735
  53. 51 114763786252275449882326043450951747878303113193875378593106150129238
  54. 52 7557780415110635899491185709206335943978800774620253565365566308998
  55. 53 4645775778031099646703478139251949282467902725740957677171962419369128
  56. 54 425364055069352222746063422097543159871764999843919760867277132119849295
  57. 55 39236722719931010513435517211500872355978124339235388432003878581952085986
  58. 56 1012419529495334120336069094468771437868640604202544541931213101614222809357
  59. 57 47786959706716076452178505376858113937170215348093622453559191570427846058366
  60. 58 2573397472606263295460586570262411872333883774212448957771800549388090414340473
  61. 59 378003225353739248513055935201460121354596678914015932520758507660897434264998211
  62. 60 31316062680174127613282880095856039880087598711862855776058575850350163179986935006
  63. 61 292872290299292660972277168603244979179586980021367197052225730689713168721549451893
  64. 62 57719181732746299211793800890347179807460766683395063874340113237073555215946080727849
  65. 63 61292881855965986204247391756545284658115765712195025710659068045864780947999885864099
  66. 64 165018440225098408048771642137323118116702883876743878983011969799963254507204885828664442
  67. 65 4174270891566111381738537542158833561343377092911452373840383156304577039325132088407440921
  68. 66 433221844741907409107690510489706273364881563248930110066621447668650916582635929958688147709
  69. 67 58570849861355501742350504710434033263373926719568179420588726369867473701455748244324803840139
  70. 68 1493870993488216291011573623527069369266102573517954657462399930022625956879503494807828263290479
  71. 69 1013945471766975681095680194949146501130100010255765253680852887388756350412452352494782865222077850
  72. 70 76767266446222143787820471943884806584393644841174177243511825468807952697524748390709878475999145461
  73. 71 125685424573854635287231552241446800871069964037284108997862284376937214332954791359145296167934507614
  74. 72 100144161029135337918565796285563515295969548537682247598038275383858815906728777122765569404138972449608
  75. 73 11785058476427991499027546213346045377363986360742286025468082154268661707510632100728640843397983717658835
  76. 74 554212109377510697859560022830988592204134315450259856411247416718528753296527814335598856208967093794744428
  77. 75 163798043674276882127678417301456806975414325098545154215259405656522198779512484883119276144005193063010791994
  78. 76 1897619964511331278269828874651636981585369707829960969076828549219935852426229067281915156527472816372515976880
  79. 77 79013214144519954308839159646731182158167510544317551706667712286837336923529971315105638807322203740024348077997
  80. 78 10540896447635444368110417785040434807175041115628771244101755143776641163614022829165957894220086920388526923065720
  81. 79 1207860281874230346273285055728541154948324961572323714765450148443630008512148298038496669482630567782591400378216140
  82. 80 77070032562974163716329842737151665596666949439739087183024344155905967675496843649536493303836485355017302751802701813
  83. 81 9155661577748783058755804614207442084665117235313589677398665479250209556547436205686423218020720391324872311249906131693
  84. 82 636180845090809916825551067739273699882636058996461881937471737909200254681811739854586426125028844871795930012021042896375
  85. 83 35414620684659699542999808601670167857618582502250934881828966654854247538127422707252495881952409584188317340606837137289880
  86. 84 9156093314320409565287903376238369509120975845426752184725287560806505020395899479657492422415270268223224814297516386582043003
  87. 87 4920096332840652311369323375109711588215412424040205585264722902076907764093755846608944277347695627561816275956351213123598221599874
  88. 88 853532638338042616026253881566842558493555959853387927892432232696547568846127220317829923913070383601283418212007189157341943767594813
  89. 89 13391046695384207945406369225943471605460691561364509112268099960471964597208486841850827267054328137950019199121783465358015165839196937
  90. 90 1229595859137934796793887137756600772009539396730419887677575147942522791943802708556941663410815502759209410653961841797567100837084476828
  91. 91 62115380824904457317077688057912792686101479518875000127450003886116923205160018669749461805884717151470283138400975601621708830709360040091
  92. 92 44574860819987004103638261278957964228283013199843800638228982621178836769800320784882313973106352909902467653129827905069764487899700508436605
  93. 93 246854148842645054275740695213247924155308431345663174652340176096230282517696916614749574578705370036942858429333562818824929358889777143716908
  94. 94 269185560043973492627104925775943886460511474095895799264702792496567364232966718581330946033362520987150423616109796018977267974101783395725120588
  95. 95 21868590646710522575376306196835845163627703874936612380112942127936112358819962524964063544760736062068784605451086871991058247731920836280088594093
  96. 96 9722604150628670367920952840243851869752144574920192175842454242836659933315316455275505164709314877332946127497367716802262948371486918844517331299992
  97. 97 134514624713790838117522237983168526353128206046710026992503894482322682927544220520890524415087280044513204826556307876257835681281260055343468180108884
  98. 98 7891571671690193027702010987870833895477168090867558338774877017003475995395873347101104582826800232093849208423297179019398728045912977034512893656643022
  99. 99 270484306588640551267066858018071668446522241930348526384603180718084288838878376094833748032462289784758589052561036656819860987712293960206638066434441959
  100. 100 8390953406129522152705086405803700986055275914442173937223426436997625848378454179961282742174811541771137509117536684015144277866820481888531017827600228113
复制代码

前758项： tn2.tgz (299.55 KB, 下载次数: 0)

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2024-10-5 11:05:26 | 显示全部楼层
和n!相遇的3的幂
前100项为

  2. 0 0
  3. 1 0
  4. 2 3
  5. 3 8
  6. 4 5
  7. 5 805
  8. 6 1689
  9. 7 12317
  10. 8 197209
  11. 9 520852
  12. 10 4493819
  13. 11 16769097
  14. 12 2053077332
  15. 13 1110380591
  16. 14 39230711849
  17. 15 516641987008
  18. 16 62653098988435
  19. 17 398166000236882
  20. 18 7896283077809532
  21. 19 99956735615338266
  22. 20 5161719458617927763
  23. 21 63295038588725505792
  24. 22 659220983938327840981
  25. 23 18741443789015137945475
  26. 24 31407903592822606578249
  27. 25 46391489386483823834469694
  28. 26 3793216881406769379073090682
  29. 27 403605176594753406466859269062
  30. 28 465685673166697291272149831728
  31. 29 36591230974364102878618511096025
  32. 30 810415231911788111377651219003976
  33. 31 18801114953804077033947292115806130
  34. 32 39328579366851028905558779545946232
  35. 33 16573977732210622184389297186647883994
  36. 34 160059870193585417316370516153102559551
  37. 35 14745272543636954468350367390003212959750
  38. 36 115682951803175966028431596897666655500245
  39. 37 180531979575742198149601608824366310410152857
  40. 38 460629689665928219539416868635359283467811142
  41. 39 33196969453444409177231471916326559832651431666
  42. 40 2144035166650676947534220650137976300064223833799
  43. 41 11715255132654033668100148141549338707141145331514
  44. 42 2090526230380314632322241227264225705780343176922628
  45. 43 114904958462862446933186417998257293289587968077410250
  46. 44 2173059229669108761286523270074097052794857878342170304
  47. 45 233593701522132525903038004032943199470238305518768387753
  48. 46 7768291632448544793251458989058065116310856374483710852296
  49. 47 379037471398344443844433928698077675462789902805838760677695
  50. 48 24811687563950017839141782553094703874322229555782284499927662
  51. 49 712495299728146893246075841099139408448991090592441373366917666
  52. 50 15109746472807370045258048795410026788190556222636419351209641710
  53. 51 2225654840662105835959009378858635743998789684349601245114779956939
  54. 52 143864179007603159965228986745297707186564085785666649800068334823278
  55. 53 13637586409915340371667042895064008857373761940045442329115443793359386
  56. 54 167033744822976165000601921813277271842935845496433864699742203969854795
  57. 55 23656671630460039344092428785766813462995643873830249321533081106163992151
  58. 56 695706707693380105860469302846688185865625299848685069395426331180908979941
  59. 57 89102725243109777324443546143798031506754048423800575417427237158929334223916
  60. 58 230779823840900826246905518478675441923538451672788323027435752104009544385821
  61. 59 197803317024213303227520984021673571346522346003403853295578809868777637026022332
  62. 60 8938150288364662660647992563505395743897419367567348646771233175354438557644993202
  63. 61 911577751078110051930236759138908970719357539686526738871823966588522501243904297667
  64. 62 2365422520828887910543844377024633544057049429422996365306705227510815546964115276614081
  65. 63 2728655546518204219662635987300386189450975715441195624837273791348023177627059964275632
  66. 64 594354839179719434022278818214654397244949494968008865315285500344140815369095426545791267
  67. 65 41403057794174165805903019058335441888029514499484653954799116530448926886931061049814626858
  68. 66 1049779121880534872170762664462627916935501846702916691326619812028080824842487369316119453617
  69. 67 30954714881094098984725336648215825191382884222016021245326619185282932935559938807745817240297
  70. 68 5763913093234787880444024582145574974339131124763766746087495334622302710128923487545192557731264
  71. 69 45137454716750167373585891896631678542321592800078342604306701170953229830276815926463995242972148
  72. 70 6480344710757925276626303679576598636552497589619916799420084578473193911487777176766305754525951440
  73. 71 1500870726459501408752140498470234239390585932605018139211816837577542085098927309468998263250543153065
  74. 72 62823124052416818446989138032942505191227617305483657130689948904549109115152728967166221991677048752521
  75. 73 302967108534731055592253050547173946657121443239808857782111205836954041267515053892516418882780610482870
  76. 74 509506184773886581601670975370361836190808751479387000086058534811143316994113800580810077865560232166009776
  77. 75 93318850222267469220378193505738384251511184133416201605588597110010221594959988402335733519105960968970450965
  78. 76 5682929998966352314641557457350684637912082379118815482398091204424236559637184305491673703631404846402130107614
  79. 77 353033490077630841643338107783369682344854188820052543373154806317643779012742044197720694723130001897768657144869
  80. 78 3214782472991747801021065443731585213708166027689636585854831666360236128947234642022735271235912266630680543423054
  81. 79 523847275350268850722599520487365258741822899416995873803158216081250188049699656290143723676977313819417188091079731
  82. 80 57530432739629835039001996096371592441682382193732893431872417112656399870963519116725973128861303665948407101962150757
  83. 81 51927889657769748251572723630769362329950311285227607317590385470043200670305331092591931168837969103498187090582075557570
  84. 82 91963595070847321177761718919549264606338458061239285764543080012032992385565474958890594974577492995948933722386051368936
  85. 83 3816798961783743876125370816230341143813371932727150161373085188530715574959151076293549577446049141166361395837143031983560
  86. 84 1580078228810824325487976173560382965214207832916349367068987243437083305034754873151579208534548026975500867473798985938282735
  87. 85 3454285282637984686108383919640358638929883568630260319966231796329574152003167369975371815148475402966012802931749173950626039177
  88. 86 392871403373372307567062183463316215018949380768203297191021326534665870767782525822308432725337681317402495612035235386939642593061
  89. 87 6825290722437835599175818151143576455805466144451325029150614679717097484773944793386878734841417033212059484704571178409607669660922
  90. 88 321664336579998561447378027785402329331012118116172885608765813568585393966345491065916702760402389569885767793915665461977600073941235
  91. 89 7947233835122249073038674016837816673526544769590892924192961892223754024113169800343078681204290138421210278855199143842164928395808655
  92. 90 871665135887296671720506983347382163614829818900334947235728808279793627581476725031638064421376497253409698585201127004234353057526474623
  93. 91 233361113154750074086172177690587671769239338920951729677601270120059494615373826128051194724154558576770274241537036447570681766293197984160
  94. 92 14735917507660157369463511604234773756874070080275075779251653310575689325885781235557129255749586688176318409752508986830394981994212911964426
  95. 93 1948007075018816163634964917715693321252841642518976086579368562264258445837054750565163390710665434923900935078128816964919909576259263381564109
  96. 94 1032055217475139304091717639388710730145633852449817295981596385291695609908576975079836954748209408779791883548396696174642083741341986334850960717
  97. 95 157256384049801804235230703423272615921727741472255495889584659664653508450517104346149260578736867034679137496542481172226371151505408328700315761049
  98. 96 7408529516803940214014361167024289761860309016320549716885231857699666741872336078922754025184958000195858374394721947512924014963517235217743892450371
  99. 97 35418864772624409717121359595244523254938804569860189272786621965978409552254691422394896257738584991370520076355904254437190582114122139099240349071561
  100. 98 17277149481381292946889861261816988781831488916660464594210937353769504382013928456671038156262032520744219307554681653645644743021063486728513918070387989
  101. 99 1360504394176668762907257522052066949072305299823153672276636871574947829496177682710046804961987683754846803440285368766671671884854705180410007537869998301
  102. 100 136045541320034945436593508900132950237115671079795689880103371118620175782324164981176046207558000520681214904948391234424942406863056709490808136956113029022
复制代码


前1000项: tn3.tgz (545.67 KB, 下载次数: 0)

评分

参与人数 2威望 +16 金币 +16 贡献 +16 经验 +16 鲜花 +16 收起 理由
王守恩 + 8 + 8 + 8 + 8 + 8 赞一个!
northwolves + 8 + 8 + 8 + 8 + 8 很给力!

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2024-10-23 12:02:50 | 显示全部楼层
northwolves 发表于 2024-10-4 22:10
{1,5}
{2,98}
{3,872}

你是怎么计算的？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

nyy
发表于 2024-10-23 12:04:08 | 显示全部楼层
我居然没看懂
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 5 天前 | 显示全部楼层
花了点时间，写了python代码。不过，我不能讲明白算法原理。主要是，不能证明我的这个算法为什么不会漏掉某些解。但是，这个代码的计算结果和楼主给出的结果完全一致，从侧面说明了我的算法的有很高的可信度。或许以后，我的这个算法被证明或者证伪。下面是源代码。今年了python比较火，这是我第一次写数值计算的Python程序。


  2. #!/usr/bin/python3
  3. # -*- coding: utf-8 -*-

  5. import mpmath
  6. from mpmath import mpf,exp,log,floor,pi

  8. # 全局变量，常数
  9. log10_2 = mpf(0) # will calc later

  11. # 令 a* 10^d =2^n, (1<=a<10), 已知n，d,求a
  12. def calc_a( n, d ):
  13.     global log10_2
  14.    
  15.     # 令 a* 10^d = 2^n, (1<=a<10),  
  16.     # 两边取常用对数，
  17.     # log10(a) + d = n*log10(2)
  18.     # d = n*log10(2) - log10(a) = floor(n*log10(2))
  19.     c2  = mpf(2)
  20.     c10 = mpf(10)
  21.     v_2pn = c2 ** n                # 2^n
  22.     d= mpmath.floor(n*log10_2)
  23.     a  = v_2pn  / (c10 ** d)
  24.     return a

  26. # 令 2^n = a*10^d , (0.1< a <= 1.0), 已知n，d,求a
  27. def calc_a1( n, d ):
  28.     c2 = mpf(2)
  29.     c10 = mpf(10)
  30.     a = (c2 ** n) / (c10 ** d)
  31.     return a
  32.    
  33. def search_in_interval( base, pi_lo, pi_hi ,layer=0):
  34.    
  35.     (n,d) = base
  36.     a= calc_a(n,d )
  37.     esp= (10 ** (-mpmath.mp.dps)) * mpf("4.0")  # 精度误差
  38.    
  39.     if a>= pi_lo and a < (pi_hi-esp):
  40.         return base
  41.         
  42.     low  = pi_lo / a   # 放大倍数的下界
  43.     high = pi_hi / a   # 放大倍数的下界
  44.     #print(f"\n2^{n} = {a} * 10^{d}")
  45.     l_lo=log(low);     l_hi=log(high)    # 取对数，方便计算，乘除变加减
  46.       
  47.     # 定义一个区间 (start, end)  c0
  48.     # 因为 2^3= 0.8 * 10^1, 2^4=1.6*10^1, 所以
  49.     # begin=(3,1,0.8),  end=(4,1,1.6)
  50.     begin=(mpf(3),mpf(1),log(mpf("0.8")))
  51.     end  =(mpf(4),mpf(1),log(mpf("1.6")))
  52.    
  53.     iter_count=0
  54.     c0  = mpf(0)
  55.     while True:
  56.         (n0,d0,v0)=begin ; (n1,d1,v1)=end
  57.         
  58.         #print(f"v0:{v0}, v1:{v1}, mid_v:{mid_v}")
  59.         l_m = v0 + v1       # l_m=log(mid)
  60.         mid = (n0+n1,d0+d1,l_m)
  61.         
  62.         if l_m < l_lo and l_m < c0 :
  63.             begin = mid    # mid总是大于begin, begin 不断增大，但 begin.v0始终<=0
  64.         elif l_m > l_hi and l_m > c0 :
  65.             end = mid      # mid总是小于end,  end 不断减小，但end.v始终>=0
  66.         else:
  67.             break
  68.         iter_count +=1
  69.     #end while
  70.    
  71.     (n0,d0,v0)=begin;  (n1,d1,v1)=end
  72.     l_m = v0 + v1
  73.     if l_m >= l_lo and l_m<l_hi:
  74.        (n,d)  = base
  75.        #print("layer:", layer, ",get an result:", n+(n0+n1))
  76.        return ( n+(n0+n1),d+(d0+d1))      
  77.    
  78.     if n0<n1:
  79.         base = (n+n0,d+d0)
  80.     else:
  81.         base = (n+n1,d+d1)
  82.     return search_in_interval( base, pi_lo, pi_hi,layer+1 ) # 递归调用   
  83.    
  84. #end search_in_interval

  86. def question_19684(MAX_N,debug=False ):

  88.     r0= (mpf(5.0), mpf(1.0) ) # 2^5/10^1=3.2
  89.     print(1, 5)
  90.     results=[r0]  
  91.    
  92.     c10 = mpf(10)
  93.     for i in range(2, MAX_N+1):
  94.         v_10p_i  = c10 ** (i-1)       # 10^(i-1)
  95.         tmp      = floor(pi * v_10p_i)
  96.         pi_lo    = tmp/v_10p_i          # 圆周率的下界
  97.         pi_hi   = (tmp+1)/v_10p_i       # 圆周率的上界
  98.       
  99.         if debug:
  100.             print(f"\n{i}:pi_lo={pi_lo},pi_hi = {pi_hi}")

  102.         base = results[-1]
  103.         res = search_in_interval(base, pi_lo, pi_hi )
  104.         (n,d)=res      # 2^n/10^d是一个非常接近于1.0的数
  105.         
  106.         a=calc_a(n,d)
  107.         if debug:
  108.             print(f"2^{n} = {a} * 10^{d}")
  109.         s=str(n)
  110.         if s.endswith(".0"):
  111.             s=s[:-2]
  112.         print(i, s)
  113.         results.append((n,d))
  114.     #end for

  116. def main():
  117.     global log10_2
  118.    
  119.     MAX_N=1000
  120.     mpmath.mp.dps = (MAX_N*2)+16
  121.    
  122.     c2 = mpf(2)
  123.     c10 = mpf(10)
  124.     log10_2 = log(c2)/log(c10)
  125.    
  126.     #question_19684(MAX_N,True)
  127.     question_19684(MAX_N,False)
  128.    
  129. main()   
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 5 天前 | 显示全部楼层
核心部分类似于二分查找。基本原理是，若a<1.0（ 但非常接近于1），b>1.0（也非常接近于1）,那么， a*b 的值 介于 a与b之间（a*b的值更加接近于1）
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-21 15:40 , Processed in 0.034528 second(s), 21 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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