Theorems of Golomb and Dasgupta

Thomas R. Nicely

http://www.trnicely.net
Current e-mail address

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.