Thomas R. Nicely
Last updated 0620 GMT 21 May 2010 (originally posted 6 September 2005).
Anirban Dasgupta (Purdue University) attributes to Solomon W. Golomb the conjecture that for every integer k > 1, n/pi(n) = k for some integer n > 1. Here pi(n) is the prime counting function, the count of prime numbers <= n. The proof of this conjecture is presented below.
By analogy, Dasgupta conjectured that for every integer k > 2, n/pi_2(n) = k for some integer n > 2. Here pi_2(n) is the twin-prime counting function, the count of twin-prime pairs (q, q+2) such that q is prime, q+2 is prime, and q <= n. The proof of this conjecture parallels the proof of Golomb's conjecture, presented below.
Wouter van Doorn has devised a proof of Golomb's conjecture, which immediately provides a template for a proof of Dasgupta's (and similar) conjectures as well. Van Doorn transmitted his results to me via e-mail on 17/18 May 2010. Following is his proof of Golomb's conjecture, including some of my own minor editing and elaboration of detail.
Let k be any given integer > 1. Let M be the largest integer for which: M/pi(M) < k. Such an M must exist for every k > 1; for let S be the set of integers (n > 1) for which n/pi(n) < k. S is not empty, since 3/pi(3) < 2 <= k. Furthermore, S is bounded above, because lim(n/pi(n), n->+infinity) is known to be +infinity; thus there must exist an integer N such that n/pi(n) > k for all n > N. Since S is bounded above and non-empty, it has a largest element M, and thus M is the largest integer for which M/pi(M) < k. Then it must furthermore follow that (M+1)/pi(M+1)=k. For if this is not so, then as a consequence of the definition of M, (M+1)/pi(M+1) > k. Multiplying by pi(M+1), we then have: M+1 > k*pi(M+1) >= k*pi(M) > M where the ">=" is implied by the monotonic non-decreasing property of pi(n), and the second ">" is implied by the definition of M. Thus the integer k*pi(M+1) would fall strictly between the successive integers M and M+1, which is impossible. Thus if k is an integer > 1, there always exists an integer M such that (M+1)/pi(M+1)=k, and Goulomb's conjecture is proven. To produce a proof of Dasgupta's conjecture for twin-prime pairs, replace pi(x) by pi_2(x); the hypothesis k > 1 by k > 2; and the inequalities 3/pi(3) < 2 <= k by 5/pi_2(5) < 3 <= k. Similar results then follow for the other prime constellations; for example, for the prime quadruplets (q, q+2, q+6, q+8), replace pi(x) by pi_4(x); replace the hypothesis k > 1 by k > 4; and replace the inequalities 3/pi(3) < 2 <= k by 5/pi_4(5) < 6 <= k (note that the case k=5 must be handled individually). For the triplets (q, q+4, q+6), the new hypothesis becomes k > 6 and the inequalities are 13/pi_3b(13) < 7 <= k.There follow some limited computational examples, generated by the author, in illustration of these two theorems.
In the first table, the third and fourth columns display the smallest and largest values obtained for n, such that n/pi(n) = k, where k is given in the first column. The second column gives the total number N of distinct values of n for which n/pi(n) = k.
=======================================================
GOLOMB'S THEOREM
=======================================================
k N n_min n_max
=======================================================
2 4 2 8
3 3 27 33
4 3 96 120
5 6 330 360
6 7 1008 1134
7 6 3059 3094
8 6 8408 8472
9 3 23526 24300
10 9 64540 64720
=======================================================
In the second table, the third and fourth columns display the
smallest and largest values obtained for n, such that n/pi_2(n) = k,
where k is given in the first column. The second column gives the
total number N of distinct values of n for which n/pi_2(n) = k.
=======================================================
DASGUPTA'S THEOREM
=======================================================
k N n_min n_max
=======================================================
3 2 3 6
4 3 4 12
5 3 10 20
6 2 24 30
7 3 28 42
8 2 40 48
9 3 54 72
10 2 70 80
11 2 88 110
12 2 96 120
13 3 130 156
14 4 168 210
15 4 225 285
16 2 304 320
17 2 340 357
18 1 378 378
19 2 399 437
20 2 460 480
21 2 504 525
22 3 550 660
23 2 598 690
24 1 720 720
25 1 750 750
26 2 780 910
27 1 945 945
28 3 980 1120
29 4 1015 1334
30 3 1260 1500
31 2 1426 1550
32 6 1600 2144
33 11 1848 2343
34 1 2448 2448
35 3 2520 2730
36 1 2880 2880
37 4 2960 3589
38 11 3116 4370
39 4 4719 4836
40 1 5160 5160
41 5 5371 5699
42 1 6006 6006
43 6 6407 6966
44 2 7172 7216
45 2 7740 7785
46 2 8142 8234
47 1 8695 8695
48 5 9216 9552
49 1 10633 10633
50 2 11050 11300
51 8 11679 12291
52 1 12688 12688
53 1 13144 13144
54 6 13554 14634
55 1 14960 14960
56 4 15512 15792
57 5 16587 18411
58 2 18850 18966
59 16 20355 23069
60 1 24240 24240
61 1 24766 24766
62 4 25792 26040
63 5 26649 28854
64 2 29824 29888
65 16 31070 35165
66 1 36630 36630
67 9 38324 39396
68 2 40392 40460
69 2 42987 43056
70 1 45500 45500
71 12 47286 50339
72 5 52848 53640
73 8 55188 56940
74 4 60014 60310
75 5 61950 62325
76 4 64448 64676
=======================================================
1) For each positive integer m, there exists an integer k, such that n/pi(n) = k has at least m distinct integer solutions n.
2) For each positive integer m, there exist infinitely many distinct integers k, such that n/pi(n) = k has exactly m distinct integer solutions n.
Parallel versions of these conjectures may be formulated for other prime constellations, e.g., for the twin-prime pairs by replacing pi(n) with pi_2(n).
Van Doorn is of the opinion that (1) is valid, but considers (2) to be questionable. I have generated numerical evidence in regard to (2) by calculating n/pi(n) up to n=2^32=4294967296. The results are as follows.
============ k m ============ 2 4 3 3 4 3 5 6 6 7 7 6 8 6 9 3 10 9 11 1 12 18 13 11 14 12 15 21 16 3 17 10 18 33 19 31 20 32 21 24 ============Here m is the number of distinct values of n (n <= 2^32) found for which n/pi(n)=k. No instance of k has been found for which m=2, m=5, or m=8, and only one for which m=1 (k=11 when n=175197). Thus the numerical results to 2^32 provide no strong evidence in support of (2); but it may be necessary to proceed to a much greater upper bound to obtain significant results, and in any case computational results alone will not provide a proof or disproof. The calculations do verify (1) for 1 <= m <= 33.