Re: Power Tower and Carmichael Lambda Function

*To*: mathgroup at smc.vnet.net*Subject*: [mg89740] Re: [mg89662] Power Tower and Carmichael Lambda Function*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Thu, 19 Jun 2008 05:44:55 -0400 (EDT)*References*: <200806170436.AAA26560@smc.vnet.net> <0843751E-D32D-4FE3-9716-49E0576B4D89@mimuw.edu.pl>

Of course, if you still think this is too slow, it is enough to do: Fold[PowerMod[#2, #1, 10^4] &, 1, Range[2001, 2008]] // Timing {0.00006, 1008} Andrzej Kozlowski On 19 Jun 2008, at 11:22, Andrzej Kozlowski wrote: > I do not understand why you did not just do this: > > Fold[PowerMod[#2, #1, 10^4] &, 1, Range[2008]] // Timing > {0.00546, 1008} > > It saves you having to use CarmichaelLambda, is not too long to > wait, and leaves not doubt as to the correct answer. > > Andrzej Kozlowski > > On 17 Jun 2008, at 13:36, John Snyder 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 the >> 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 >> result >> 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 >> in >> 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 >> parentheses >> in the exponent in evaluating something like this? >> >> Thanks, >> >> John >

**References**:**Power Tower and Carmichael Lambda Function***From:*"John Snyder" <jsnyder@wi.rr.com>