Re: Power Tower and Carmichael Lambda Function
- To: mathgroup at smc.vnet.net
- Subject: [mg89739] Re: [mg89662] Power Tower and Carmichael Lambda Function
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Thu, 19 Jun 2008 05:44:44 -0400 (EDT)
- References: <200806170436.AAA26560@smc.vnet.net>
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>
- Power Tower and Carmichael Lambda Function