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). /p table border=1 align="center" tr td n /tdtdfont size="-1" q(n) /tdtdfont size="-1" (log q(n))/(log n) /td tdfont size="-1"(log q(n))/(log log n) /tr trtdfont size="-1" 1 /tdtdfont size="-1" 2 /tdtdfont size="-1" - /tdtdfont size="-1"- /tr trtdfont size="-1"3 /tdtdfont size="-1" 3 /tdtdfont size="-1" 1. /tdtdfont size="-1"11.681421 /tr tr tdfont size="-1"7 /tdtdfont size="-1" 5 /tdtdfont size="-1" 0.827087 /tdtdfont size="-1"2.417554 /tr trtdfont size="-1" 13 /tdtdfont size="-1" 7 /tdtdfont size="-1" 0.758654 /tdtdfont size="-1" 2.065856 /tr tr tdfont size="-1"31 /tdtdfont size="-1" 13 /tdtdfont size="-1" 0.746930 /tdtdfont size="-1" 2.079033 /tr tr tdfont size="-1"51 /tdtdfont size="-1" 19 /tdtdfont size="-1" 0.748873 /tdtdfont size="-1" 2.150632 /tr trtd font size="-1"101 /tdtdfont size="-1" 23 /tdtdfont size="-1" 0.679396 /tdtdfont size="-1" 2.050230 /tr tr tdfont size="-1"146 /tdtdfont size="-1" 41 /tdtdfont size="-1" 0.745158 /tdtdfont size="-1" 2.31209 /tr trtd font size="-1"311 /tdtdfont size="-1" 71 /tdtdfont size="-1" 0.742654 /tdtdfont size="-1" 2.439409 /tr tr tdfont size="-1"1332 /tdtdfont size="-1" 109 /tdtdfont size="-1" 0.65208 /tdtdfont size="-1" 2.377403 /tr trtd font size="-1"2213 /tdtdfont size="-1" 179 /tdtdfont size="-1" 0.673502 /tdtdfont size="-1" 2.540976 /tr trtd font size="-1"6089 /tdtdfont size="-1" 239 /tdtdfont size="-1" 0.62845 /tdtdfont size="-1" 2.529593 /tr trtd font size="-1"10382 /tdtdfont size="-1" 269 /tdtdfont size="-1" 0.604976 /tdtdfont size="-1" 2.515168 /tr trtd font size="-1"11333 /tdtdfont size="-1" 347 /tdtdfont size="-1" 0.62657 /tdtdfont size="-1" 2.618528 /tr trtdfont size="-1" 32003 /tdtdfont size="-1" 353 /tdtdfont size="-1" 0.56552 /tdtdfont size="-1" 2.507828 /tr trtdfont size="-1" 83633 /tdtdfont size="-1" 443 /tdtdfont size="-1" 0.537627 /tdtdfont size="-1" 2.509889 /tr trtdfont size="-1" 143822 /tdtdfont size="-1" 503 /tdtdfont size="-1" 0.52378 /tdtdfont size="-1" 2.513829 /tr trtdfont size="-1" 176192 /tdtdfont size="-1" 509 /tdtdfont size="-1" 0.51596 /tdtdfont size="-1" 2.501489 /tr trtdfont size="-1" 246314 /tdtdfont size="-1" 617 /tdtdfont size="-1" 0.517535 /tdtdfont size="-1" 2.550711 /tr tr tdfont size="-1"386237 /tdtdfont size="-1" 641 /tdtdfont size="-1" 0.502404 /tdtdfont size="-1" 2.530107 /tr trtd font size="-1"450644 /tdtdfont size="-1" 701 /tdtdfont size="-1" 0.503325 /tdtdfont size="-1" 2.553224 /tr trtd font size="-1"1198748 /tdtdfont size="-1"773 /tdtdfont size="-1" 0.475129 /tdtdfont size="-1" 2.520164 /tr trtdfont size="-1" 2302457 /tdtdfont size="-1"881 /tdtdfont size="-1" 0.462887 /tdtdfont size="-1" 2.526093 /tr trtd font size="-1"5513867 /tdtdfont size="-1"971 /tdtdfont size="-1" 0.443112 /tdtdfont size="-1" 2.508225 /tr trtd font size="-1"9108629 /tdtdfont size="-1"977 /tdtdfont size="-1" 0.429616 /tdtdfont size="-1" 2.481671 /tr tr tdfont size="-1"11814707 /tdtdfont size="-1"1013 /tdtdfont size="-1" 0.424976 /tdtdfont size="-1" 2.480318 /tr tr tdfont size="-1"16881479 /tdtdfont size="-1"1019 /tdtdfont size="-1" 0.416217 /tdtdfont size="-1" 2.463297 /tr tr tdfont size="-1"18786623 /tdtdfont size="-1"1103 /tdtdfont size="-1" 0.418290 /tdtdfont size="-1" 2.485805 /tr trtd font size="-1"24911213 /tdtdfont size="-1"1109 /tdtdfont size="-1" 0.411678 /tdtdfont size="-1" 2.473069 /tr trtd font size="-1"28836722 /tdtdfont size="-1"1223 /tdtdfont size="-1" 0.413867 /tdtdfont size="-1" 2.500039 /tr trtdfont size="-1" 34257764 /tdtdfont size="-1"1559 /tdtdfont size="-1" 0.423749 /tdtdfont size="-1" 2.576361 /tr tr tdfont size="-1"196457309 /tdtdfont size="-1"1607/tdtdfont size="-1"0.386581 /tdtdfont size="-1" 2.502859 /tr trtd font size="-1"238192517 /tdtdfont size="-1"1709 /tdtdfont size="-1"0.385910 /tdtdfont size="-1" 2.515164 /tr tr tdfont size="-1"482483669 /tdtdfont size="-1"1889 /tdtdfont size="-1"0.377295 /tdtdfont size="-1" 2.518416 /tr trtd font size="-1"750301568 /tdtdfont size="-1"2063 /tdtdfont size="-1"0.373455 /tdtdfont size="-1" 2.529388 /tr /table p This table is complete for n 10sup9/sup (the first two colums are sequences a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A060424"A060424/a and a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062252"A062252/a; the corresponding values of p give a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062256"A062256/a). 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: /p table border="1" align="center" tr tdx /tdtdfont size="-1" Q(x) /td tdfont size="-1" Q(x)/(x log x log log x ) /trtr tdfont size="-1"10sup2/sup /tdtdfont size="-1" 427 /tdtdfont size="-1" 0.607145 /trtr tdfont size="-1"10sup3/sup /tdtdfont size="-1" 6680 /tdtdfont size="-1" 0.500366 /trtr tdfont size="-1"10sup4/sup /tdtdfont size="-1" 101494 /tdtdfont size="-1" 0.496304 /trtr tdfont size="-1"10sup5/sup/tdtdfont size="-1" 1354578 /tdtdfont size="-1" 0.481517 /trtr tdfont size="-1"10sup6/sup/tdtdfont size="-1" 17189068 /tdtdfont size="-1" 0.473833 /trtr tdfont size="-1"10sup7/sup /tdtdfont size="-1" 210240001 /tdtdfont size="-1" 0.469208 /trtr tdfont size="-1"10sup8/sup /tdtdfont size="-1" 2501065886 /tdtdfont size="-1" 0.466024 /trtr tdfont size="-1"10sup9/sup /tdtdfont size="-1" 29118770352 /tdtdfont size="-1" 0.463545 /tr /table p 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 psubi/sub (psub1/sub=2, psub2/sub=3, etc.) that need to be run through before n(psubi/sub+1)–1 is prime. Assuming the psubi/sub are small compared to n, the probability of n(psubi/sub+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. /p p Finally, let s(x) be the number of n = x for which q(n) = q(n-1). We have the following table: /p table border="1" align="center" tr tdx /tdtdfont size="-1" s(x) /td tdfont size="-1" (log(s(x)/x))/(log log x) /td tdfont size="-1" (s(x) log x)/ x /tr trtd 10sup5/sup /tdtdfont size="-1" 6881 /tdtdfont size="-1" -1.095330 /tdtdfont size="-1" 0.792204/tr trtd10sup6/sup /tdtdfont size="-1" 60547 /tdtdfont size="-1" -1.067996 /tdtdfont size="-1" 0.836488 /tr trtd10sup7/sup /tdtdfont size="-1" 539273 /tdtdfont size="-1" -1.050424 /tdtdfont size="-1" 0.869205 /tr trtd10sup8/sup /tdtdfont size="-1" 4874595 /tdtdfont size="-1" -1.036952 /tdtdfont size="-1" 0.897934 /tr /table /p p The two right-hand columns both indicate the same thing: that s(x) appears to be approximately x/log x. /p p h2 References/h2 /p p 1. A. Schinzel and W. Sierpinski, Sur certaines hypothèses concernant les nombres premiers, iActa Arithmetica/i b4/b (1958), 185-208 /p p 2. N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at a href="http://www.research.att.com/~njas/sequences/"www.research.att.com/~njas/sequences//a. p hr p small (Concerned with sequences a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A060324"A060324/a, a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A060424"A060424/a, a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062251"A062251/a, a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062252"A062252/a, a href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A062256"A062256/a .) /small p hr p Received March 29, 2001; published in Journal of Integer Sequences July 5, 2001. p hr p Return to a href="../.." STRONGJournal of Integer Sequences home page/STRONG/a p hr /body /html