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>
- Power Tower and Carmichael Lambda Function