Journal of Integer Sequences, Vol. 4 (2001), Article 01.1.7 |

5212 Ravenna Avenue NE, Apt. #8

Seattle, WA 98105, USA

Email: doctormatt@earthlink.net

**Abstract**: It would follow from a conjecture of Schinzel that all
positive integers are representable as (p+1)/(q+1)
with q and p prime. This conjecture is verified to 10^{9}, and
various results of the calculation are
given.

A consequence of an unproved conjecture of Schinzel[1] is
that every positive integer n can be represented as n=(p+1)/(q+1),
with p and q prime.
For n a positive integer,
define the function q(n) to be the smallest prime q such that
n(q+1)-1 is prime.
In other words, let q(n) be the smallest prime q
so that n has a representation n=(p+1)/(q+1) with p prime.
The sequence q(n) begins 2,2,3,2,3,2,5,2,5,2,3,3,7
(sequence A060324 in [2]; the values of p form
sequence A062251).
I have verified that q(n) exists for all n < 10^{9}.

Generally, q(n) is quite a small prime. For example, letting v(x,q) = #{ n <= x : q=q(n) }, we have, for q <= 31:

q |
v(10^{3},q)
| v(10^{4},q) |
v(10^{5},q) |
v(10^{6},q) |
v(10^{7},q) |
v(10^{8},q) |

2 | 222 | 1634 | 13026 | 108476 | 929119 | 8126474 |

3 | 223 | 1796 | 14962 | 128051 | 1117099 | 9903208 |

5 | 236 | 2085 | 18339 | 162796 | 1456211 | 13149129 |

7 | 93 | 971 | 9276 | 86491 | 800838 | 7418842 |

11 | 102 | 1095 | 11324 | 109516 | 1041573 | 9838207 |

13 | 35 | 524 | 6045 | 62243 | 617983 | 6044694 |

17 | 31 | 522 | 6204 | 66859 | 685210 | 6830034 |

19 | 13 | 261 | 3349 | 38962 | 420793 | 4369435 |

23 | 20 | 316 | 4097 | 46593 | 501096 | 5181342 |

29 | 12 | 261 | 3839 | 46723 | 520540 | 5518907 |

31 | 2 | 67 | 1039 | 14343 | 176355 | 1986081 |

Notice that, for a fixed x, v(x,q) to some extent reflects the number of prime factors of q+1. This makes sense, since the more prime factors q+1 has, the more likely it is that (q+1)n –1 is prime.

The following table gives the maximal values for q(n) (that is, values of n for which q(n') < q(n) for every n' < n).

n | q(n) | (log q(n))/(log n) | (log q(n))/(log log n) |

1 | 2 | - | - |

3 | 3 | 1. | 11.681421 |

7 | 5 | 0.827087 | 2.417554 |

13 | 7 | 0.758654 | 2.065856 |

31 | 13 | 0.746930 | 2.079033 |

51 | 19 | 0.748873 | 2.150632 |

101 | 23 | 0.679396 | 2.050230 |

146 | 41 | 0.745158 | 2.31209 |

311 | 71 | 0.742654 | 2.439409 |

1332 | 109 | 0.65208 | 2.377403 |

2213 | 179 | 0.673502 | 2.540976 |

6089 | 239 | 0.62845 | 2.529593 |

10382 | 269 | 0.604976 | 2.515168 |

11333 | 347 | 0.62657 | 2.618528 |

32003 | 353 | 0.56552 | 2.507828 |

83633 | 443 | 0.537627 | 2.509889 |

143822 | 503 | 0.52378 | 2.513829 |

176192 | 509 | 0.51596 | 2.501489 |

246314 | 617 | 0.517535 | 2.550711 |

386237 | 641 | 0.502404 | 2.530107 |

450644 | 701 | 0.503325 | 2.553224 |

1198748 | 773 | 0.475129 | 2.520164 |

2302457 | 881 | 0.462887 | 2.526093 |

5513867 | 971 | 0.443112 | 2.508225 |

9108629 | 977 | 0.429616 | 2.481671 |

11814707 | 1013 | 0.424976 | 2.480318 |

16881479 | 1019 | 0.416217 | 2.463297 |

18786623 | 1103 | 0.418290 | 2.485805 |

24911213 | 1109 | 0.411678 | 2.473069 |

28836722 | 1223 | 0.413867 | 2.500039 |

34257764 | 1559 | 0.423749 | 2.576361 |

196457309 | 1607 | 0.386581 | 2.502859 |

238192517 | 1709 | 0.385910 | 2.515164 |

482483669 | 1889 | 0.377295 | 2.518416 |

750301568 | 2063 | 0.373455 | 2.529388 |

This table is complete for n < 10^{9}
(the first two colums are sequences A060424 and A062252;
the corresponding values of p give A062256).
The fact that the maximal values of q(n) are so small (apparently less
than log n to a fixed power) is
supportive of the conjecture that it is always defined.
Indeed, on average q(n) was found to be quite a bit smaller.
Let Q(x) be the sum of q(n) for all n <= x.
We have the following table:

x | Q(x) | Q(x)/(x log x log log x ) |

10^{2} | 427 | 0.607145 |

10^{3} | 6680 | 0.500366 |

10^{4} | 101494 | 0.496304 |

10^{5} | 1354578 | 0.481517 |

10^{6} | 17189068 | 0.473833 |

10^{7} | 210240001 | 0.469208 |

10^{8} | 2501065886 | 0.466024 |

10^{9} | 29118770352 | 0.463545 |

A heuristic argument can be given to explain the behavior
seen in this table. We can think of q(n) as representing
the k-th prime, where k is the number of primes p_{i}
(p_{1}=2, p_{2}=3, etc.)
that need to be run through before
n(p_{i}+1)–1 is prime. Assuming the p_{i} are
small compared
to n, the probability of n(p_{i}+1)–1 being prime is about
1/log n. Hence we expect to need to run through about
log n primes. Since the log
of the n-th prime is roughly
log n log log n, we can expect q(n) to be about log n log log n
on average.

Finally, let s(x) be the number of n <= x for which q(n) = q(n-1). We have the following table:

x | s(x) | (log(s(x)/x))/(log log x) | (s(x) log x)/ x |

10^{5} | 6881 | -1.095330 | 0.792204 |

10^{6} | 60547 | -1.067996 | 0.836488 |

10^{7} | 539273 | -1.050424 | 0.869205 |

10^{8} | 4874595 | -1.036952 | 0.897934 |

The two right-hand columns both indicate the same thing: that s(x) appears to be approximately x/log x.

1. A. Schinzel and W. Sierpinski, Sur certaines hypothèses
concernant les nombres premiers,
*Acta Arithmetica* **4** (1958), 185-208

2. N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at www.research.att.com/~njas/sequences/.

(Concerned with sequences A060324, A060424, A062251, A062252, A062256 .)

Received March 29, 2001; published in Journal of Integer Sequences July 5, 2001.

Return to
**Journal of Integer Sequences home page**