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

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

• The last three digits seem easy , but the first digit is far from elementary. – Oscar Lanzi Nov 30 '18 at 10:59
• @1ENİGMA1, then we need to find 3^4^...^1000 in the form $a+bk$, ($a$ and $b$ are natural numbers). – Hussain-Alqatari Nov 30 '18 at 11:28
• @OscarLanzi , you are right (the expression contains exponents, not a common product). – Hussain-Alqatari Nov 30 '18 at 12:12
• @Hussain-Alqatari Apart from such trivial cases, there is no hope. We would need the logarithm accurate enough. – Peter Nov 30 '18 at 12:18
• In binary, the first digit is 1 and the last three digits are 000. – B. Goddard Nov 30 '18 at 12:36

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)