User:Peter Luschny/SchinzelSierpinskiConjectureAndCalkinWilfTree

The Schinzel-Sierpinski conjecture
and the Calkin-Wilf tree.

KEYWORDS: Schinzel-Sierpinski conjecture, Calkin-Wilf tree, semiprimes, supersingular primes.

Concerned with sequences: A000790, A001358, A002267, A060324, A062251, A108574, A108764.

Introduction

A conjecture of Schinzel and Sierpinski asserts that every positive rational number r can be represented as a quotient of shifted primes, that

$r={\frac {p+1}{q+1}}\quad (p,q$ primes).

In fact we would expect there to be not just one such pair of primes, but infinitely many pairs. Schinzel and Sierpinski wrote:

Tout nombre rationnel positif peut être représenté d'une infinité de manières sous la forme (p+1)/(q+1) ainsi que sous la forme (p-1)/(q-1), où p et q sonst des nombres premiers.

We will determine (computationally) the smallest prime p so that r = (p+1) / (q+1) for some q prime. This pair of primes (p,q) we will call the Schinzel-Sierpinski primes of r (if such primes exist). Thus we assume a map

$\mathbb {Q} ^{*}\rightarrow \mathbb {P} ^{2},\quad r\mapsto (p,q)\,.$

Additionally we define an encoding with sgn(p,q) = 1 if p < q and -1 otherwise

$\mathbb {P} ^{2}\rightarrow \mathbb {Z} ;\ (p,q)\mapsto \pm pq\,.$

This function will be called the Schinzel-Sierpinski encoding of the (positive) rational number r = (p, q), p, q primes. In the unlikely case that no pair of prime numbers corresponding to a given r can be found we set by convention p = q = 1. Additionally we define 0 → 0.

Conversely, let us for instance decode 39. The prime factors of 39 are 3 and 13, thus 39 represents 7/14 = 2/7 and -39 represents 7/2.

The case of integers

The Schinzel-Sierpinski primes can be easily computed by a simple search.

SchinzelSierpinskiPrimes := proc(a, type)
local p,q,P; P := select(isprime,[$1..4000]):
if a = 1 then RETURN(2) fi;
for p in P do for q in P do
   if (p+1)/(q+1) = a then
   `if`(type="numer", p, q); RETURN(%) fi
od od; print("More primes needed!") end:

Alois Heinz pointed out that there is a much more efficient and elegant way to compute the denominators (q) returned by this function if the input 'a' is an integer 'n'.

a := proc(n) local q;
       q := 2;
       while not isprime (n*(q+1)-1) do
          q := nextprime(q);
       od; q
    end:

However, as long as the Schinzel-Sierpinski conjecture is not proved this is a classical implementation of a potential infinite loop. Wikipedia: "An infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, or having one that can never be met."

The full and efficient implementation can be found in the appendix. Note that we use a single function for both the numerator and the denominator of r.

A062251 := n -> SchinzelSierpinskiPrimes(n,"numer"):

A062251 = 2, 5, 11, 11, 19, 17, 41, 23, 53, 29, 43, 47, 103, 41,
59, 47, 67, 53, 113, 59, 83, 131, 137, 71, 149, 103, 107, 83, 

A060324 := n -> SchinzelSierpinskiPrimes(n,"denom"):

A060324 = 2, 2, 3, 2, 3, 2, 5, 2, 5, 2, 3, 3, 7, 2, 3, 2,
3, 2, 5, 2, 3, 5, 5, 2, 5, 3, 3, 2, 5, 2, 13, 3

The Calkin-Wilf tree

We give the two functions needed to compute the Calkin-Wilf tree. For details and generalizations we refer the reader to the blog "Stern's Diatomic Array" (see the link below ).

DijkstraFusc := proc(m) option remember;
local a, b, n; a := 1; b := 0; n := m;
while n > 0 do
  if type(n, odd) then b := a+b else a := a+b fi;
n := iquo(n,2) od; b end:

// returns the n-th level of the Calkin-Wilf tree
CalkinWilfTree := proc(n) local k;
seq(DijkstraFusc(k)/DijkstraFusc(k+1),k=2^(n-1)..2^n-1) end:

The case of rational numbers

Now we apply the Schinzel-Sierpinski encoding to the Calkin-Wilf tree.

SchinzelSierpinski :=
proc(a,b) local p,q,P; P := select(isprime,[$1..4000]):
for p in P do for q in P do
  if (p+1)/(q+1) = a/b then RETURN(`if`(a<b,-p*q,p*q)) fi
od od; print("More primes needed!") end:

SchinzelSierpinskiEncodedCalkinWilfTree := proc(n) local l;
seq(SchinzelSierpinski(numer(l),denom(l)),l=CalkinWilfTree(n)) end:

seq(print(SchinzelSierpinskiEncodedCalkinWilfTree(i)),i=0..5);

The case r = (p + 1) / ( q + 1)

// The encoded tree [form r=(p+1)/(q+1)] in breadth-first traversal.

A = 4, -10, 10, -33, 15, -15, 33, -22, 6, -209, 133, 
-133, 209, -6, 22, -57, 667, -91, 65, -14, 589, -1189, 39,

// The rightmost branch of the encoded tree, 
// i.e. the codes for the natural numbers.
seq(SchinzelSierpinski(n, 1), n = 1..42);

