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