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 sufficiently large.
Previous Page Next Page