% EPRIMES - locate the first "n-digit" primes in consecutive
% digits of e (where n varies from 1 to 500).
%
%
% Notes: Recently, Google Inc. created a few highway billboard signs
% asking passersby to find the first ten-digit prime within
% consecutive digits of e. Certainly the Mathworks File Exchange
% must address such a challenge!
%
% Unfortunately, the answer to the Google billboard question was
% quickly published in the media, so the answer is readily available.
% Nevertheless, if you wish to solve the problem yourself, please feel
% free to ignore those publications and this program.
%
% The program has an arbitrary stoping point at 500 digits. Also,
% to save space there are only 10,000 stored digits of e, so there is
% a limit (much larger than 500) to how large your desired prime can
% be using this code.
%
% Probable prime calculations are employed using Java.
% (See notes under the function ISPR.M, submitted previously.)
%
% Michael Kleder, September 2004
function eprimes
ex = getex;
disp('Primes hidden in e:')
tic
for numdigs=1:500
loc = 1;
n=ex(loc:loc+numdigs-1);
flag=1;
while flag
if ispr(n)
disp(['The first ' num2str(length(n)) '-digit prime starts at digit ' num2str(loc) ...
' and took ' num2str(toc,4) ' seconds to find:'])
tic
disp(n)
flag=0;
else
loc = loc + 1;
n=ex(loc:loc+numdigs-1);
qq=0;
while n(1) == 48 % first digit is zero
qq=qq+1;
n = ex(loc+qq:loc+qq+numdigs-1);
end
end
end
end
return
% ISPR - Rapidly determine whether an arbitrarily large positive integer
% is a probable prime.
%
% USAGE: q = ispr(n)
% q = ispn(n,1)
%
% n = positive integer, either as a numeric or string datatype
% q = 1 if n is prime, 0 if n is composite
% 1 = any second input will cause the function to output
% a message describing the result in plain language,
% including (if n is probably prime) a statement about
% the certainty with which n is claimed to be prime.
%
% Notes: Probable primes are also known as "industrial strength"
% primes because of the exceedingly high probability -- but
% not certainty -- of primality. This function utilizes the
% Java class "BigInteger" with its method "isProbablePrime."
% For small integers, you can use numeric inputs; however,
% for abitrarily large integers, you must input the number
% as a string in order to avoid an overflow. Note the overflow
% error in the second to last example below.
%
% Examples:
%
% >>ispr(314159,1)
% I believe that 314159 is prime, but there is a
% 1 in 590295810358705650000 chance that I am mistaken.
%
% >>ispr('338327950288419716939',1) % correct with quotes
% I believe that 338327950288419716939 is prime, but there
% is a 1 in 664613997892457940000000000000000000 chance
% that I am mistaken.
%
% >>ispr(338327950288419716939,1) % no quotes, therefore overflow
% 338327950288419680000 is definitely not prime.
%
% >> for i=1:1000;if ispr(i);fprintf('%i ',i);end;end;fprintf('\n')
%
% Michael Kleder, 2004
function q=ispr(varargin)
n = varargin{1};
if isnumeric(n)
n = num2str(n);
end
if n(end)==46 % strip trailing decimal point
n=n(1:end-1);
end
% check for positive integers:
if strcmp(n,'0') | any(n==45) | any(n==46)
error('Input must be a positive integer.')
end
x=java.math.BigInteger(n);
% create "industrial-strength" certainty:
certfactor = ceil(3.33*length(n))+50;
q=x.isProbablePrime(certfactor);
if nargin > 1
% code to display the result, if you want it:
if q
wrong = 2 ^ certfactor;
disp(['I believe that ' n ' is prime, but there is a 1 in ' ...
num2str(wrong) ' chance that I am mistaken.']);
else
disp([n ' is definitely not prime.']);
end
end
return
function ex = getex
ex = ['27182818284590452353602874713526624977572470936999'...
'59574966967627724076630353547594571382178525166427'...
'42746639193200305992181741359662904357290033429526'...
'05956307381323286279434907632338298807531952510190'...
'11573834187930702154089149934884167509244761460668'...
'08226480016847741185374234544243710753907774499206'...
'95517027618386062613313845830007520449338265602976'...
'06737113200709328709127443747047230696977209310141'...
'69283681902551510865746377211125238978442505695369'...
'67707854499699679468644549059879316368892300987931'...
'27736178215424999229576351482208269895193668033182'...
'52886939849646510582093923982948879332036250944311'...
'73012381970684161403970198376793206832823764648042'...
'95311802328782509819455815301756717361332069811250'...
'99618188159304169035159888851934580727386673858942'...
'28792284998920868058257492796104841984443634632449'...
'68487560233624827041978623209002160990235304369941'...
'84914631409343173814364054625315209618369088870701'...
'67683964243781405927145635490613031072085103837505'...
'10115747704171898610687396965521267154688957035035'...
'40212340784981933432106817012100562788023519303322'...
'47450158539047304199577770935036604169973297250886'...
'87696640355570716226844716256079882651787134195124'...
'66520103059212366771943252786753985589448969709640'...
'97545918569563802363701621120477427228364896134225'...
'16445078182442352948636372141740238893441247963574'...
'37026375529444833799801612549227850925778256209262'...
'26483262779333865664816277251640191059004916449982'...
'89315056604725802778631864155195653244258698294695'...
'93080191529872117255634754639644791014590409058629'...
'84967912874068705048958586717479854667757573205681'...
'28845920541334053922000113786300945560688166740016'...
'98420558040336379537645203040243225661352783695117'...
'78838638744396625322498506549958862342818997077332'...
'76171783928034946501434558897071942586398772754710'...
'96295374152111513683506275260232648472870392076431'...
'00595841166120545297030236472549296669381151373227'...
'53645098889031360205724817658511806303644281231496'...
'55070475102544650117272115551948668508003685322818'...
'31521960037356252794495158284188294787610852639813'...
'95599006737648292244375287184624578036192981971399'...
'14756448826260390338144182326251509748279877799643'...
'73089970388867782271383605772978824125611907176639'...
'46507063304527954661855096666185664709711344474016'...
'07046262156807174818778443714369882185596709591025'...
'96862002353718588748569652200050311734392073211390'...
'80329363447972735595527734907178379342163701205005'...
'45132638354400018632399149070547977805669785335804'...
'89669062951194324730995876552368128590413832411607'...
'22602998330535370876138939639177957454016137223618'...
'78936526053815584158718692553860616477983402543512'...
'84396129460352913325942794904337299085731580290958'...
'63138268329147711639633709240031689458636060645845'...
'92512699465572483918656420975268508230754425459937'...
'69170419777800853627309417101634349076964237222943'...
'52366125572508814779223151974778060569672538017180'...
'77636034624592787784658506560507808442115296975218'...
'90874019660906651803516501792504619501366585436632'...
'71254963990854914420001457476081930221206602433009'...
'64127048943903971771951806990869986066365832322787'...
'09376502260149291011517177635944602023249300280401'...
'86772391028809786660565118326004368850881715723866'...
'98422422010249505518816948032210025154264946398128'...
'73677658927688163598312477886520141174110913601164'...
'99507662907794364600585194199856016264790761532103'...
'87275571269925182756879893027617611461625493564959'...
'03798045838182323368612016243736569846703785853305'...
'27583333793990752166069238053369887956513728559388'...
'34998947074161815501253970646481719467083481972144'...
'88898790676503795903669672494992545279033729636162'...
'65897603949857674139735944102374432970935547798262'...
'96145914429364514286171585873397467918975712119561'...
'87385783644758448423555581050025611492391518893099'...
'46342841393608038309166281881150371528496705974162'...
'56282360921680751501777253874025642534708790891372'...
'91722828611515915683725241630772254406337875931059'...
'82676094420326192428531701878177296023541306067213'...
'60460003896610936470951414171857770141806064436368'...
'15464440053316087783143174440811949422975599314011'...
'88868331483280270655383300469329011574414756313999'...
'72217038046170928945790962716622607407187499753592'...
'12756084414737823303270330168237193648002173285734'...
'93594756433412994302485023573221459784328264142168'...
'48787216733670106150942434569844018733128101079451'...
'27223737886126058165668053714396127888732527373890'...
'39289050686532413806279602593038772769778379286840'...
'93253658807339884572187460210053114833513238500478'...
'27169376218004904795597959290591655470505777514308'...
'17511269898518840871856402603530558373783242292418'...
'56256442550226721559802740126179719280471396006891'...
'63828665277009752767069777036439260224372841840883'...
'25184877047263844037953016690546593746161932384036'...
'38931313643271376888410268112198912752230562567562'...
'54701725086349765367288605966752740868627407912856'...
'57699631378975303466061666980421826772456053066077'...
'38996242183408598820718646826232150802882863597468'...
'39654358856685503773131296587975810501214916207656'...
'76995065971534476347032085321560367482860837865680'...
'30730626576334697742956346437167093971930608769634'...
'95328846833613038829431040800296873869117066666146'...
'80001512114344225602387447432525076938707777519329'...
'99421372772112588436087158348356269616619805725266'...
'12206797540621062080649882918454395301529982092503'...
'00549825704339055357016865312052649561485724925738'...
'62069174036952135337325316663454665885972866594511'...
'36441370331393672118569553952108458407244323835586'...
'06310680696492485123263269951460359603729725319836'...
'84233639046321367101161928217111502828016044880588'...
'02382031981493096369596735832742024988245684941273'...
'86056649135252670604623445054922758115170931492187'...
'95927180019409688669868370373022004753143381810927'...
'08030017205935530520700706072233999463990571311587'...
'09963577735902719628506114651483752620956534671329'...
'00259943976631145459026858989791158370934193704411'...
'55121920117164880566945938131183843765620627846310'...
'49034629395002945834116482411496975832601180073169'...
'94373935069662957124102732391387417549230718624545'...
'43222039552735295240245903805744502892246886285336'...
'54221381572213116328811205214648980518009202471939'...
'17105553901139433166815158288436876069611025051710'...
'07392762385553386272553538830960671644662370922646'...
'80967125406186950214317621166814009759528149390722'...
'26011126811531083873176173232352636058381731510345'...
'95736538223534992935822836851007810884634349983518'...
'40445170427018938199424341009057537625776757111809'...
'00881641833192019626234162881665213747173254777277'...
'83488774366518828752156685719506371936565390389449'...
'36642176400312152787022236646363575550356557694888'...
'65495002708539236171055021311474137441061344455441'...
'92101336172996285694899193369184729478580729156088'...
'51039678195942983318648075608367955149663644896559'...
'29481878517840387733262470519450504198477420141839'...
'47731202815886845707290544057510601285258056594703'...
'04683634459265255213700806875200959345360731622611'...
'87281739280746230946853678231060979215993600199462'...
'37993434210687813497346959246469752506246958616909'...
'17857397659519939299399556754271465491045686070209'...
'90126068187049841780791739240719459963230602547079'...
'01774527513186809982284730860766536866855516467702'...
'91133682756310722334672611370549079536583453863719'...
'62358563126183871567741187385277229225947433737856'...
'95538456246801013905727871016512966636764451872465'...
'65373040244368414081448873295784734849000301947788'...
'80204603246608428753518483649591950828883232065221'...
'28104190448047247949291342284951970022601310430062'...
'41071797150279343326340799596053144605323048852897'...
'29176598760166678119379323724538572096075822771784'...
'83361613582612896226118129455927462767137794487586'...
'75365754486140761193112595851265575973457301533364'...
'26307679854433857617153334623252705720053039882894'...
'99034259566232975782488735029259166825894456894655'...
'99265845476269452878051650172067478541788798227680'...
'65366506419109734345288783386217261562695826544782'...
'05672987756426325321594294418039943217000090542650'...
'76309558846589517170914760743713689331946909098190'...
'45012903070995662266203031826493657336984195557769'...
'63787624918852865686607600566025605445711337286840'...
'20557441603083705231224258722343885412317948138855'...
'00756893811249353863186352870837998456926199817945'...
'23364087429591180747453419551420351726184200845509'...
'17084568236820089773945584267921427347756087964427'...
'92027083121501564063413416171664480698154837644915'...
'73900121217041547872591998943825364950514771379399'...
'14720521952907939613762110723849429061635760459623'...
'12535060685376514231153496656837151166042207963944'...
'66621163255157729070978473156278277598788136491951'...
'25748332879377157145909106484164267830994972367442'...
'01758622694021594079244805412553604313179926967391'...
'57542419296607312393763542139230617876753958711436'...
'10408940996608947141834069836299367536262154524729'...
'84642137528910798843813060955526227208375186298370'...
'66787224430195793793786072107254277289071732854874'...
'37435578196651171661833088112912024520404868220007'...
'23440350254482028342541878846536025915064452716577'...
'00044521097735585897622655484941621714989532383421'...
'60011406295071849042778925855274303522139683567901'...
'80764060421383073087744601708426882722611771808426'...
'64333651780002171903449234264266292261456004337383'...
'86833555534345300426481847398921562708609565062934'...
'04052649432442614456659212912256488935696550091543'...
'06426134252668472594914314239398845432486327461842'...
'84665598533231221046625989014171210344608427161661'...
'90012571958707932175696985440133976220967494541854'...
'07118446433946990162698351607848924514058940946395'...
'26780735457970030705116368251948770118976400282764'...
'84141605872061841852971891540196882532893091496653'...
'45753571427318482016384644832499037886069008072709'...
'32767312758196656394114896171683298045513972950668'...
'76047409154204284299935410258291135022416907694316'...
'68574242522509026939034814856451303069925199590436'...
'38402842926741257342244776558417788617173726546208'...
'54982944989467873509295816526320722589923687684570'...
'17823038096567883112289305809140572610865884845873'...
'10165815116753332767488701482916741970151255978257'...
'27074064318086014281490241467804723275976842696339'...
'35773542930186739439716388611764209004068663398856'...
'84168100387238921448317607011668450388721236436704'...
'33140911557332801829779887365909166596124020217785'...
'58854876176161989370794380056663364884365089144805'...
'57103976521469602766258359905198704230017946553678'];
return
