# Sequence A092188, Smallest Positive Integer M such that 2^3^4^5^...^N ≡ M mod N

This sequence, Sloane's A092188, was suggested by John Horton Conway to NJA Sloane in 2004. It looks hard to compute, but is actually relatively easy.

To give the first few examples:

2 ≡ 2 mod 2

2^{3} ≡ 2 mod 3

2^{34} = 2^{81}; all powers of 2 bigger than 2^{1} are ≡ 4 mod 4,
so 2^{34} ≡ 4 mod 4

Beyond that it appears very hard: 2^{345} = 2^{31024}. What
is 2^{31024} modulo 5? 3^{1024} ≈ 3.733918487432×10^{488}, a
little unwieldy to calculate directly — and computing all the digits
of 2^{31024} is impossible, even if every atom in the known
universe were used to store a digit.

To work out terms in this sequence, you have to find a new modulus for
the given base and modulus, that can be used to reduce the exponent.
For example, consider 2^{P} % 10 (where % is the "remainder
function"). This is just the last digit of the powers of 2. As P
increases, 2^{P} % 10 goes through the values 2,4,8,6, and then
repeats. So 2^{P} % 10 depends on P % 4. In this case, the
"exponent modulus" for base 2 mod 10 is 4. No matter how big the power
is, as long as you can figure out what it is mod 4, then you can
figure out what 2^{P} is mod 10. So, to compute 2^{P} % 10, we
start by computing P % 4. This simplifies the problem by removing
one exponent from the "tower of exponents", and replacing the modulus
(10) with another (4).

Using that method, let's work out 2^{345} % 5:

We want to find X = 2^{345} % 5.

Let A = 3^{45}. Then X = 2^{A} % 5.

The powers of 2 mod 5 are: 2^{0} ≡ 1 mod 5, 2^{1} ≡ 2 mod 5,
2^{2} ≡ 4 mod 5, 2^{3} ≡ 3 mod 5, 2^{4} ≡ 1 mod 5, and then
it repeats. So if A ≡ 0 mod 4, 2^{A} % 5 = 1 and 2^{A} ≡ 1
mod 5, and similarly for other values of A. So 2^{A} % 5 =
(2^{(A%4)})% 5. Let Y = A % 4 = 3^{45} % 4.

We now want to find Y = 3^{45} % 4 — after doing that we'll
return to X.

Let B = 4^{5}. Then Y = 3^{B} % 4.

The powers of 3 mod 4 are: 3^{0} ≡ 1 mod 4, 3^{1} ≡ 3 mod 4,
3^{2} ≡ 1 mod 4, and then it repeats. So if B ≡ 0 mod 4,
3^{B} % 4 = 1 and 3^{B} ≡ 1 mod 4, and similarly for other
values of B. So 3^{B} % 4 = (3^{(B%2)})%4. Let Z = B % 2 =
4^{5} % 2.

We now want to find Z = B % 2 = 4^{5} % 2 — after doing that
we'll return to Y and X.

4^{5} is small enough to compute Z directly. If it weren't, we would
simply note that since B = 4^{5} is a power of 4 greater than
4^{0}=1, B is even: B % 2 = 0.

Substituting back in, Y = 3^{B} % 4 = (3^{(B%2)}) % 4 = (3^0) % 4 = 1.

Substituting back in, X = 2^{A} % 5 = (2^{(A%4)}) % 5 = (2^1)
% 5 = 2. So 2 is the answer, and the next term in the sequence:
2^(3^(4^5)) ≡ 2 mod 5.

It is important to note that the repeating pattern of values of
B^{P} % M does not necessarily start right away — the first few
powers of a base might not fit into the pattern. For example, if B
is 2 and M is 12, B^{P} % M is 1, 2, 4, 8, 4, 8, 4, 8, ... —
so it takes 3 steps to get to the repeating part, and the repeating
part is 2 steps long. The algorithm described below accounts for this
possibility.

Now, notice that if X % M is 0, then KX % M is also 0, for all
positive integers K. It follows that if A^{B} % M = 0, then all
higher powers of A are also equal to 0 mod M. That means that the
cycle consists entirely of 0, a cycle of length 1. Any other cycles
(such as the 2,4,8,6 cycle above) cannot include 0, because if they
did, 0 would be the end of the cycle. Thus, every cycle is of a length
less than M, unless M itself is 1. So, whenever the old modulus is
not 1, the new modulus is smaller than the old one. The practical
upshot of this is that when evaluating high power-towers, the problem
usually reduces to something of the form B^{P} mod 1, which is
always 0.

Algorithm: To compute (B^{P}) % M, where base B and modulus
M are positive integers, and P is a positive integer or a "power
tower" of 2 or more terms each greater than 1:

If M is 1, return 0

If P is 1, return B % M

Otherwise P is an integer greater than 1, or a power tower:

Calculate B^{0} % M, B^{1} % M, B^{2} % M, through
B^{M} % M, then continue until you find the least N such that
N>M and B^{N} ≡ B^{M} mod M. Then C = N-M is
the length of the cycle for powers of B mod M.

If P is an integer or a power tower less than N+1, then
B^{P} % M is one of the values already examined in determining
C. If P is a power tower greater than N, invoke this algorithm
recursively to get the value of P % C. Then use P % C to
determine which term in the series [B^{M} % M, B^{(M+1)} %
M, ...] is equal to B^{P} % M.

Alternate Explanations

This Dr. Math article
addresses the problem of computing the last 8 digits of 13^{④}27,
which is the power tower 13^{1313.·˙1313} with
27 13's.

A similar description based on the Dr. Math article is found in the Wikipedia article on the Graham-Rothschild number, and gives the last 100 digits of that huge quantity.

Both descriptions give an algorithm that is similar to mine, but without handling the general case of arbitrary moduli and exponents. For example, the Dr. Math article's power tower consists entirely of 13's.

Computing the First 1000 Terms of A092188

Using this method, the terms are easy to calculate. There is only one
recursive call, so the amount of computation does not increase
dramatically with each level of the power tower. Further we note that
the modulus is guaranteed to reduce by 1 at each step in the recursive
reduction. Statistically one might expect the modulus to reduce by an
average of one-half at each stage, implying log(M) steps in a
typical case. In fact this is usually true for the sequence in
question: among the first million terms, none requires more than 11
recursive iterations. Since the loop to find the pattern for B^{P}
% M increases with M, the N^{th} term in A092188 takes about
O(N log(N)) calculations. For the first 1000 terms I get:

A092188: 2, 2, 4, 2, 2, 1, 8, 8, 2, 2, 8, 5, 8, 2, 16, 2, 8, 18, 12, 8, 2, 16, 8, 2, 18, 26, 8, 11, 2, 2, 32, 2, 2, 22, 8, 31, 18, 5, 32, 2, 8, 27, 24, 17, 16, 8, 32, 43, 2, 2, 44, 45, 26, 2, 8, 56, 40, 47, 32, 33, 2, 8, 64, 57, 2, 5, 36, 62, 22, 60, 8, 1, 68, 2, 56, 57, 44, 8, 32, 80, 2, 2, 8, 2, 70, 11, 24, 16, 62, 57, 16, 2, 8, 37, 32, 70, 92, 35, 52, 67, 2, 9, 96, 92, 98, 45, 80, 76, 2, 68, 64, 99, 56, 62, 40, 44, 106, 36, 32, 35, 94, 2, 64, 102, 8, 16, 128, 113, 122, 95, 68, 113, 72, 107, 104, 2, 62, 8, 92, 8, 60, 57, 80, 127, 74, 92, 68, 21, 2, 64, 56, 53, 134, 2, 44, 149, 8, 98, 32, 85, 80, 162, 84, 2, 2, 157, 8, 161, 2, 170, 156, 27, 98, 127, 112, 47, 16, 97, 152, 146, 148, 155, 16, 142, 2, 2, 8, 134, 132, 50, 128, 23, 70, 122, 92, 147, 134, 62, 152, 5, 168, 127, 104, 2, 112, 62, 96, 189, 92, 86, 204, 131, 152, 27, 80, 64, 76, 74, 112, 70, 68, 128, 64, 152, 212, 216, 56, 32, 62, 134, 40, 142, 44, 102, 224, 8, 36, 200, 32, 30, 156, 242, 216, 92, 2, 18, 64, 2, 102, 187, 8, 200, 16, 2, 256, 2, 242, 253, 252, 98, 226, 198, 200, 257, 246, 194, 72, 101, 242, 10, 240, 239, 2, 2, 200, 269, 8, 188, 232, 81, 8, 149, 60, 227, 200, 43, 224, 2, 272, 167, 220, 168, 92, 47, 216, 134, 170, 200, 152, 113, 64, 269, 208, 277, 206, 34, 288, 215, 2, 94, 200, 305, 306, 197, 8, 178, 98, 156, 192, 152, 246, 189, 80, 252, 162, 185, 248, 8, 2, 267, 168, 179, 324, 72, 176, 295, 330, 212, 172, 2, 170, 239, 328, 62, 200, 264, 272, 216, 302, 161, 288, 262, 224, 202, 16, 155, 276, 148, 152, 284, 146, 35, 148, 147, 338, 327, 16, 125, 142, 204, 188, 145, 2, 227, 8, 330, 134, 260, 132, 143, 50, 42, 128, 57, 216, 242, 264, 167, 122, 223, 288, 95, 344, 87, 332, 183, 62, 113, 352, 144, 206, 343, 168, 242, 330, 68, 104, 106, 2, 2, 112, 106, 62, 2, 96, 8, 398, 331, 92, 298, 86, 8, 416, 2, 344, 155, 152, 200, 242, 229, 80, 79, 64, 272, 76, 246, 74, 256, 112, 386, 70, 323, 68, 372, 128, 170, 64, 352, 152, 2, 212, 215, 216, 57, 56, 32, 32, 53, 292, 419, 134, 111, 272, 2, 142, 355, 44, 407, 102, 149, 224, 156, 8, 227, 36, 98, 200, 291, 32, 31, 30, 407, 156, 167, 242, 1, 216, 488, 92, 299, 248, 359, 18, 332, 64, 344, 2, 97, 352, 491, 438, 141, 8, 67, 200, 161, 16, 341, 2, 1, 512, 512, 2, 112, 500, 431, 512, 200, 512, 321, 98, 424, 488, 302, 198, 2, 464, 453, 522, 224, 512, 330, 194, 152, 72, 455, 370, 288, 512, 294, 10, 146, 512, 512, 512, 101, 276, 521, 2, 417, 200, 8, 546, 512, 8, 269, 188, 70, 512, 2, 362, 263, 8, 212, 432, 323, 344, 438, 512, 477, 200, 50, 330, 177, 512, 65, 2, 23, 272, 85, 458, 310, 512, 512, 168, 443, 92, 436, 342, 344, 512, 465, 134, 512, 468, 62, 200, 8, 152, 64, 414, 206, 64, 277, 572, 204, 512, 533, 582, 525, 512, 269, 34, 2, 288, 601, 524, 192, 312, 269, 94, 372, 512, 352, 618, 398, 620, 512, 512, 228, 8, 86, 178, 397, 416, 239, 156, 557, 512, 2, 152, 501, 568, 242, 512, 402, 80, 519, 252, 281, 488, 75, 512, 357, 576, 512, 8, 273, 332, 139, 598, 512, 168, 512, 512, 591, 324, 128, 72, 277, 512, 161, 632, 377, 668, 44, 212, 652, 512, 443, 2, 667, 512, 2, 582, 32, 672, 681, 62, 365, 200, 134, 264, 147, 272, 2, 216, 608, 652, 689, 512, 512, 640, 572, 262, 673, 224, 53, 202, 8, 16, 591, 512, 57, 276, 200, 148, 206, 512, 421, 284, 512, 508, 127, 398, 9, 512, 728, 512, 70, 704, 653, 694, 92, 384, 541, 494, 97, 512, 512, 204, 398, 560, 617, 518, 251, 376, 687, 602, 151, 384, 689, 330, 517, 512, 95, 260, 200, 512, 49, 524, 512, 432, 512, 42, 460, 512, 720, 442, 2, 216, 2, 242, 2, 264, 512, 556, 740, 512, 486, 614, 620, 288, 777, 488, 414, 344, 461, 482, 99, 728, 460, 580, 257, 460, 792, 512, 478, 352, 728, 144, 585, 608, 407, 746, 101, 168, 759, 242, 599, 736, 281, 68, 162, 512, 113, 106, 512, 412, 2, 2, 129, 112, 2, 106, 166, 476, 658, 2, 269, 512, 631, 8, 157, 816, 188, 750, 210, 512, 11, 298, 362, 508, 837, 8, 519, 416, 149, 2, 660, 344, 94, 582, 512, 152, 836, 200, 331, 672, 617, 660, 222, 512, 27, 512, 2, 64, 640, 272, 5, 512, 458, 246, 477, 512, 827, 256, 461, 112, 451, 386, 757, 512, 47, 766, 576, 512, 778, 372, 728, 128, 854, 170, 97, 512, 200, 352, 591, 152, 257, 2, 113, 664, 327, 668, 231, 216, 269, 512, 129, 512, 2, 32, 887, 32, 750, 512, 229, 752, 341, 880, 486, 596, 327, 574, 215, 736, 221, 2, 778, 608, 716, 822, 2, 512, 227, 876, 305, 572, 833, 620, 453, 224, 512, 156, 569, 8, 512, 702, 812, 512, 2, 98, 432, 200, 794, 770, 687, 512, 33, 512, 152, 512, 602, 890, 841, 640, 512, 652, 79, 728, 8, 488, 902, 704, 567, 488, 728, 92, 512, 790, 565, 248, 147, 852, 8, 512, 844, 332, 964, 64, 929, 344, 62, 500, 872, 596, 512, 352, ...

Some other sequences are discussed here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2018 Feb 04. s.11