Primes In the Decimal Expansion of p

Letting pk denote the integer given by the k most significant decimal digits of p, it's not too difficult to determine that pk is prime for k = 1, 2, 6, and 38. In other words, the following integers are primes

p1 = 3

p2 = 31

p6 = 314159

p38 = 31415926535897932384626433832795028841

Maple's probabilistic primality test shows that pk is composite for every other value of k from 1 to 500. A deterministic test of primality for numbers of more than 500 digits is fairly challenging, so it will be difficult to rigorously prove the primality of any further terms in this sequence.

It's interesting to consider the "expected number" of primes in this list. Just based on the density of primes, pk has a probability of being prime approaching 1/(k ln(10)). On this basis, the expected number of primes of the form pk for k less than x is approximately

For x = 500 the expected number of primes is just about 3, whereas we actually have 4. If this formula is anywhere near correct it suggests two things: (1) there are infinitely many primes of the form pk, and (2) we may never know (deterministically) the next prime beyond p38. This is because even to achieve an expected value of 4 requires over x = 5000 digits, which I believe is well beyond the range of practical deterministic primality testing for general numbers (unlike, for instance, Mersenne primes). Here I'm assuming there is no special structure in the decimal expansion of p that could be exploited to test for primality. Of course, we might find another prime pk for some unexpectedly low value of k, but I would venture to say that we will never find two more.

Update: In Dec 2001, Ed T. Prothro reported discovering the next (probable) prime in the decimal digits of p. This took 4.5 months of computation on a 1000 MHz Pentium 3 with Maple running in the background. The probable prime has 16,208 digits:

p16208 =

