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

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[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 < 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). /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=""A060424/a and a href=""A062252/a; the corresponding values of p give a href=""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="" p hr p small (Concerned with sequences a href=""A060324/a, a href=""A060424/a, a href=""A062251/a, a href=""A062252/a, a href=""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