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

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⁹, 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⁹.

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

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).

This table is complete for n < 10⁹ (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:

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₁=2, p₂=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:

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

References

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