Re: Power Tower and Carmichael Lambda Function

*To*: mathgroup at smc.vnet.net*Subject*: [mg89744] Re: Power Tower and Carmichael Lambda Function*From*: m.r at inbox.ru*Date*: Thu, 19 Jun 2008 05:45:40 -0400 (EDT)*References*: <g37ev9$pse$1@smc.vnet.net>

On Jun 16, 11:35 pm, "John Snyder" <jsny... at wi.rr.com> wrote: > On New Year's Day of this year the following problem was published in a > problem contest on an internet website asking for the last four digits of > the following number: > > 2008^(2007^(2006^.^.^.^(2^1))) > > For some reason I got interested in the problem (it isn't homework, I am = 58 > years old) and I solved it using Mathematica's CarmichaelLambda function = as > follows: > > In[9]:= lambda=FoldList[CarmichaelLambda[#1]&,10000,Range[6]] > Out[9]= {10000,500,100,20,4,2,1} > > In[10]:= m=Range[2002,2008]//Reverse > Out[10]= {2008,2007,2006,2005,2004,2003,2002} > > In[11]:= Mod @@@ Transpose[{m, lambda}] > Out[11]= {2008,7,6,5,0,1,0} > > Now, since the tower of powers is evaluated from the top down I reasoned > that everything from the top down through the 5 contributed nothing to th= e > answer because 5^0=1. I got my answer doing the following: > > In[12]:= PowerMod[2008,7^6,10000] > Out[12]= 5328 > > When the solution was finally published the other day the following resul= t > was listed as being the correct solution: > > In[13]:= PowerMod[2008,7^6^5,10000] > Out[13]= 1008 > > It seems to me that the relevant exponent should be just 7^6, not 7^6^5 > because 5^0=1. Playing around with some smaller and easier numbers i= n > Mathematica I think I am correct, but the problem site says otherwise. = I am > no expert in number theory so could someone who is please explain to me > which answer is correct and why? Does Mathematica really use the parenthe= ses > in the exponent in evaluating something like this? > > Thanks, > > John The site answer is correct. Your reasoning is equivalent to assuming that PowerMod[2005, p, 20] == PowerMod[2005, 0, 20] because the sequence PowerMod[2005, p, 20] has period 1. The problem is that the sequence is only eventually periodic and the period starts at p == 1. Doing it step by step from there (and I just checked manually that we landed inside the period on each step): In[1]:= Fold[PowerMod @@ Insert[#2, #, 2]&, 5, {{2006, 100}, {2007, 500}, {2008, 10^4}}] Out[1]= 1008 Maxim Rytin m.r at inbox.ru