login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A295511 The Schinzel-Sierpiński tree of fractions, read across levels. 4
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 22:40 EST 2020. Contains 332312 sequences. (Running on oeis4.)