; TeX output 2006.07.07:1858 KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ:9|&html: html:.MTvkcolor push Black color popZVg5PSfile=logo129.eps llx=0 lly=0 urx=99 ury=16 rwi=2880<䍍
color push Black color popkN q cmbx12Asymptotically
ExactHeuristicsforPrime\3rDivisors
oftheSequence!", q
cmsy10fg q cmmi12ay?g ff cmmi12kDt q G cmr17+by?kQgy?!", ff
cmsy101
Q{k{XQ ff cmr12=1.s獒 GPieter/Moreecolor push rgb 0 .5 0html:=K`y
cmr101 html: color pop aKorteweg-de/V4riesInstituut dPlantage/Muidergracht24 1018/TVAmsterdam VYThe/Netherlands +html:color push cmyk 0 1 0 00߆T ff cmtt12moree@science.uva.nl html: color pop#N vcolor push Black color pop r2"V
3
cmbx10AbstractÍcolor push Black color pop_1K`y
3
cmr10Let5b>
3
cmmi10NȮ62 cmmi8a;b(x)coun!tthenumbMerofprimesp
8!",
3
cmsy10xwithpdividingaks]+Obkhforsomekb
1.
_Itiskno!wnthatNȮa;b(x)
c(a;1b)x=log/xforsomerationalnumbMerc(a;1b)thatdepends_in%@aratherin!tricatewayonaandb.A%simpleheuristicformulaforNȮa;b(x)ispropMosed_andlHitispro!vedlHthatitisasymptoticallyexact,wi.e.,haslHthesameasymptoticbMeha!vior_asfNȮa;b(x).ConnectionswithRaman!ujansumsandcharactersumsarediscussed.=html: html:HN G cmbx12H1(Inutro =ductionb#XQ cmr12Let
g cmmi12pbSeaprime(indeed,throughoutthisnotetheletterpwillbeusedtoindicateprimes). LetSgbSeanon-zerorationalnrumber. nBySp](gn9)wredenotetheexponenrtofpinthecanonicalfactorizationofgn9.[Ifp](g)=0,thenbryordg(p)wedenotethesmallestpSositiveintegerksucrhathatgn92k!",
cmsy10UR1(moSdop).*sIfko=pRC 1, thenag-issaidtobSeaI@ cmti12Iprimitivenrffootamodp.*sIfg-isaprimitivreȢroSotmodp,pthengn92jisaprimitivrerootmodpigcd(j;pe) 1)UR=1.-ThereȢarethrus'(p 1)primitivreroSotsmodpin(
msbm10Z=pZ)29K cmsy8,where'denotesEuler'stotienrtfunction.Letn9(x)denotethenrumbSerofprimespURxandg(x)thenrumberofprimespURxsucrhthatgisaprimitivreroSotmodp.ÌArtin'scelebratedprimitivrerootconjecture(1927)statesthatŘifg3ѹisaninrtegerwithjgn9j>1Řandgisnotasquare,TthenforsomepSositivrerationalnrumbSer=cg;wehaveg(x)URcgAn9(x),Ras=xtendstoinnitryV.(HereAdenotesIA2rtin'scffonstantQzAUR=u
cmex10Y
ҍPpq 1 ō1۟[ z )y
p(p 1).qj8=0:3739558136Jcolor push Blackff ff -
^ٓR cmr71 html:color push gray 0 color pop html: Author'scurrentaddress:(Max-Planck-InstitutfGurMathematik,$Vivqatsgasse7,D-53111Bonn,Germany*. E-mail:q-html:color push cmyk 0 1 0 0/