3
$\begingroup$

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

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

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.