For a positive integer let be the remainder of the division of by . This is conveniently computed in Python as pow(2, n, n). For example, the first 20 values are returned by

[pow(2, n, n) for n in range(1, 21)]

and they are:

[0, 0, 2, 0, 2, 4, 2, 0, 8, 4, 2, 4, 2, 4, 8, 0, 2, 10, 2, 16]

Obviously, if and only if is a power of . It also looks like is always even, with powers of 2 dominating the list of its values. But does take on odd values, although this does not happen often: only 6 times in the first 100 integers.

[(n, pow(2, n, n)) for n in range(1, 101) if pow(2, n, n) % 2]

returns

[(25, 7), (45, 17), (55, 43), (91, 37), (95, 13), (99, 17)]

It is conjectured that the range of consists of all nonnegative integers except 1. Here is a proof that , provided by Max Alexeyev on the OEIS page for A036236

Suppose for some . Let be the smallest prime divisor of . Then . This means that the order of in the multiplicative group is a divisor of . But this group has elements, and the only divisor of that is smaller than is . Thus, the order of is , which means , which is absurd.

The fact that the smallest with is 4700063497 deserves to be mentioned here. But I would like to consider the most frequent values of instead. Experimentally, they are found like this:

from collections import Counter freq = Counter(pow(2, n, n) for n in range(1, 100000000 + 1)) print(freq.most_common(20))

which prints 20 pairs (value, frequency):

(2, 5763518), (4, 3004047), (8, 2054167), (16, 1569725), (64, 1076293), (256, 824438), (512, 737450), (1024, 668970), (32, 638063), (4096, 569705), (128, 466015), (65536, 435306), (262144, 389305), (1048576, 351723), (2097152, 326926), (16384, 246533), (16777216, 243841), (32768, 232037), (2048, 153537), (8192, 131614)

These are all powers of 2… but not exactly in the order one might expect. I repeated the experiment for the first integers with . The frequency order remained stable at the top. These are the most common 11 values, with their frequency (in %) listed for the aforementioned six ranges.

2, [5.8, 5.5, 5.4, 5.3, 5.3, 5.2] 4, [3.0, 2.9, 2.8, 2.8, 2.7, 2.7] 8, [2.1, 2.0, 1.9, 1.9, 1.9, 1.8] 16, [1.6, 1.5, 1.5, 1.4, 1.4, 1.4] 64, [1.1, 1.0, 1.0, 1.0, 1.0, 1.0] 256, [0.8, 0.8, 0.8, 0.8, 0.7, 0.7] 512, [0.7, 0.7, 0.7, 0.7, 0.7, 0.7] 1024, [0.7, 0.6, 0.6, 0.6, 0.6, 0.6] 32, [0.6, 0.6, 0.6, 0.6, 0.6, 0.6] 4096, [0.6, 0.5, 0.5, 0.5, 0.5, 0.5] 128, [0.5, 0.4, 0.4, 0.4, 0.4, 0.4]

It seems that 32 and 128 are consistently less common than one might expect.

The most common value, 2, is contributed by primes and pseudoprimes to base 2. The value of 4 appears when with prime (but not only then). Still, the primes having zero density makes it difficult to explain the frequency pattern based on primality. A more convincing reason could be: when is even, we are computing and that is likely to be a power of . This boosts the frequency of the even (generally, composite) powers of 2 in the sequence.