Question

Let π(N) be the number of primes less than or equal to N (example: π(100) = 25). The famous prime number theorem then states (with ∼ meaning asymptotically equal):

Proving this theorem is very hard. However, we can derive a statistical form of the prime number theorem. For this, we consider random primes which are generated as follows:
(i) Create a list of consecutive integers from 2 to N.
(ii) Start with 2 and mark every number > 2 with a probability of .
(iii) Let n be the next non-marked number. Mark every number > n with a probability of .
(iv) Repeat (iii) until you have reached N.
All the non-marked numbers in the list are called random primes.
(a) Let qn be the probability of n being selected as a random prime during this algorithm. Find an expression for qn in terms of qn−1.
(b) Prove the following inequality of qn and qn+1:

(c) Use the result from (b) to show this inequality:

(d) With this result, derive an asymptotic expression for qn in terms of n.
(e) Let ˜π(N) be the number of random primes less than or equal to N. Use the result from (d) to derive an asymptotic expression for ˜π(N), i.e. the prime number theorem for random primes.

Answer 1

Answer:

Let π(N) be the number of primes less than or equal to N (example: π(100) = 25). The famous

prime number theorem then states (with ∼ meaning asymptotically equal):

π(N) ∼

N/log(N)

Proving this theorem is very hard. However, we can derive a statistical form of the prime

number theorem. For this, we consider random primes which are generated as follows:

(i) Create a list of consecutive integers from 2 to N.

(ii) Start with 2 and mark every number > 2 with a probability of 1/2

.

(iii) Let n be the next non-marked number. Mark every number > n with a probability of 1/n

.

(iv) Repeat (iii) until you have reached N.

Answer 2

i did gate you, where is the answer please?