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³ ≡ 2 mod 3

2³⁴ = 2⁸¹; all powers of 2 bigger than 2¹ are ≡ 4 mod 4, so 2³⁴ ≡ 4 mod 4

Beyond that it appears very hard: 2³⁴⁵ = 2³¹⁰²⁴. What is 2³¹⁰²⁴ modulo 5? 3¹⁰²⁴ ≅ 3.733918487432×10⁴⁸⁸, a little unwieldy to calculate directly — and computing all the digits of 2³¹⁰²⁴ 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, and replacing the modulus (10) with another (4).

Except when the old modulus is 1, the new modulus is smaller than the old one (because the value 0 is either not in the cycle, or constitutes the entire cycle).

Using that method, let's work out 2³⁴⁵ % 5:

We want to find X = 2³⁴⁵ % 5.

Let A = 3⁴⁵. Then X = 2^A % 5.

The powers of 2 mod 5 are: 2⁰ ≡ 1 mod 5, 2¹ ≡ 2 mod 5, 2² ≡ 4 mod 5, 2³ ≡ 3 mod 5, 2⁴ ≡ 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⁴⁵ % 4.

We now want to find Y = 3⁴⁵ % 4 — after doing that we'll return to X.

Let B = 4⁵. Then Y = 3^B % 4.

The powers of 3 mod 4 are: 3⁰ ≡ 1 mod 4, 3¹ ≡ 3 mod 4, 3² ≡ 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⁵ % 2.

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

4⁵ is small enough to compute Z directly. If it weren't, we would simply note that since B = 4⁵ is a power of 4 greater than 4⁰=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 incorporates this.

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⁰ % M, B¹ % M, B² % 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.

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. 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.

Men Core Values

© 1996-2008 Robert P. Munafo. email me more info

This work is licensed under a Creative Commons Attribution 2.5 License. Details here

Back to my main page s.13