MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Power Tower and Carmichael Lambda Function

On Jun 16, 11:35 pm, "John Snyder" <jsny... at> 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 =
> years old) and I solved it using Mathematica's CarmichaelLambda function =
> 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=
> 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=
> 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=
> 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=
> 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

  • Prev by Date: Re: Power Tower and Carmichael Lambda Function
  • Next by Date: How to get a ordered text combining Text and values
  • Previous by thread: Re: Power Tower and Carmichael Lambda Function
  • Next by thread: plot in text mode