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)/
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
(13) Show that
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) = 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.