The first digit and the last three digits of tower of exponents

Question

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)?

Answer 1

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+2\times100}=...=008\mod1000$$

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 $n\ge b$ we can write:

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

$$a^n \equiv a^{[(n \ \text{mod}\ p)-(b\text{mod}\ p)]+b}\mod m\tag{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)-(b\text{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)