B = 4, 10, 33, 22, 57, 34, 205, 46, 265, 58, 129,
141, 721, 82, 177, 94, 201, 106, 565, 118, 249, 655, 685,

There is a third interesting sequence here: the numbers which do not appear in the encoded tree (apart from the sign). This is the complement of A relative to the semiprimes A001358. For instance the squares of odd primes are not members of B (they all map to '1' but do not meet the minimality condition).

The case r = (p − 1) / ( q − 1)

Schinzel and Sierpinski considered in their conjecture besides r = (p + 1)/(q + 1) also the form r = (p − 1)/(q − 1); in fact both forms are easy consequences of a more general conjecture. So let us look also at this case. The encoded tree starts

4,
-6,6,
-21,35,-35,21,
-10,221,-77,55,-55,77,-221,10,

This leads to another set of sequences.

// The encoded tree [form r=(p-1)/(q-1)] in breadth-first traversal.
4, -6, 6, -21, 35, -35, 21, -10, 221, -77, 55, -55, 77, -221, 10, 
-33, 46513, -493, 377, -119, 187, -1333, 559, -559, 1333, -187, 119,

// The rightmost branch of this encoded tree, 
// i.e. the codes for the natural numbers.
4, 6, 21, 10, 33, 14, 145, 51, 57, 22, 69, 26, 265, 87, 93, 34, 721,
38, 2101, 123, 129, 46, 141, 485, 505, 159, 545, 58, 177, 62,

Is there a connection with supersingular primes?

Is there any pattern in the encodings of the CW-tree? If we look only at the positive values of the first five lines

4,
10,
33,15,
22,6,209,133,
57,(667),91,65,14,(589),(1189),39,

we see 13 values which are products of exactly two supersingular primes (from the sequence A108764 by Jonathan Vos Post). This is not a very significant concordance; however, it is remarkable how it points in the right direction: to group theory. It is known that the set of shifted primes generates a subgroup of the multiplicative group of rational numbers (see the references).

And the conjecture of Schinzel and Sierpinski can be formulated in terms of group theory. Let Q* denote the multiplicative group of positive rationals and let G be the subgroup generated by shifted primes p+1 then the conjecture of Schinzel and Sierpinski can be stated as: Q* = G.

The supersingular primes are the set of primes that divide the group order of a big sporadic group, the so called Monster group. In what way the group orders of other (sporadic) groups are possibly reflected in the encoded Calkin-Wilf tree has not yet been studied to my knowledge.

Appendix

CalkinWilfTree_level := proc(n) 
local k, DijkstraFusc;

DijkstraFusc := proc(m) option remember; 
local a, b, n; a := 1; b := 0; n := m;
while n > 0 do 
   if type(n, odd) then b := a+b else a := a+b fi;
   n := iquo(n,2) 
od; 
b end:

seq(DijkstraFusc(k)/DijkstraFusc(k+1),
k=2^(n-1)..2^n-1) end:

for i from 1 to 6 do CalkinWilfTree_level(i) od;

#-- A fast and save implementation. 
SchinzelSierpinski := proc(l, primetype, outtype)
local a, b, r, p, q, uno, sgn, SearchLimit;
a := numer(l); b := denom(l);
SearchLimit := 40000; q := 2;
sgn := `if`(a < b, -1, 1);
uno := `if`(primetype = "plus", 1, -1);
do r := a*(q + uno);
  if r mod b = 0 then p := r/b - uno;
    if isprime(p) then 
         if outtype = "pri" then RETURN(p/q) 
       elif outtype = "cod" then RETURN(sgn*p*q)
       elif outtype = "num" then RETURN(p)
       elif outtype = "den" then RETURN(q)
       else ERROR("Wrong type specification!")
  fi fi fi;
  q := nextprime(q);
  if q > SearchLimit then
     ERROR("SearchLimit reached! Input was: ",a, b)
  fi
od end:

for i from 1 to 3 do 
seq(SchinzelSierpinski(l,"plus","pri"),
l=CalkinWilfTree_level(i)) od;

The parameters in the call SchinzelSierpinski(l,para1,para2) are for para1 'plus' for the type r = (p+1)/(q+1) and 'minus' for the type r = (p-1)/(q-1). For para2: 'pri' stands for the encoding to a rational number p/q, p, q, primes; 'cod' for the encoding to semiprimes; 'num' and 'den' returns the numerator and the denominator of the rational number respectively.

References

Calkin, Neil; Wilf, Herbert (2000), "Recounting the rationals", Amer. Math. Monthly 107 (4): 360–363
E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232.
Elliott, P. D. T. A. "The multiplicative group of rationals generated by the shifted primes. I." J. Reine Angew. Math. 463 (1995), 169–216.
Elliott, P. D. T. A. "The multiplicative group of rationals generated by the shifted primes. II." J. Reine Angew. Math. 519 (2000), 59–71.
Matthew M. Conroy, A sequence related to a conjecture of Schinzel, J. Integ. Seqs. Vol. 4 (2001), #01.1.7.
Schinzel, A. and Sierpinski, W. "Sur certaines hypothèses concernant les nombres premiers." Acta Arith. 4, 185-208, 1958. erratum 5 (1958) p. 259.

See also

Stern's Diatomic Array