3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
9821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819
6442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127
3724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609
4330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491
2983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513
2000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923
5420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185
9502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730
3598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198
9380952572010654858632788659361533818279682303019520353018529689957736225994138912497217752834791315
1557485724245415069595082953311686172785588907509838175463746493931925506040092770167113900984882401
2858361603563707660104710181942955596198946767837449448255379774726847104047534646208046684259069491
2933136770289891521047521620569660240580381501935112533824300355876402474964732639141992726042699227
9678235478163600934172164121992458631503028618297455570674983850549458858692699569092721079750930295
5321165344987202755960236480665499119881834797753566369807426542527862551818417574672890977772793800
0816470600161452491921732172147723501414419735685481613611573525521334757418494684385233239073941433
3454776241686251898356948556209921922218427255025425688767179049460165346680498862723279178608578438
3827967976681454100953883786360950680064225125205117392984896084128488626945604241965285022210661186
3067442786220391949450471237137869609563643719172874677646575739624138908658326459958133904780275900
9946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745530506820
3496252451749399651431429809190659250937221696461515709858387410597885959772975498930161753928468138
2686838689427741559918559252459539594310499725246808459872736446958486538367362226260991246080512438
8439045124413654976278079771569143599770012961608944169486855584840635342207222582848864815845602850
6016842739452267467678895252138522549954666727823986456596116354886230577456498035593634568174324112
5150760694794510965960940252288797108931456691368672287489405601015033086179286809208747609178249385
8900971490967598526136554978189312978482168299894872265880485756401427047755513237964145152374623436
4542858444795265867821051141354735739523113427166102135969536231442952484937187110145765403590279934
4037420073105785390621983874478084784896833214457138687519435064302184531910484810053706146806749192
7819119793995206141966342875444064374512371819217999839101591956181467514269123974894090718649423196
1567945208095146550225231603881930142093762137855956638937787083039069792077346722182562599661501421
5030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539057962685
6100550810665879699816357473638405257145910289706414011097120628043903975951567715770042033786993600
7230558763176359421873125147120532928191826186125867321579198414848829164470609575270695722091756711
6722910981690915280173506712748583222871835209353965725121083579151369882091444210067510334671103141
2671113699086585163983150197016515116851714376576183515565088490998985998238734552833163550764791853
5893226185489632132933089857064204675259070915481416549859461637180270981994309924488957571282890592
3233260972997120844335732654893823911932597463667305836041428138830320382490375898524374417029132765
6180937734440307074692112019130203303801976211011004492932151608424448596376698389522868478312355265
8213144957685726243344189303968642624341077322697802807318915441101044682325271620105265227211166039
6665573092547110557853763466820653109896526918620564769312570586356620185581007293606598764861179104
5334885034611365768675324944166803962657978771855608455296541266540853061434443185867697514566140680
0700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797270826683
0634328587856983052358089330657574067954571637752542021149557615814002501262285941302164715509792592
3099079654737612551765675135751782966645477917450112996148903046399471329621073404375189573596145890
1938971311179042978285647503203198691514028708085990480109412147221317947647772622414254854540332157
1853061422881375850430633217518297986622371721591607716692547487389866549494501146540628433663937900
3976926567214638530673609657120918076383271664162748888007869256029022847210403172118608204190004229
6617119637792133757511495950156604963186294726547364252308177036751590673502350728354056704038674351
3622224771589150495309844489333096340878076932599397805419341447377441842631298608099888687413260472
1569516239658645730216315981931951673538129741677294786724229246543668009806769282382806899640048243
5403701416314965897940924323789690706977942236250822168895738379862300159377647165122893578601588161
7557829735233446042815126272037343146531977774160319906655418763979293344195215413418994854447345673
8316249934191318148092777710386387734317720754565453220777092120190516609628049092636019759882816133
2316663652861932668633606273567630354477628035045077723554710585954870279081435624014517180624643626
7945612753181340783303362542327839449753824372058353114771199260638133467768796959703098339130771098
7040859133746414428227726346594704745878477872019277152807317679077071572134447306057007334924369311
3835049316312840425121925651798069411352801314701304781643788518529092854520116583934196562134914341
5956258658655705526904965209858033850722426482939728584783163057777560688876446248246857926039535277
3480304802900587607582510474709164396136267604492562742042083208566119062545433721315359584506877246
0290161876679524061634252257719542916299193064553779914037340432875262888963995879475729174642635745
5254079091451357111369410911939325191076020825202618798531887705842972591677813149699009019211697173
7278476847268608490033770242429165130050051683233643503895170298939223345172201381280696501178440874
5196012122859937162313017114448464090389064495444006198690754851602632750529834918740786680881833851
0228334508504860825039302133219715518430635455007668282949304137765527939751754613953984683393638304
7461199665385815384205685338621867252334028308711232827892125077126294632295639898989358211674562701
0218356462201349671518819097303811980049734072396103685406643193950979019069963955245300545058068550
1956730229219139339185680344903982059551002263535361920419947455385938102343955449597783779023742161
7271117236434354394782218185286240851400666044332588856986705431547069657474585503323233421073015459
4051655379068662733379958511562578432298827372319898757141595781119635833005940873068121602876496286
7446047746491599505497374256269010490377819868359381465741268049256487985561453723478673303904688383
4363465537949864192705638729317487233208376011230299113679386270894387993620162951541337142489283072
2012690147546684765357616477379467520049075715552781965362132392640616013635815590742202020318727760
5277219005561484255518792530343513984425322341576233610642506390497500865627109535919465897514131034
8227693062474353632569160781547818115284366795706110861533150445212747392454494542368288606134084148
6377670096120715124914043027253860764823634143346235189757664521641376796903149501910857598442391986
2916421939949072362346468441173940326591840443780513338945257423995082965912285085558215725031071257
0126683024029295252201187267675622041542051618416348475651699981161410100299607838690929160302884002
6910414079288621507842451670908700069928212066041837180653556725253256753286129104248776182582976515
7959847035622262934860034158722980534989650226291748788202734209222245339856264766914905562842503912
7577102840279980663658254889264880254566101729670266407655904290994568150652653053718294127033693137
8517860904070866711496558343434769338578171138645587367812301458768712660348913909562009939361031029
1616152881384379099042317473363948045759314931405297634757481193567091101377517210080315590248530906
6920376719220332290943346768514221447737939375170344366199104033751117354719185504644902636551281622
8824462575916333039107225383742182140883508657391771509682887478265699599574490661758344137522397096
8340800535598491754173818839994469748676265516582765848358845314277568790029095170283529716344562129
6404352311760066510124120065975585127617858382920419748442360800719304576189323492292796501987518721
2726750798125547095890455635792122103334669749923563025494780249011419521238281530911407907386025152
2742995818072471625916685451333123948049470791191532673430282441860414263639548000448002670496248201
7928964766975831832713142517029692348896276684403232609275249603579964692565049368183609003238092934
5958897069536534940603402166544375589004563288225054525564056448246515187547119621844396582533754388
5690941130315095261793780029741207665147939425902989695946995565761218656196733786236256125216320862
8692221032748892186543648022967807057656151446320469279068212073883778142335628236089632080682224680
1224826117718589638140918390367367222088832151375560037279839400415297002878307667094447456013455641
7254370906979396122571429894671543578468788614445812314593571984922528471605049221242470141214780573
4551050080190869960330276347870810817545011930714122339086639383395294257869050764310063835198343893
4159613185434754649556978103829309716465143840700707360411237359984345225161050702705623526601276484
8308407611830130527932054274628654036036745328651057065874882256981579367897669742205750596834408697
3502014102067235850200724522563265134105592401902742162484391403599895353945909440704691209140938700
1264560016237428802109276457931065792295524988727584610126483699989225695968815920560010165525637567
8566722796619885782794848855834397518744545512965634434803966420557982936804352202770984294232533022
5763418070394769941597915945300697521482933665556615678736400536665641654732170439035213295435291694
1459904160875320186837937023488868947915107163785290234529244077365949563051007421087142613497459561
5138498713757047101787957310422969066670214498637464595280824369445789772330048764765241339075920434
0196340391147320233807150952220106825634274716460243354400515212669324934196739770415956837535551667
3027390074972973635496453328886984406119649616277344951827369558822075735517665158985519098666539354
9481068873206859907540792342402300925900701731960362254756478940647548346647760411463233905651343306
8449539790709030234604614709616968868850140834704054607429586991382966824681857103188790652870366508
3243197440477185567893482308943106828702722809736248093996270607472645539925399442808113736943388729
4063079261595995462624629707062594845569034711972996409089418059534393251236235508134949004364278527
1383159125689892951964272875739469142725343669415323610045373048819855170659412173524625895487301676
0029886592578662856124966552353382942878542534048308330701653722856355915253478445981831341129001999
2059813522051173365856407826484942764411376393866924803118364453698589175442647399882284621844900877
7697763127957226726555625962825427653183001340709223343657791601280931794017185985999338492354956400
5709955856113498025249906698423301735035804408116855265311709957089942732870925848789443646005041089
2266917835258707859512983441729535195378855345737426085902908176515578039059464087350612322611200937
3108048548526357228257682034160504846627750450031262008007998049254853469414697751649327095049346393
8243222718851597405470214828971117779237612257887347718819682546298126868581705074027255026332904497
6277894423621674119186269439650671515779586756482399391760426017633870454990176143641204692182370764
8878341968968611815581587360629386038101712158552726683008238340465647588040513808016336388742163714
0643549556186896411228214075330265510042410489678352858829024367090488711819090949453314421828766181
0310073547705498159680772009474696134360928614849417850171807793068108546900094458995279424398139213
5055864221964834915126390128038320010977386806628779239718014613432445726400973742570073592100315415
0893679300816998053652027600727749674584002836240534603726341655425902760183484030681138185510597970
5664007509426087885735796037324514146786703688098806097164258497595138069309449401515422221943291302
1739125383559150310033303251117491569691745027149433151558854039221640972291011290355218157628232831
8234254832611191280092825256190205263016391147724733148573910777587442538761174657867116941477642144
1111263583553871361011023267987756410246824032264834641766369806637857681349204530224081972785647198
3963087815432211669122464159117767322532643356861461865452226812688726844596844241610785401676814208
0885028005414361314623082102594173756238994207571362751674573189189456283525704413354375857534269869
9472547031656613991999682628247270641336222178923903176085428943733935618891651250424404008952719837
8738648058472689546243882343751788520143956005710481194988423906061369573423155907967034614914344788
6360410318235073650277859089757827273130504889398900992391350337325085598265586708924261242947367019
3907727130706869170926462548423240748550366080136046689511840093668609546325002145852930950000907151
0582362672932645373821049387249966993394246855164832611341461106802674466373343753407642940266829738
6522093570162638464852851490362932019919968828517183953669134522244470804592396602817156551565666111
3598231122506289058549145097157553900243931535190902107119457300243880176615035270862602537881797519
4780610137150044899172100222013350131060163915415895780371177927752259787428919179155224171895853616
8059474123419339842021874564925644346239253195313510331147639491199507285843065836193536932969928983
7914941939406085724863968836903265564364216644257607914710869984315733749648835292769328220762947282
3815374099615455987982598910937171262182830258481123890119682214294576675807186538065064870261338928
2299497257453033283896381843944770779402284359883410035838542389735424395647555684095224844554139239
4100016207693636846776413017819659379971557468541946334893748439129742391433659360410035234377706588
8677811394986164787471407932638587386247328896456435987746676384794665040741118256583788784548581489
6296127399841344272608606187245545236064315371011274680977870446409475828034876975894832824123929296
0582948619196670918958089833201210318430340128495116203534280144127617285830243559830032042024512072
8725355811958401491809692533950757784000674655260314461670508276827722235341911026341631571474061238
5042584598841990761128725805911393568960143166828317632356732541707342081733223046298799280490851409
4790368878687894930546955703072619009502076433493359106024545086453628935456862958531315337183868265
6178622736371697577418302398600659148161640494496501173213138957470620884748023653710311508984279927
5442685327797431139514357417221975979935968525228574526379628961269157235798662057340837576687388426
6405990993505000813375432454635967504844235284874701443545419576258473564216198134073468541117668831
1865448937769795665172796623267148103386439137518659467300244345005449953997423723287124948347060440
6347160632583064982979551010954183623503030945309733583446283947630477564501500850757894954893139394
4899216125525597701436858943585877526379625597081677643800125436502371412783467926101995585224717220
1777237004178084194239487254068015560359983905489857235467456423905858502167190313952629445543913166
3134530893906204678438778505423939052473136201294769187497519101147231528932677253391814660730008902
7768963114810902209724520759167297007850580717186381054967973100167870850694207092232908070383263453
4520380278609905569001341371823683709919495164896007550493412678764367463849020639640197666855923356
5463913836318574569814719621084108096188460545603903845534372914144651347494078488442377217515433426
0306698831768331001133108690421939031080143784334151370924353013677631084913516156422698475074303297
1674696406665315270353254671126675224605511995818319637637076179919192035795820075956053023462677579
43936307

Prothro has determined that this number passes the "strong-pseudoprime" test, which means it is almost certainly a prime (although this is not a deterministic proof). In the course of his search he verified that all the numbers from p500 to p16207 are composite.

Based on the probabilistic formula given above, the expected number of primes in the sequence p1, p2... pk reaches 5 for k = 56146, so finding the 5th prime at k = 16208 is a bit earlier than expected, but not much. (The expectation at k=16208 is for 4.46 primes, so it isn't too improbable for the 5th prime to occur at this point.) Using the same formula, the expected number of primes reaches six at k = 561460 digits, so it would be fairly challenging to find the next probable prime in the sequence.

Return to MathPages Main Menu

Сайт управляется системой uCoz