## Theorems of Golomb and Dasgupta Thomas R. Nicely

Freeware copyright © 2010 Thomas R. Nicely. Released into the public domain by the author, who disclaims any legal liability arising from its use.

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
=======================================================
```

### RELATED CONJECTURES

Wouter van Doorn proposes (20 May 2010) the following additional conjectures.

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.