A295511 The Schinzel-Sierpiński tree of fractions, read across levels.

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, 3, 11, 241, 193, 17, 29, 29, 13, 7, 17, 17, 11, 31, 43, 43, 13, 13, 43, 43, 31, 11, 17, 17, 7, 13, 29, 29, 17, 193, 241, 11, 3

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

Table of n, a(n) for n=1..62.

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))

Crossrefs

Cf. A002487, A294442, A295510, A295512, A295515.

Sequence in context: A238969 A238956 A331415 * A116505 A110534 A194340

Adjacent sequences: A295508 A295509 A295510 * A295512 A295513 A295514

Keyword

nonn,tabf

Author

Peter Luschny, Nov 23 2017

Status

approved