# The distribution of pow(2, n, n)

For a positive integer ${n}$ let ${f(n)}$ be the remainder of the division of ${2^n}$ by ${n}$. 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, ${f(n)=0}$ if and only if ${n}$ is a power of ${2}$. It also looks like ${f}$ is always even, with powers of 2 dominating the list of its values. But ${f}$ 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 ${f}$ consists of all nonnegative integers except 1. Here is a proof that ${f(n)\ne 1}$, provided by Max Alexeyev on the OEIS page for A036236

Suppose ${2^n \equiv 1 \bmod n}$ for some ${n>1}$. Let ${p}$ be the smallest prime divisor of ${n}$. Then ${2^n\equiv 1 \bmod p}$. This means that the order of ${2}$ in the multiplicative group ${(\mathbb Z/ p \mathbb Z)^*}$ is a divisor of ${n}$. But this group has ${p-1}$ elements, and the only divisor of ${n}$ that is smaller than ${p}$ is ${1}$. Thus, the order of ${2}$ is ${1}$, which means ${2\equiv 1 \bmod p}$, which is absurd.

The fact that the smallest ${n}$ with ${f(n) = 3}$ is 4700063497 deserves to be mentioned here. But I would like to consider the most frequent values of ${f}$ 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 ${10^8k}$ integers with ${k=1, 2, 3, 4, 5, 6}$. 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 ${n = 2p}$ with ${p}$ 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 ${n=2k}$ is even, we are computing ${4^k \bmod 2k}$ and that is likely to be a power of ${4}$. This boosts the frequency of the even (generally, composite) powers of 2 in the sequence.

This site uses Akismet to reduce spam. Learn how your comment data is processed.