Related Collections

More Stage 5 Students Articles

Fixing It

A and B are two fixed points on a circle and RS is a variable diamater. What is the locus of the intersection P of AR and BS?

Pericut

Two semicircle sit on the diameter of a semicircle centre O of twice their radius. Lines through O divide the perimeter into two parts. What can you say about the lengths of these two parts?

OK! Now Prove It

Make a conjecture about the sum of the squares of the odd positive integers. Can you prove it?

2^n -n Numbers

Stage: 5

Article by Yatir Halevi

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:

$$ \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} $$

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	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	Probable
3415	2 ³⁴¹⁵ -3415	Probable
4185	2 ⁴¹⁸⁵ -4185	Probable
7353	2 ⁷³⁵³ -7353	Probable
12213	2 ¹²²¹³ -12213	Probable
60975	2 ⁶⁰⁹⁷⁵ -60975	Probable
61011	2 ⁶¹⁰¹¹ -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 mod (p-1) $ (the remainder that we get when dividing $ n $ by $ (p-1) $ ).

If $ 2^r = n mod 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. If you find anything interesting (not-interesting is also good) about these numbers don't hesitate to send me an email: yatir@bigfoot.com

[Yatir Halevi is 17 years old, he lives in Maccabim, Israel and goes to the Maccabim-Reut High-School].

Making and proving conjectures. Modulus arithmetic. Interactivities. Geometric sequence. Number theory. Mathematical reasoning & proof. Recurrence relations. Fibonacci sequence. Summation of series. Generalising.

Related Collections

You may also like

Fixing It

Pericut

OK! Now Prove It

2^n -n Numbers

Stage: 5