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.

Immaculate perfection

— I am so lucky. I was born on April 4th 1944, that’s 4/4/44. If you add that up, it comes to 16, one six. One plus six is seven: luckiest number of all.
— You know your math.
— It’s more than math, Mike, it’s… immaculate perfection.

The value of 7 for the the digital root indeed seems preferable, at least on this blog. But looking at the dates formed by repeated digits is too anthropocentric (not to mention xkcd1179). Besides, mathematics already has a concept of perfect numbers: being equal to the sum of proper divisors.

So, are there any perfect numbers with digital root equal to 7, equivalently {n\equiv 7\bmod 9}? For even perfect numbers, one can expect that the Euclid-Euler theorem {n = 2^{p-1} (2^p-1)} will help with the answer, but even so, the solution turns out to be surprisingly simple.

A lucky coincidence is that {2^6\equiv 1\bmod 9} ({64 = 1 + 7\cdot 9}). Since all primes greater than 3 have remainder 1 or 5 mod 6, there are only a few cases to check:

  • {p\equiv 1\bmod 6}, hence {2^{p-1}\equiv 2^{1-1} \equiv 1 \bmod 9} and {2^p-1\equiv 2^1-1 \equiv 1\bmod 9}. In this case {n\equiv 1\cdot 1 \equiv 1 \bmod 9}
  • {p\equiv 5\bmod 6}, hence {2^{p-1}\equiv 2^{5-1} \equiv 7 \bmod 9} and {2^p-1\equiv 2^5-1 \equiv 4\bmod 9}. In this case {n\equiv 7\cdot 4 \equiv 1 \bmod 9}
  • Exceptional cases p=2, 3 correspond to n = 6, 28. The latter is congruent to 1 mod 9, matching the preceding cases.

So, every even perfect number except 6 is congruent to 1 mod 9. Should a perfect number be congruent to 7 mod 9, it has to be odd. An odd perfect number, should it exist, must be either divisible by 9 (not good for us) or congruent to 1 mod 12. (Reference: On the form of an odd perfect number). The condition {n\equiv 1 \bmod 12} is consistent with {n\equiv 7 \bmod 9}: for example, 25 satisfies both. Come to think of it, the sum of proper divisors of 25 is… not 25. But there might still be a 7 mod 9 perfect number out there.

What numbers k have the property that the sequence {n mod k : n is perfect} stabilizes? Assuming odd perfect numbers do not exist, every power of 2 has this property. So do 3 and 9 by the above (and therefore, their products with powers of 2). I don’t know any other such k, in particular n mod 27 does not appear to stabilize. Of course, it is impossible to prove any negative result here since we don’t know if there are infinitely many perfect numbers.