Tuesday, March 17, 2009

solution: 81^2009

Grades 11 & 12 5-Star Challenge #2
Find (a) the number of digits and (b) the last three (least significant) digits in the decimal expression of 812009.


My Solution...
This problem asks for two elementary observations. If the number were written in its entirety, it would be a simple matter to obtain the number of digits and the values of the last three digits. The entire number can be generated with a couple of lines of code using Java's BigInteger class.

BigInteger myBigNumber = new BigInteger("81").pow(2009);
System.out.println("myBigNumber: "+myBigNumber);

This returns (in a fraction of a second):

myBigNumber:

1400886426099001433589715356524325994077360058833291454060331448901202858812711608791505300540205160834871243114967077782896741018493232826119962265403933221408273710682285389474611581003628765532988693839153728368550209031963049953365587333165550684382285106676049916357515617508318430039472665058505400648134895508543610798780057273663322426956561416111481073295564688756106556978220972883768498990439376379038088913512578774433394954966862795937723871349150451305665824022155706009283754336379201724142185351446653196901336911382788170275693693431585571516214076703025655694724313935072160077237502277620633564638041394172823865006761057098692874958064119778303667684220473562875130389095576612598169616570264206698883864712941599975306460033566903701203176613915280808200553190149220172757742382552424264898048660485008953744755857351182328200797217390733117879482736723725387755343016641042324605268387235071317590044699322617486518833978498750446720283318797784379982099655399049514088697411493542735966238355231518335754560005454557858737827355594203256731113150254221184261378594118900660565386875397480998177808153453972240763137726201802935458465644187508973316810617828944777550600037116120613295523595674229092486855978909224433568001602101966137609851452418351933395026445713151813690775772659529245247483081061394734160452917273402957713927998398637008649959045364542625757251174939330779763645565078645414995355444331511328545544587436720247358813300136273063929536760693736894399092656898581391777601176686638814415800605457552137755811561722992947830941361575088520921316840670291945199828480758662688749076445628397158944252925926207253727397615642302175056456168537654926096910594424358310081741719763482063248026418549153981883499716627174273667624458356479660732203553476892308402043990264919201939021708092767869280613832259386192559262656045967546526551060223597953426164586528815240198370930615443469369831397836790511704027247717287613128262970900587798085687044826070427586179676392059739626595037167328563772506422713580328669959080751912111426766214386993833793411310032618393156947481034604475623258966648528615807295339485106694016473355821675133837209206523909378952991095736019452549069793468232090700893085918364572584074859059077156795322914743377215102376435931960712370356874666922951857034687294703109308613860715556328236763180084679159342631746367233847114542831918603472299798321527157441161819532742005968777296078987636685014605803610522533976135083018079462867231622504340685958958775803013385058237912087337518155851768194473603085161979303255925564896683534521901491172404855277443706334679904563837822732299389135616888785840527710491760378625577274127165160723696855383968993354486834189433444754952751349119445485023181677760092071751879339708391793177141272161381338406604416686619826676210135423387944224584209170249358763128906780988581499912792718505330714538446491560748113617647828696553112964608607567406647137734043006583685118169281006120091135549995534312849407690524527234325455560291603364366173667248135691235606237319206864662357808314487913529150433701250314479681846670702891523598161060942612992920037173624206384607196996451365525196548440267693551682140725599199807911935490733624764556262308015951473144301853801136043280112830549607313441641080796896809627284910178979983295107307002907330430332271237131267427131349236806228355581537700780297380111225674100174944973118017202128990296866935839828010719361300152001055622795047713257519014364284326307078184203112517839087782402492861653020274288404432905972207465665985433591495473890988412099059297644788913887941133672356210069355051778825969788920325814207846046437928268923946341521305003727054700978419670287048809561516312934357723512398670440769027697003378905339200718030813912207894907559735934856589959121

Of course you could count the digits by hand or write a couple more lines of java to find the number of digits, or use the character count in a Word document. Each of these processes is admirably resourceful, but disregards a lurking elegance. I would not object to such a direct approach to the problem, but there is certainly room for some more finesse. The sheer size of the number renders useless more accessible tools like calculators and spreadsheets. Microsoft Excel has pitiful accuracy, and the students quickly find out that they cannot even use their TI calculators to find the number of digits (directly).

To find the number of digits, we need to remember that we mean 'decimal' digits. The relationship between exponents and the number of digits is clear if the bases agree. Our number, 812009 can be written as 102009*log81=103834.146..., which must be a 3835 digit (base 10) number, as it is situated between 103834 (which is the smallest 3835-digit number) and 103835 (which is the smallest 3836-digit number).

The last three digits present more of a challenge (barring the availability of the number in decimal form). The last digit, one may easily observe, is 1.

As in the first part of the question, there is a simple shortcut that most would fail to find, but a few would anticipate or discover. The last three digits of the powers of 81 progress through a repeating pattern. This is because 8125=515377520732011331036461129765621272702107522001. The important part is that the last three digits of 8125 are 001, which means that when we multiply by 81 to get 8126, we will be back at 081 for our last three digits, and we will go through the progression again for every 25 factors of 81. By this, we can conclude that 812000 will have 001 as the last three digits, so 812009 will have the same three-digit ending as 819, which is 121. This idea can be used within Excel, but even 819 is beyond the precision, so it is necessary to discard the more significant digits, through a formula like:

A2=MOD(A1*81,1000)

which gives the last three digits of the next power of 81. The calculation is always manageable for Excel, and the values never get larger than 3 digits. I do not expect my students to know about modular arithmetic, but the problem certainly supports that type of finding.

A basic high-school-math-with-scientific-calculator method for solving this problem involves the binomial theorem, and I think is very clever.

If we write 812009 as (80+1)2009, we can expand it using the binomial theorem as:

(2009C0)802009*10
+(2009C1)802008*11
+(2009C2)802007*12
+...
+(2009C2006)803*12006
+(2009C2007)802*12007
+(2009C2008)801*12008
+(2009C2009)800*12009

Notice that most of the 2010 numbers in this sum end in 000. Any time the exponent on 80 is at least 3, the number will have 1000 as a factor. This means that the last three digits are entirely determined by the terms (2009C2007)802*12007, (2009C2008)801*12008, and (2009C2009)800*12009, which are:

12909030400
160720
1

...and whose sum ends in the digits 121.

This method is more general in that it does not rely on the discovery of a cycle (which may be very long for some bases) or the access to a computer brute-force approach.

1 comment: