; TeX output 2007.01.17:1735 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=28807獍_"color push Black color popeN q cmbx12CounZting
KeithNumb ers.s獒 XQ ff cmr12Martin/Klazar kDepartment/ofAppliedMathematicsandTrInstitute/forTheoreticalComputerScience(ITI)zF4aculty/ofMathematicsandPhysics МCharles/University BMalostranskW}e/n9am.D>25 e11800/Praha 1Czech/Republic ^-html:color push cmyk 0 1 0 0߆T ff cmtt12klazar@kam.mff.cuni.cz html: color pop RyFlorian/Luca Instituto/deMatem9aticasdCUniversidad/NacionalAutonomadeMW}exico ɯwC.P4./58089 ^Morelia,/Michoac9an jMW}exico +html:color push cmyk 0 1 0 0fluca@matmor.unam.mx html: color pop)
č vcolor push Black color pop r"V
3
cmbx10AbstractMƍlcolor push Black color pop-̻K`y
3
cmr10AoKeithon!umbMerisapositiv!eintegerb>
3
cmmi10Nwiththedecimalrepresentationaz|{Y cmr81az25!",
3
cmsy101,az2 cmmi8n
_suc!h{thatnr2{andNappMearsinthesequence(Kzmľ)zmK cmsy81givenbytherecurrence_Kz1GW=Saz1;1:::l;1Kzn /=azn and4Kzm=Kzm 1
+Kzm 2+1+Kzm nfor4mS>n.GWeepro!ve_that(thereareonlynitelyman!yKeithnumbMersusingonlyonedecimaldigit(i.e.,_az1ʫ=
az2=1۱=aznP),fandthatthesetofKeithn!umbMersfisofasymptoticdensit!yzero."html: html:C4*N G cmbx121(Inutro =ductionb#XQ cmr12WiththenrumbSer197,let(+g cmmi12KmĹ)m1ӹbethesequencewhoserstthreetermsK1V=UR1;K2=9 and>K3V=UR7arethedigitsof197andthatsatisestherecurrenceKmZ=Km 1;+ Km 2+Km 3 :9color push Black 1G color pop *KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ&:9forallmUR>3.8Itsinitialtermsare 1;ꦹ9;7;17;33;57;107;197;361;665;::::9Noteethat197itselfisamemrbSerofthissequence.Thisphenomenonwasrstnoticedby :9MikreZKeithandsuchnumbSersarenowcalled1@ cmti12Keithnumbffers.MorepreciselyV,uanumbSerN:9withdecimalrepresenrtationa1a2,!",
cmsy10an
=isaKeithnumbSerifn{2andNѹappearsinthe:9sequencevK ܞ2N
9ǹ=C(K2 ܞNRAm)m1XwhoseninitialtermsarethedigitsofNreadfromlefttorighrt:9and%satisfyingK2 ܞNRAm~=K2 ܞNRAm 1+K2 ܞNRAm 2++K2 ܞNRAm n for%allm>n.These%nrumbSersappearin:9Keith's-QpapSers[html:color push cmyk 0 1 0 03 html: color pop,html:color push cmyk 0 1 0 04 html: color pop
M]andtheyarethesub jectofenrtryA007629inNeilSloane'sEncyclopedia:9ofInrtegerSequences[html:color push cmyk 0 1 0 011 html: color pop](seealso[html:color push cmyk 0 1 0 07 html: color pop,html:color push cmyk 0 1 0 08 html: color pop ʤ,html:color push cmyk 0 1 0 09 html: color pop]). -Let?Kl,bSethesetofallKeithnrumbers. 8MIt?isnotknorwnifKl,isinniteornot.The:9sequenceKbSegins 2},14;ꦹ19;28;47;61;75;197;742;1104;1537;2208;2580;3684;4788;::::9M.13KeithandD.Licrhtblau13foundall94KeithnrumbSers13smallerthan10229
1;[html:color push cmyk 0 1 0 04 html: color pop].D.Licrhtblau :9foundtherstpffandigitalKeithnrumbSer(containingeachofthedigits0to9atleastonce)::927847652577905793413.-Recallthatarep-digitisapSositivreintegerNI oftheforma(102n R m1)=9forsomea;32:9f1;:::ʜ;9gtOandn?1;#i.e.,atOnrumbSerwhichisastringofthesamedigitawhenwrittenin:9baseR@10.oOurrstresultshorwsthatthereareonlynitelymanyKeithnumbSerswhichare:9rep-digits.:9UThtml: html:*color push Black2N cmbx12Theorem>D1.1.- color popTherffeareonlynitelymanyKeithnumbersthatarerep-digitsandtheirsetcffan35beeectivelydetermined. WVefpSoinrtoutthatsomeauthorsrefertotheKeithnumbSersasrffeplicatingFibonaccidigitsinanalogywiththeFibSonaccisequence(FnP)n1PgivrenbyF15o=uk1;F2=1andFn+27=Fn+1b+Fn އfor67alln1.F.67Lucashorwed67[html:color push cmyk 0 1 0 05 html: color pop]thatthelargestrep-digitFibSonaccinrumber67is55.TheproSofofTheoremhtml:color push cmyk 0 1 0 01.1 html: color popusesBakrer-typeestimatesforlinearformsinlogarithms.HItwillibSeclearfromtheproofthatitappliestoallbffaseE]bKeithnumbersiforanryxedintegerbUR3,swhereVthesenrumbSersVaredenedanalogouslystartingwiththeirbasebexpansion(seetheremarkaftertheproSofofTheoremhtml:color push cmyk 0 1 0 01.1 html: color pop).FVorapSositivreintegerxwewriteK,`(x)UR=K i\ [1;x].AswementionedbSefore,K,`(10229 )UR=94.Ayheuristic}argumenrt[html:color push cmyk 0 1 0 04 html: color pop]suggeststhat#K,`(x)URlogx,and,in}particular,thatKݹshouldbSeinnite.8GoingintheoppSositewrayV,weshowthatKisofasymptoticdensityzero.UThtml: html:*color push BlackTheorem 1.2. color popThe35estimate #K,`(x)URō+x[ z !ڝup
z ڛ \log-IxCholds35foral lpffositiveintegersxUR2. :9color push Black 2G color pop (KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ&-TheibabSorveestimateisveryweak.
ItdoSesnotevenimplythatthatsumofthereciproScals :9of|lthememrbSersofK̹isconvergent.!WVeleavetothereaderthetaskofndingabSetterupper:9bSounddoon#K,`(x).4Trypographicalcrhanges(seetheremarkaftertheproofofTheoremhtml:color push cmyk 0 1 0 01.2 html: color pop):9shorwdthatTheoremhtml:color push cmyk 0 1 0 01.2 html: color popalsoisvXalidforthesetofbasebKeithnumbSersifb%64.HPerhaps:9itzcanbSeextendedalsotothecasebF =3.WFVorzb=2,WoKennethFVanhasanunpublished:9manruscript(mentionedbyKeith[html:color push cmyk 0 1 0 04 html: color pop])showinghowtoconstructallKeithnumbSersandthat,:9inparticular,thereareinnitelymanryofthem.FVorexample,anrypSowerof2isabinary:9KeithnrumbSer.r=-ThroughoutthispapSer,,wreusetheVinogradovsymbSolsandaswellastheLandau:9symrbSolsOM$andowiththeirusualmeaning.RecallthatforfunctionsAandBtheinequalities:9A[B ,B:aAandA[=OS(B)areallequivXalenrttothefactthatthereexistsapSositive:9constanrt=|csuchthattheinequalityjAjURcBholds.'The=|constantsintheinequalitiesimplied:9bry|thesesymbSolsmayoSccasionallydependonotherparameters.-FVorarealnrumber|xwreuse:9loggxNforthenaturallogarithmofx.mFVorasetA,Awreuse#AandjAjtodenoteitscardinalityV.:9:html: html: 2(PreliminaryzResultsb#FVoraninrtegerNjz>)0,BrecallthedenitionofthesequenceK ܞ2Nx=(K2 ܞNRAm)m1givrenintheInrtroSduction.8InK ܞ2N
zweallowNũtobSeanystringofthedigits0;1;:::ʜ;9,MsoNũmaryhaveinitialqzeros.:So,
forexample,K ܞ20206=(0;2;0;2;4;6;12;22;:::ʜ).:FVorqn1wredenethesequenceL2n[asL2n=URK ܞ2M
kwhereM6=111withndigits1.VInparticular,7L21V=(1;1;1;:::ʜ)andVL22V=UR(1;1;2;3;5;8;:::ʜ),gtheFibSonaccinrumbSers.8Inthefollowinglemma,gwhichwillbSeused?intheproSofsofbothTheorems1and2,wreestablishsomepropertiesofthesequencesK ܞ2NandL2nP.html: html:Vcolor push BlackLemmat2.1.lt color popLffetlN7Pbeastringofthedigits0;1;:::ʜ;9withlengthn1.IfN7Pdoffesnotstart35with0,weunderstanditalsoasthedeffcimalrepresentationofapositiveinteger.H color push Black(a) color popIfONO3hasatleffastkoUR1nonzeroentries,thenK2 ܞNRAmK4URL2kyk6+m n#holdsforeverymnX+1.r> color push Black(b) color popIfYNhasatleffastonenonzeroentry,c~thenK2 ܞNRAmL2nRAm n#bholdsforeverymnE+1.MWe_have35K2 ܞNRAmK4UR9L2nRAm7foreverym1. color push Black(c) color pop_If35nUR3andN6=K2 ܞNRAm
)forsomem1(soNtisaKeithnumbffer),then2n