A295511 - OEIS

%I #26 Jun 03 2019 01:13:25

%S 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,

%T 3,11,241,193,17,29,29,13,7,17,17,11,31,43,43,13,13,43,43,31,11,17,17,

%U 7,13,29,29,17,193,241,11,3

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

%C 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).

%C 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.

%C The Schinzel-Sierpiński tree of fractions is the Euclid tree A295515 with root 1 and fractions represented by the Schinzel-Sierpiński encoding.

%D E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232.

%H N. Calkin and H. S. Wilf, <a href="https://www.jstor.org/stable/2589182">Recounting the rationals</a>, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.

%H Matthew M. Conroy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL4/CONROY/conroy.html">A sequence related to a conjecture of Schinzel</a>, J. Integ. Seqs. Vol. 4 (2001), #01.1.7.

%H P. D. T. A. Elliott, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002212722">The multiplicative group of rationals generated by the shifted primes. I.</a>, J. Reine Angew. Math. 463 (1995), 169-216.

%H P. D. T. A. Elliott, <a href="http://dx.doi.org/10.1515/crll.2000.017">The multiplicative group of rationals generated by the shifted primes. II.</a> J. Reine Angew. Math. 519 (2000), 59-71.

%H Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/SchinzelSierpinskiConjectureAndCalkinWilfTree">The Schinzel-Sierpiński conjecture and the Calkin-Wilf tree</a>.

%H A. Malter, D. Schleicher, D. Zagier, <a href="http://people.mpim-bonn.mpg.de/zagier/files/doi/10.4169/amer.math.monthly.120.03.243/NewLooksAtOldNumberTheory.pdf">New looks at old number theory</a>, Amer. Math. Monthly, 120 (2013), 243-264.

%H A. Schinzel and W. Sierpiński, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa4/aa432.pdf">Sur certaines hypothèses concernant les nombres premiers</a>, Acta Arithmetica 4 (1958), 185-208; erratum 5 (1958) p. 259.

%e The tree starts:

%e                                         2/2

%e                    2/3                                     3/2

%e          3/7                  7/5                 5/7                   7/3

%e    2/5       17/13     7/11        11/5     5/11       11/7     13/17        5/2

%e .

%e The numerators of the terms written as an array (the denominators are given by reversion of the arrays):

%e 1: 2

%e 2: 2, 3

%e 3: 3, 7, 5, 7

%e 4: 2, 17, 7, 11, 5, 11, 13, 5

%e 5: 3, 241, 17, 29, 7, 17, 31, 43, 13, 43, 11, 17, 13, 29, 193, 11

%o (Sage)

%o def EuclidTree(n): # with root 1

%o     def DijkstraFusc(m):

%o         a, b, k = 1, 0, m

%o         while k > 0:

%o             if k % 2 == 1: b += a

%o             else: a += b

%o             k = k >> 1

%o         return b

%o     DF = [DijkstraFusc(k) for k in (2^(n-1)..2^n)]

%o     return [DF[j]/DF[j+1] for j in (0..2^(n-1)-1)]

%o def SchinzelSierpinski(l):

%o     a, b = l.numerator(), l.denominator()

%o     p, q = 1, 2

%o     while q < 1000000000: # search limit

%o         r = a*(q - 1)

%o         if b.divides(r):

%o             p = r // b + 1

%o             if is_prime(p): return p/q

%o         q = next_prime(q)

%o     print("Search limit reached for ", l); return 0

%o def SSETree(level):

%o     return [SchinzelSierpinski(l) for l in EuclidTree(level)]

%o # With the imperfection that Sage reduces 2/2 automatically to 1.

%o for level in (1..6): print(SSETree(level))

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

%K nonn,tabf

%O 1,1

%A _Peter Luschny_, Nov 23 2017