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

## A sequence related to a conjecture of Schinzel

### Matthew M. Conroy 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 109, and various results of the calculation are given.

A consequence of an unproved conjecture of Schinzel 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 ; the values of p form sequence A062251). I have verified that q(n) exists for all n < 109.

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(103,q) v(104,q) v(105,q) v(106,q) v(107,q) v(108,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 < 109 (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 ) 102 427 0.607145 103 6680 0.500366 104 101494 0.496304 105 1354578 0.481517 106 17189068 0.473833 107 210240001 0.469208 108 2501065886 0.466024 109 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 pi (p1=2, p2=3, etc.) that need to be run through before n(pi+1)–1 is prime. Assuming the pi are small compared to n, the probability of n(pi+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 105 6881 -1.095330 0.792204 106 60547 -1.067996 0.836488 107 539273 -1.050424 0.869205 108 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.

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