34 1. Arithmetic Functions

(10) Counting prime factors without multiplicity, show that for every integer

n ≥ 2 there is some integer n with n n 2n so that n and n have

the same number of prime factors.

(11) Use divisibility properties of the factorial to show that the sequence of

primes has unbounded gaps. Then use a Chebyshev-type estimate to

find a constant c 0 so that there exist arbitrarily large pairs pk,pk+1

of consecutive primes with pk+1 − pk ≥ c log(pk).

(12) † a) Compute the normalized differences (pk+1 − pk)/ log(pk) of pairs

pk,pk+1 of successive primes in intervals

(1000, 2000], (10000, 11000], (100000, 101000], (1000000, 1001000].

Sort and plot the normalized differences on each interval. Comment on:

(i) the family resemblance of the various plots disregarding scale, (ii)

the shape of the plots with special attention to the prevalence of small

and large differences, and (iii) lack of “smoothness” of the plots.

b) Compute ratios (pk+1 − pk)/

log2(pk)

to investigate an old conjecture

of C. H. Cram´ er to the effect that this ratio is bounded. Since extreme

values of the difference pk+1 −pk are sought, the computational strategy

should be different from part a). Determine approximately the largest

prime for which the time involved in computing the ratio is 1/10 of a

second, and calculate a thousand ratios for randomly chosen and well

scattered primes of about the same order of magnitude. Sort and plot

the ratios as in a). (Here a computer algebra system is needed, or else

some programming. In the latter case, Prime Numbers. A computa-

tional perspective by Richard Crandall and Carl Pomerance, or Prime

numbers and computer methods for factorization by Hans Riesel, may

prove helpful.)

(13) Show that

p≤n

p ≤

5n

for all n ≥ 1. According to P. Erd¨ os and L. Kalm´ ar one can take 4 in

the inequality, and according to D. Hanson one can take 3.

(14) a) Let Ax = (x/2,x] ∪ (x/4,x/3] ∪ (x/6,x/5] ∪ · · · . Show that

n∈Ax

Λ(n) = log(2)x + O(log(x)),

and that the error term cannot be improved.

b) Deduce that the interval (x/2,x] contains at least x/(5 log(x)) primes

for all x suﬃciently large.