cp's OEIS Frontend

A143515 Array D of denominators of Best Remaining Upper Approximates of x=(1+sqrt(5))/2, by antidiagonals.

%I A143515 #14 Jun 01 2022 12:16:37
%S A143515 1,3,2,8,4,5,21,6,7,10,55,11,9,12,13,144,16,14,17,15,18,377,29,19,22,
%T A143515 20,23,26,987,42,24,27,25,28,31,34,2584,76,37,32,30,33,36,39,47,6765,
%U A143515 110,50,45,35,38,41,44,52,60,17711,199,63,58,40,43,46,49,57,65
%N A143515 Array D of denominators of Best Remaining Upper Approximates of x=(1+sqrt(5))/2, by antidiagonals.
%C A143515 (1) Row 1 of R consists of upper principal convergents to x.
%C A143515 (2) (row limits of R) = x; (column limits of R) = 0.
%C A143515 (3) Every positive integer occurs exactly once in D, so that as a sequence, this is a permutation of the positive integers.
%C A143515 (4) p=1+floor(q*r) for every p/q in R. Consequently, the terms of N are distinct and their ordered union is 1+A000201.
%C A143515 (5) Conjecture: Every (N(n,k+1)-N(n,k))/(D(n,k+1)-D(n,k)) is a principal convergent to x.
%C A143515 (6) Suppose n>=1 and p/q and s/t are consecutive terms in row n of R. Then (conjecture) p*t-q*s=n.
%C A143515 In general, for irrational r, let {n*r} denote the fractional part of n*r. Define t(1,1) = 1, and t(1,n) = least k such that {k*r} > {t(1,n-1)*x} for n >= 2. Inductively, for m >= 2 and n >= 1, let t(m,1) be the least k not already defined as a term in the array, and for n >= 2, define t(m,n) = least k such that {k*r} > {t(m,n-1)*x and k has not previously been defined as a term. Thus, every row of (t(m,n)) is strictly increasing. For r = (1+sqrt(5))/2, the array (t(m,n) is D. - _Clark Kimberling_, Feb 21 2021
%H A143515 Clark Kimberling, <a href="http://dx.doi.org/10.1007/s000170050020">Best lower and upper approximates to irrational numbers</a>, Elemente der Mathematik, 52 (1997) 122-126.
%F A143515 For any positive irrational number x, define an array D by successive rows as follows: D(n,k) = least positive integer q not already in D such that there exists an integer p such that 0 < p/q - x < c/d - x for every positive rational number c/d that has 0 < d < q. Thus p/q is the "best remaining upper approximate" of x when all better upper approximates are unavailable. For each q, define N(n,k)=p and R(n,k)=p/q. Then R is the "array of best remaining upper approximates of x," D is the corresponding array of denominators and N, of numerators.
%e A143515 Northwest corner of D:
%e A143515   1 3 8 21
%e A143515   2 4 6 11
%e A143515   5 7 9 14
%e A143515   10 12 17 22
%e A143515 Northwest corner of R:
%e A143515   2/1 5/3 13/8 34/21
%e A143515   4/2 7/4 10/6 18/11
%e A143515   9/5 12/7 15/9 23/14
%e A143515   17/10 20/12 28/17 36/22
%t A143515 r = N[(1 + Sqrt[5])/2, 100]; Table[d = 0; t[k] = {};
%t A143515 Do[a = FractionalPart[n*r];
%t A143515   If[a > d && ! MemberQ[Apply[Union, Map[t[#] &, Range[k - 1]]], n],
%t A143515    d = a; AppendTo[t[k], n]], {n, 10000}]; t[k], {k, 12}];
%t A143515 Column[Table[t[k], {k, 1, 12}]]
%t A143515 (* _Peter J. C. Moses_, Feb 18 2021 *)
%Y A143515 Cf. A000045, A000201, A143514, A143516.
%K A143515 nonn,tabl
%O A143515 1,2
%A A143515 _Clark Kimberling_, Aug 22 2008