Jtdylktuy

How to find the first digit and the last three digits of ${{{{2}^{3}}^{4}}^{cdots }}^{1000}$, where the expression contains all integer numbers (from $2$ to $1000$, in order)?

Let us compute the last three digits. Basically, we want to calculate:

$$2^{something big} mod 1000$$

In general, values of $a^n$ modulo $m$ start to repeat after a certain value of $n$. For example, in case of $a=2$ and $m=1000$, values $2^1$ and $2^2$ won't appear ever again, but:

$$2^3=2^{3+100}=2^{3+2times100}=...=008mod1000$$

Base exponent $b$ and period $p$ can be computed for every possible value of $a,m$. I'll need a function for it:

findCycle[n_, modulo_] := Module[

  {n2 = Mod[n n, modulo], k = 1, lst = {Mod[n, modulo]}},

  While[! MemberQ[lst, n2],

   AppendTo[lst, n2]; n2 = Mod[n2 n, modulo]; k = k + 1;

   ];

  pos = Position[lst, n2];

  Return[{pos[[1, 1]], k + 1 - pos[[1, 1]]}];

  ]

For example:

findCycle[2,1000]

returns $b,p$ for $a=2$, $m=1000$:

{3, 100}

For values of $nge b$ we can write:

$$a^n equiv a^{[(n-b)text{mod} p]+b}mod m$$

$$a^n equiv a^{[(n text{mod} p)-(btext{mod} p)]+b}mod mtag{1}$$

Note that if the value in the square brackets is negative, we have to add $p$ to make it positive. Now suppose that:

$$a=2^{3^{4^{dots^{1000}}}}$$

This tower is a nightmare to write, so I'll represent it as list:

$$a={2, 3, 4, dots,1000}tag{2}$$

Replace that into (1) and you get:

$${2, 3, 4, dots,1000} equiv 2^{[({3, 4, dots,1000} text{mod} p)-(btext{mod} p)]+b}mod m$$

$${2, 3, 4, dots,1000} equiv 2^{[({3, 4, dots,1000} text{mod} 100)-3]+3}mod m$$

Now you can repeat the same process to calculate:

$${3, 4, dots,1000} text{mod} 100$$

With this in mind we can create a recurrent function that calculates any tower modulo any number. We'll pass the tower to Mathematica as the list (2).

First, any tower is equal to zero modulo 1:

findMod[tower_, m_] := 0 /; m == 1

If the tower has single number (no exponent at all), just calculate the module:

findMod[tower_, m_] := Mod[tower[[1]], m] /; Length[tower]==1

And in the general case, we'll have to apply resursion:

findMod[tower_,m_] := Module[

    {a1,tower2,cycle,b,p,exp},

    a1=tower[[1]];

    tower2=Drop[tower,1];

    cycle=findCycle[a1,m];

    b=cycle[[1]];

    p=cycle[[2]];

    exp=findMod[tower2,p]-Mod[b,p];

    If[exp<0, exp=exp+p];

    exp=exp+b;

    Return[Mod[a1^exp,m]];

]

We can test the recursion on a simple tower:

$$2^{3^5} = 2^{243} = 14134776..........0958208
equiv 208 mod 1000$$

The following call will really return 208, as expected:

findMod[{2, 3, 5}, 1000]

You can calculate the last 3 digits of the complete tower from the problem with the following call:

findMod[Range[2,1000], 1000]

...and the result is 352.

The first digit of the tower is equal to the first digit of Graham's number.

(Just kidding)