Sequence A162002: 2↑↑N ≡ 22N mod N
This sequence, Sloane's A162002, contains all values of N such that 2↑↑N ≡ 22N mod N.
A↑↑B uses Knuth's up-arrow notation, in which A↑B is AB and A↑↑B represents the tetration operator (iterated exponentiation): A↑↑1 = A, A↑↑2 = AA, A↑↑3 = AAA, etc. Sequence A014221 gives the first few values of 2↑↑N.
An efficient method of calculating the value R such that A↑↑B ≡ R mod N is described on my page concerning sequence A092188.
The sequence begins: 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 15, 16, 17, 18, 20, 24, 26, 28, 30, 32, 34, 36, 40, 42, 43, 44, 46, 48, 51, 52, 56, 58, 60, 64, 68, 70, 72, 76, 78, 80, 84, 85, 88, 90, 96, 100, ...
Here are the first few terms with the values of 2↑↑N mod N and 22N mod N shown explicitly:
221 = 22 = 4 ≡ 1 mod 1 ; 2↑↑1 = 2 ≡ 1 mod 1
222 = 24 = 16 ≡ 2 mod 2 ; 2↑↑2 = 22 = 4 ≡ 2 mod 2
223 = 28 = 256 ≡ 1 mod 3
; 2↑↑3 = 222 = 24 = 16 ≡ 1 mod 3
224 = 216 = 65536 ≡ 4 mod 4
; 2↑↑4 = 2222 = 224 = 216 = 65536 ≡ 4 mod 4
225 = 232 = 4294967295 ≡ 1 mod 5
; 2↑↑5 = 22222 = 2224 = 2216 = 265536
≈ 2.0035299308×1019728 ≡ 1 mod 5
Based on the first several terms, and the relative difficulty in calculating 2↑↑N directly, reader Tony Noe hypothesized that 2↑↑N was equal to 22N mod N for all N.
The first counterexample is for N=7, followed by 9, 11, 13, 19, 21, 22, 23, 25, 27, 29, ... (sequence A162018). The equality becomes rarer as we go up to higher numbers. For example, it's true for only 10 values between 950 and 1000.
The First Counterexample
7 is not a member of the sequence because 227 ≡ 4 mod 7, but 2↑↑7 ≡ 2 mod 7. Here are the complete details:
227 = 2128 = 340282366920938463463374607431768211456, which is ≡ 4 (mod 7) because 48611766702991209066196372490252601636 times 7 = 340282366920938463463374607431768211452. (There is an easier way to get this result, as we'll see below).
Now let's consider 2↑↑7 mod 7. Think of this as 2P mod 7, where P is 2↑↑6.
The powers of 2 mod 7 are:
20 ≡ 1 mod 7
21 ≡ 2 mod 7
22 ≡ 4 mod 7
23 ≡ 1 mod 7
24 ≡ 2 mod 7
...
and so on. Notice the pattern: 1, 2, 4, 1, 2, ... is a repeating cycle of 3 different values. This continues indefinitely, as is easy to show. So, if P is a multiple of 3, then 2P ≡ 1 mod 7. If P is a multiple of 3 plus 1, then 2P ≡ 2 mod 7, and if P is a multiple of 3 plus 2, then 2P ≡ 4 mod 7.
For example, consider 2128 mod 7, which we calculated above by the "direct" method. Since 128 = 3×42+2, it is a multiple of 3 plus 2. That means that 2128 ≡ 4 mod 7.
So, to determine 2↑↑7 mod 7, we need to determine P mod 3, that is to say, 2↑↑6 mod 3.
Doing a similar thing we see that:
20 ≡ 1 mod 3
21 ≡ 2 mod 3
22 ≡ 1 mod 3
23 ≡ 2 mod 3
...
and so on. Notice here there is a cycle of 2. In particular, all even powers of 2 are ≡ 1 mod 3, and all odd powers of 2 are ≡ 2 mod 3.
Since 2↑↑6 = 2(2↑↑5) and 2↑↑5 is even, we know that 2↑↑6 ≡ 1 mod 3. Thus, P ≡ 1 mod 3, or in other words, P is a multiple of 3 plus 1.
Now that we know that P is a multiple of 3 plus 1, we can see that 2P ≡ 2 mod 7.
Since 227 = 2128 ≡ 4 mod 7, and 2↑↑7 = 2P ≡ 2 mod 7, we can see that 7 is not a member of sequence A162002.
A Longer List
Using a similar method, it is relatively easy to compute both 2↑↑N mod N and 22N mod N for surprisingly large values of N. Here are the first 500 terms of both sequences:
A162002: N such that 2↑↑N ≡ 22N mod N: 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 15, 16, 17, 18, 20, 24, 26, 28, 30, 32, 34, 36, 40, 42, 43, 44, 46, 48, 51, 52, 56, 58, 60, 64, 68, 70, 72, 76, 78, 80, 84, 85, 88, 90, 96, 100, 102, 104, 112, 120, 124, 126, 127, 128, 130, 132, 136, 140, 141, 144, 145, 148, 156, 160, 164, 168, 170, 172, 176, 180, 182, 190, 192, 194, 196, 200, 204, 208, 210, 220, 224, 226, 232, 234, 238, 240, 244, 248, 252, 255, 256, 257, 260, 264, 272, 276, 280, 288, 292, 300, 304, 306, 308, 312, 316, 320, 328, 336, 340, 352, 356, 360, 364, 370, 372, 384, 386, 388, 390, 394, 396, 400, 406, 408, 416, 420, 424, 430, 436, 439, 440, 442, 448, 468, 476, 480, 482, 488, 490, 492, 493, 496, 504, 508, 510, 512, 514, 520, 528, 532, 536, 537, 544, 546, 560, 565, 568, 572, 576, 580, 582, 592, 600, 604, 612, 616, 620, 624, 628, 630, 640, 641, 646, 656, 658, 660, 672, 676, 680, 688, 700, 704, 706, 714, 720, 724, 728, 730, 732, 736, 744, 746, 748, 754, 760, 768, 771, 772, 776, 780, 784, 792, 796, 800, 816, 820, 824, 832, 834, 840, 844, 868, 880, 884, 896, 898, 900, 904, 910, 916, 924, 928, 936, 952, 960, 964, 966, 970, 976, 984, 988, 992, 996, 1002, 1008, 1020, 1024, 1028, 1036, 1038, 1040, 1048, 1056, 1060, 1088, 1090, 1092, 1096, 1100, 1102, 1116, 1120, 1144, 1148, 1152, 1158, 1164, 1168, 1170, 1190, 1196, 1200, 1204, 1206, 1208, 1216, 1220, 1224, 1232, 1240, 1246, 1248, 1252, 1258, 1260, 1264, 1270, 1276, 1280, 1282, 1285, 1300, 1312, 1320, 1324, 1326, 1330, 1344, 1346, 1348, 1358, 1360, 1364, 1366, 1400, 1408, 1416, 1420, 1428, 1440, 1446, 1456, 1462, 1464, 1465, 1476, 1480, 1488, 1496, 1528, 1530, 1536, 1538, 1540, 1542, 1544, 1552, 1560, 1582, 1584, 1600, 1612, 1616, 1624, 1632, 1638, 1640, 1648, 1656, 1664, 1666, 1672, 1680, 1684, 1692, 1696, 1700, 1708, 1716, 1720, 1724, 1732, 1736, 1744, 1746, 1753, 1760, 1768, 1792, 1800, 1804, 1812, 1820, 1848, 1860, 1864, 1872, 1876, 1900, 1904, 1912, 1920, 1921, 1923, 1924, 1928, 1930, 1936, 1940, 1952, 1960, 1968, 1972, 1980, 1984, 2016, 2032, 2040, 2044, 2048, 2056, 2080, 2100, 2108, 2112, 2128, 2132, 2136, 2142, 2146, 2176, 2184, 2188, 2192, 2196, 2200, 2210, 2212, 2232, 2236, 2240, 2244, 2245, 2248, 2260, 2272, 2284, 2288, 2296, 2304, 2308, 2312, 2316, 2320, 2328, 2332, 2340, 2346, 2356, 2368, 2380, 2400, 2410, 2416, 2440, 2448, 2456, 2460, 2464, 2470, 2472, 2480, 2482, 2494, 2496, 2506, 2512, 2520, 2522, 2524, 2548, 2560, 2564, 2570, 2572, 2576, 2584, 2590, 2600, 2604, 2620, 2624, 2640, 2648, 2652, 2656, 2684, 2688, 2689, 2692, 2702, 2704, 2716, 2720, 2728, 2730, 2752, 2770, 2772, 2788, 2800, 2812, 2816, 2842, 2856, 2860, 2880, 2892, 2896, 2910, 2912, 2920, 2928, 2938, 2952, 2956, 2968, 2976, 2992, 3010, 3016, 3020, 3026, 3036, 3040, 3052, 3054, 3060, 3068, 3072, 3076, ...
A162018: N such that 2↑↑N ≠ 22N mod N: 7, 9, 11, 13, 19, 21, 22, 23, 25, 27, 29, 31, 33, 35, 37, 38, 39, 41, 45, 47, 49, 50, 53, 54, 55, 57, 59, 61, 62, 63, 65, 66, 67, 69, 71, 73, 74, 75, 77, 79, 81, 82, 83, 86, 87, 89, 91, 92, 93, 94, 95, 97, 98, 99, 101, 103, 105, 106, 107, 108, 109, 110, 111, 113, 114, 115, 116, 117, 118, 119, 121, 122, 123, 125, 129, 131, 133, 134, 135, 137, 138, 139, 142, 143, 146, 147, 149, 150, 151, 152, 153, 154, 155, 157, 158, 159, 161, 162, 163, 165, 166, 167, 169, 171, 173, 174, 175, 177, 178, 179, 181, 183, 184, 185, 186, 187, 188, 189, 191, 193, 195, 197, 198, 199, 201, 202, 203, 205, 206, 207, 209, 211, 212, 213, 214, 215, 216, 217, 218, 219, 221, 222, 223, 225, 227, 228, 229, 230, 231, 233, 235, 236, 237, 239, 241, 242, 243, 245, 246, 247, 249, 250, 251, 253, 254, 258, 259, 261, 262, 263, 265, 266, 267, 268, 269, 270, 271, 273, 274, 275, 277, 278, 279, 281, 282, 283, 284, 285, 286, 287, 289, 290, 291, 293, 294, 295, 296, 297, 298, 299, 301, 302, 303, 305, 307, 309, 310, 311, 313, 314, 315, 317, 318, 319, 321, 322, 323, 324, 325, 326, 327, 329, 330, 331, 332, 333, 334, 335, 337, 338, 339, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 353, 354, 355, 357, 358, 359, 361, 362, 363, 365, 366, 367, 368, 369, 371, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 385, 387, 389, 391, 392, 393, 395, 397, 398, 399, 401, 402, 403, 404, 405, 407, 409, 410, 411, 412, 413, 414, 415, 417, 418, 419, 421, 422, 423, 425, 426, 427, 428, 429, 431, 432, 433, 434, 435, 437, 438, 441, 443, 444, 445, 446, 447, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 469, 470, 471, 472, 473, 474, 475, 477, 478, 479, 481, 483, 484, 485, 486, 487, 489, 491, 494, 495, 497, 498, 499, 500, 501, 502, 503, 505, 506, 507, 509, 511, 513, 515, 516, 517, 518, 519, 521, 522, 523, 524, 525, 526, 527, 529, 530, 531, 533, 534, 535, 538, 539, 540, 541, 542, 543, 545, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 561, 562, 563, 564, 566, 567, 569, 570, 571, 573, 574, 575, 577, 578, 579, 581, 583, 584, 585, 586, 587, 588, 589, 590, 591, 593, 594, 595, 596, 597, 598, 599, 601, 602, 603, 605, 606, 607, 608, 609, 610, 611, 613, 614, 615, 617, 618, 619, 621, 622, 623, 625, 626, 627, 629, 631, 632, 633, 634, 635, 636, 637, 638, 639, 642, 643, 644, 645, 647, 648, 649, 650, 651, 652, 653, 654, 655, 657, 659, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 673, 674, 675, 677, 678, ...
Similar Sequences
More sequences involving the ↑↑ operator and a relatively small modulus are A092188 and A094358.
Some other sequences are discussed here.
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2015 Jan 11.
s.27