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
23 ≡ 2 mod 3
234 = 281; all powers of 2 bigger than 21 are ≡ 4 mod 4, so 234 ≡ 4 mod 4
Beyond that it appears very hard: 2345 = 231024. What is 231024 modulo 5? 31024 ≈ 3.733918487432×10488, a little unwieldy to calculate directly — and computing all the digits of 231024 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 2P % 10 (where % is the "remainder function"). This is just the last digit of the powers of 2. As P increases, 2P % 10 goes through the values 2,4,8,6, and then repeats. So 2P % 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 2P is mod 10. So, to compute 2P % 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 2345 % 5:
We want to find X = 2345 % 5.
Let A = 345. Then X = 2A % 5.
The powers of 2 mod 5 are: 20 ≡ 1 mod 5, 21 ≡ 2 mod 5, 22 ≡ 4 mod 5, 23 ≡ 3 mod 5, 24 ≡ 1 mod 5, and then it repeats. So if A ≡ 0 mod 4, 2A % 5 = 1 and 2A ≡ 1 mod 5, and similarly for other values of A. So 2A % 5 = (2(A%4))% 5. Let Y = A % 4 = 345 % 4.
We now want to find Y = 345 % 4 — after doing that we'll return to X.
Let B = 45. Then Y = 3B % 4.
The powers of 3 mod 4 are: 30 ≡ 1 mod 4, 31 ≡ 3 mod 4, 32 ≡ 1 mod 4, and then it repeats. So if B ≡ 0 mod 4, 3B % 4 = 1 and 3B ≡ 1 mod 4, and similarly for other values of B. So 3B % 4 = (3(B%2))%4. Let Z = B % 2 = 45 % 2.
We now want to find Z = B % 2 = 45 % 2 — after doing that we'll return to Y and X.
45 is small enough to compute Z directly. If it weren't, we would simply note that since B = 45 is a power of 4 greater than 40=1, B is even: B % 2 = 0.
Substituting back in, Y = 3B % 4 = (3(B%2)) % 4 = (3^0) % 4 = 1.
Substituting back in, X = 2A % 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 BP % 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, BP % 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 AB % 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 BP mod 1, which is always 0.
Algorithm: To compute (BP) % 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 B0 % M, B1 % M, B2 % M, through BM % M, then continue until you find the least N such that N>M and BN ≡ BM 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 BP % 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 [BM % M, B(M+1) % M, ...] is equal to BP % M.
Alternate Explanations
This Dr. Math article addresses the problem of computing the last 8 digits of 13④27, which is the power tower 131313.·˙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 O(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 BP % M increases with M, the Nth 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 2024 Aug 05.
s.27