Power Tower and Carmichael Lambda Function
- To: mathgroup at smc.vnet.net
- Subject: [mg89662] Power Tower and Carmichael Lambda Function
- From: "John Snyder" <jsnyder at wi.rr.com>
- Date: Tue, 17 Jun 2008 00:36:51 -0400 (EDT)
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
- Follow-Ups:
- Re: Power Tower and Carmichael Lambda Function
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: Power Tower and Carmichael Lambda Function