Thomas R. Nicely

Current e-mail address

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.