Copyright © University of Cambridge. All rights reserved.
This article is about $ 2^n-n $ numbers, that is, numbers that are produced by replacing '$n$' in $ 2^n-n $ with a positive integer $ (1,2,3...) $. I came across these numbers while studying Mersenne numbers $ (2^n-1) $. It got me thinking about $ 2^n-n $ numbers, if there are any interesting properties to them, and what are the properties of their primes. In the rest of the article $A_n$ will
mean $ 2^n-n $. The first few numbers are:
| n |
A n |
| 1 |
1 |
| 2 |
2 |
| 3 |
5 |
| 4 |
12 |
| 5 |
27 |
| 6 |
58 |
| 7 |
121 |
| 8 |
248 |
| 9 |
503 |
| 10 |
1014 |
The first question that one would ask himself is how could I advance from $ A_n $ to $ A_{n+1} $, that is, if I'm given $ A_n $, how would I find $ A_{n+1} $ without needing to calculate $ 2^n-n $. In order to find this one might notice the following:
$ A_1=1 $
$ A_2=2\times 1+0=2 $
$ A_3=2\times 2+1=5 $
$ A_4=2\times 5+2=12 $
That would lead us to the following theorem:
Theorem 1
The rule of advancement is:
$ A_{n+1}=2A_n+n-1 $
Proof
To prove this, we will have to show that when we take $ A_n $ multiply it by $2$ add $n$ and subtract $1$ we get $ A_{n+1}$:
$ 2A_n+n-1=2(2^n-n)+n-1=2^{n+1}-n-1=2^{n+1}-(n+1)=A_{n+1} $
Q.E.D.
The next demanding thing to do is to find the sum of the series, the sum of all the members of the series up till a certain '$n$'.
Theorem 2
The sum of the series $ A_n $ will be defined as $ S_n $.
$$ S_n = 1+2+5+12+ \cdots +(2^n - n)= \frac{2^{n+2} - n^2 - n - 4}{2} $$
I will prove that this formula is correct, however that manner in which I got to it, I will leave to the reader to discover (it is not difficult).
Proof
I will prove by induction on '$n$'.
First lets check for the case in which $n=1$: $$ S_1 = \frac{2^3 - 1^2 -1 -4}{2} = \frac{8-1-1-4}{2}= \frac{2}{2} = 1 $$
Which is obviously correct.
Assumption: $ n=k $, a certain integer.
$$ 1+2+5+12+ \cdots +(2^k - k) = \frac{2^{k+2} - k^2 - k - 4}{2} $$
Next we have to prove that it is also true for $ n=k+1$:
$$ 1+2+5+12+ \cdots +(2^k - k) + (2^{k+1} - (k+1))= \frac{2^{(k+1)+2} - (k+1)^2 - (k+1) - 4}{2} $$
By our assumption we know that:
$$ 1+2+5+12+ \cdots +(2^k - k) = \frac{2^{k+2} - k^2 - k - 4}{2} $$
Substituting it and opening it up, we get:
$$\begin{align*} \frac{2^{k+2} - k^2 - k - 4}{2} + 2^{k+1}- (k+1) &= \frac{2^{k+2} - k^2 - k - 4 + 2^{k+2} - 2k -2}{2} \\ &= \frac{2^{k+3} - k^2 - 3k - 6}{2} &= \frac{2^{k+3} - (k+1)^2 - (k+1) - 4}{2} \end{align*}$$
Q.E.D.
Thus, it is proven for all positive integers.
After finding these basic and essential formulas that one must find for any series of numbers, we may go on to the interesting part.
First, notice that the difference between two consecutive members of the series is a Mersenne number:
$ A_{n+1} - A_n =M_n $
Where $ M_n $ signifies the nth Mersenne number.
I will leave this easy proof to the reader.
The major research on series of numbers like the Fermat numbers $ (2^{2^n} + 1) $ or the Mersenne numbers $ (2^n-1) $ is done on finding prime numbers (numbers that their only divisors are 1 and the number itself, 1 is not prime number by definition) and primality testing for their members.
The prime numbers in the form of $ 2^n-n $ that I found using my computer are (some are not definite but probable primes, because my computer wasn't strong enough to reach a concrete conclusion):
| n |
2 n -n |
Definite/Probable Prime |
| 2 |
2 |
Definite |
| 3 |
5 |
Definite |
| 9 |
503 |
Definite |
| 13 |
8179 |
Definite |
| 19 |
524269 |
Definite |
| 21 |
2097131 |
Definite |
| 55 |
36028797018963913 |
Definite |
| 261 |
2 261 -261 |
Probable |
| 3415 |
2 3415 -3415 |
Probable |
| 4185 |
2 4185 -4185 |
Probable |
| 7353 |
2 7353 -7353 |
Probable |
| 12213 |
2 12213 -12213 |
Probable |
| 60975 |
2 60975 -60975 |
Probable |
| 61011 |
2 61011 -61011 |
Probable |
Here are a few interesting theorems regarding the prime numbers of this form:
Theorem 3
For $ 2^n-n $ primes that are greater from $ 2, n $ must be odd.
Proof
$ 2^n $ is always even, so we must only consider $ n$.
If $ n $ is even: even minus even is even.
If $ n $ is odd: even minus odd is odd.
$ 2 $ is the only even prime number (if there would have been another one, it could be divided by $ 2 $ and therefore not a prime number), so for all prime numbers of this form, $ n $ must be odd, because we want $ A_n $ to be odd as well.
Q.E.D.
Theorem 4
If $ p \mid n $ ($ p $ divides $ n $ ), where $ p $ is an odd prime number $ (p\neq2) $ , then $ p $ doesn't divide $ 2^n - n $.
Proof
Let's consider the opposite and then try to prove by reaching a contradiction.
Suppose $ p \mid 2^n -n $. As $ p \mid n $ we see that $ p \mid(2^n -n) + n = 2^n $ and hence $ p=2 $ . BUT $p\neq2$ according to our theorem. Hence a contradiction, ergo $ p $ does not divide $ 2^n- n$. Q.E.D.
Theorem 4 is a very important theorem, since it gives us a useful tool for marking out those primes who do not divide $ 2^n-n $. The basic way of finding if a certain number '$m$' is a prime number, is if every number from $ 2 $ to the square-root of '$m$' does not divide '$m$'. Theorem 4 allows us to mark out those primes that divide '$n$', because we know for sure that they wont divide $
2^n-n $.
There is an easy algorithm that can be used when we want the check if a certain prime divides $ A_n $:
Given $ 2^n-n $ and a prime, $ p> 2. $
Change $ 2^n $ to $ 2^r $ , where $ r $ is: $ n \bmod (p-1) $ (the remainder that we get when dividing $ n $ by $ (p-1) $ ).
If $ 2^r \equiv n \pmod{p}$ , then $ p \mid ( 2^n-n). $
Using Fermat's little theorem one can easily prove this algorithm. The readers who are familiar with this theorem may go ahead and prove it.
Are there infinity prime numbers of the form $ 2^n-n$?
Probably yes.
The proof for this is rather advanced so I will only sketch the proof.
The probability for a certain number to be prime is: $$ \frac{1}{\log(2^n-n)} $$
for a large $ n $. Taking the harmonic series: $$ \sum_{n=1}^{\infty} \frac{1}{\log(2^n-n)} $$ one will the see that the harmonic series diverges and therefore there are, probably, infinity number of primes of this form.
There are certainly much more that can be found about this sort of numbers, and especially about their primes, but unfortunately like all good things, this article must come to an end. I urge the reader to try to investigate these numbers.