# Sequence A094358, 2^^N ≡ 1 mod N

This sequence consists of all numbers N such that 2↑↑N ≡ 1 mod N.

2↑↑N, also written 2^{④}N, is a tower
of 2's N high, a very quickly-growing function given by Sloane's
A014221:

2↑↑0 = 1,

2↑↑1 = 2,

2↑↑2 = 2^{2} = 4,

2↑↑3 = 2^{22} = 16,

2↑↑4 = 2^{222} = 65536,

2↑↑5 = 2^{2222} ≈ 2.00353×10^{19728},

2↑↑6 = 2^{22222} ≈ 10^{6.03122×1019727},

and so on.

The definition of sequence A094358 states that N is in the sequence if 2↑↑N ≡ 1 mod N. For example, 3 is in the sequence because 2↑↑3 = 16, and 16 ≡ 1 mod 3.

Using the techniques described here it is easy to calculate the "remainder" M, the non-negative integer 0≤M<N such that ((2↑↑N)-M)/N is an integer. Thus it is easy to find those N for which M is 1, and thus 2↑↑N ≡ 1 mod N. For example, we can easily determine that 2↑↑15 ≡ 1 mod 15.

The sequence, Sloane's A094358, starts: 1, 3, 5, 15, 17, 51, 85, 255, 257, 641, 771, 1285, 1923, 3205, 3855, 4369, 9615, 10897, 13107, 21845, 32691, 54485, 65535, 65537, 114689, 163455, 164737, 196611, 274177, 319489, 327685, 344067, 494211, 573445, 822531, 823685, 958467, 974849, 983055, 1114129, 1370885, 1597445, 1720335, 1949713, 2424833, 2471055, 2800529, 2924547, 3342387, 4112655, 4661009, 4792335, 4874245, 5431313, 5570645, 5849139, 6700417, 7274499, 8401587, 9748565, 12124165, ...

As far as I've seen so far, each term is a squarefree product of terms in A023394, the prime factors of the Fermat numbers. The factorizations are:

3 (prime)

5 (prime)

15 = 3 × 5

17 (prime)

51 = 3 × 17

85 = 5 × 17

255 = 3 × 5 × 17

257 (prime)

641 (prime)

771 = 3 × 257

1285 = 5 × 257

1923 = 3 × 641

3205 = 5 × 641

3855 = 3 × 5 × 257

4369 = 17 × 257

9615 = 3 × 5 × 641

10897 = 17 × 641

13107 = 3 × 17 × 257

21845 = 5 × 17 × 257

32691 = 3 × 17 × 641

54485 = 5 × 17 × 641

65535 = 3 × 5 × 17 × 257

65537 (prime)

114689 (prime)

163455 = 3 × 5 × 17 × 641

164737 = 257 × 641

196611 = 3 × 65537

274177 (prime)

319489 (prime)

327685 = 5 × 65537

344067 = 3 × 114689

494211 = 3 × 257 × 641

573445 = 5 × 114689

822531 = 3 × 274177

823685 = 5 × 257 × 641

958467 = 3 × 319489

974849 (prime)

983055 = 3 × 5 × 65537

1114129 = 17 × 65537

1370885 = 5 × 274177

1597445 = 5 × 319489

1720335 = 3 × 5 × 114689

1949713 = 17 × 114689

2424833 (prime)

2471055 = 3 × 5 × 257 × 641

2800529 = 17 × 257 × 641

2924547 = 3 × 974849

3342387 = 3 × 17 × 65537

4112655 = 3 × 5 × 274177

4661009 = 17 × 274177

4792335 = 3 × 5 × 319489

4874245 = 5 × 974849

5431313 = 17 × 319489

5570645 = 5 × 17 × 65537

5849139 = 3 × 17 × 114689

6700417 (prime)

7274499 = 3 × 2424833

8401587 = 3 × 17 × 257 × 641

9748565 = 5 × 17 × 114689

12124165 = 5 × 2424833

(...)

At first I thought that the sequence was related to A058910 (because of its definition, being a large power of 2 mod N for some large N). The sequence is also similar to A001317 and A004729, until we get to 641. The appearance of 641 is what tipped me off to a possible link with the Fermat factors.

Some other sequences I have investigated are discussed here.

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