OFFSET
1,1
COMMENTS
A conjecture of Schinzel and Sierpiński asserts that every positive rational number r can be represented as a quotient of shifted primes such that r = (p-1)/(q-1).
The function r -> [p, q] will be called the Schinzel-Sierpiński encoding of r if q is the smallest prime such that r = (p-1)/(q-1) for some prime p. In the case that no pair of such primes exists we set by convention p = q = 1.
The Schinzel-Sierpiński tree of fractions is the Euclid tree A295515 with root 1 and fractions represented by the Schinzel-Sierpiński encoding.
REFERENCES
E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232.
LINKS
N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.
Matthew M. Conroy, A sequence related to a conjecture of Schinzel, J. Integ. Seqs. Vol. 4 (2001), #01.1.7.
P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. I., J. Reine Angew. Math. 463 (1995), 169-216.
P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. II. J. Reine Angew. Math. 519 (2000), 59-71.
Peter Luschny, The Schinzel-Sierpiński conjecture and the Calkin-Wilf tree.
A. Malter, D. Schleicher, D. Zagier, New looks at old number theory, Amer. Math. Monthly, 120 (2013), 243-264.
A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arithmetica 4 (1958), 185-208; erratum 5 (1958) p. 259.
EXAMPLE
The tree starts:
2/2
2/3 3/2
3/7 7/5 5/7 7/3
2/5 17/13 7/11 11/5 5/11 11/7 13/17 5/2
.
The numerators of the terms written as an array (the denominators are given by reversion of the arrays):
1: 2
2: 2, 3
3: 3, 7, 5, 7
4: 2, 17, 7, 11, 5, 11, 13, 5
5: 3, 241, 17, 29, 7, 17, 31, 43, 13, 43, 11, 17, 13, 29, 193, 11
PROG
(Sage)
def EuclidTree(n): # with root 1
def DijkstraFusc(m):
a, b, k = 1, 0, m
while k > 0:
if k % 2 == 1: b += a
else: a += b
k = k >> 1
return b
DF = [DijkstraFusc(k) for k in (2^(n-1)..2^n)]
return [DF[j]/DF[j+1] for j in (0..2^(n-1)-1)]
def SchinzelSierpinski(l):
a, b = l.numerator(), l.denominator()
p, q = 1, 2
while q < 1000000000: # search limit
r = a*(q - 1)
if b.divides(r):
p = r // b + 1
if is_prime(p): return p/q
q = next_prime(q)
print("Search limit reached for ", l); return 0
def SSETree(level):
return [SchinzelSierpinski(l) for l in EuclidTree(level)]
# With the imperfection that Sage reduces 2/2 automatically to 1.
for level in (1..6): print(SSETree(level))
KEYWORD
nonn,tabf
AUTHOR
Peter Luschny, Nov 23 2017
STATUS
approved