cp's OEIS Frontend

A001000 a(n) = least m such that if a/b < c/d where a,b,c,d are integers in [0,n], then a/b < k/m < c/d for some integer k.

%I A001000 #29 Dec 26 2016 01:50:01
%S A001000 2,3,5,7,13,17,26,31,43,57,65,82,101,111,133,157,183,197,226,257,290,
%T A001000 307,343,381,421,463,485,530,577,626,677,703,757,813,871,931,993,1025,
%U A001000 1090,1157,1226,1297,1370,1407,1483,1561,1641,1723,1807,1893,1937,2026,2117
%N A001000 a(n) = least m such that if a/b < c/d where a,b,c,d are integers in [0,n], then a/b < k/m < c/d for some integer k.
%C A001000 It suffices for (a/b, c/d) to range through the consecutive pairs of Farey fractions of order n.
%C A001000 This is the same sequence (apart from the initial term) as A071111. The identity of these two sequences was first proved by Rustem Aidagulov and a detailed version of the proof can be found in the Alekseyev link below.
%C A001000 For sets of real numbers S and T, let S be a divider of T if some element of S lies strictly between any two distinct elements of T. Let Fence(n) = {a/n : a in Z}, Recip(n) = {1/b : 1 <= b <= n} Farey(n) = {a/b : a in Z, 1 <= b <= n}. Then a(n) is the smallest k such that Fence(k) is a divider of Recip(n) and also the smallest k such that Fence(k) is a divider of Farey(n), as shown by S. Rustem Aidagulov. - _David W. Wilson_, Aug 30 2007
%C A001000 Suppose that S is a set of 2 or more real numbers.  The least m such that for every r and s in S there is an integer k such that r < k/m < s is the first separator of S.  The least m such that for every r and s in S there exists an integer k such that r < k/m < (k+1)/m < s is the second separator of S, and so on.
%C A001000 ...
%C A001000 For example, A001000 gives first separators for the sets S(n) = {0,1/2,1/3,...,1/n}.  In the following guide, the set S(n) consists of numbers given by the shown formula for h = 1, 2, ..., n; F = A000045 (Fibonacci numbers), and r = (1+sqrt(5))/2 (golden ratio).
%C A001000 ...
%C A001000 S(n) ................... 1st separators
%C A001000 Farey fractions ........ A001000
%C A001000 1/h .................... A071111
%C A001000 1/(2*h-1) .............. A024819
%C A001000 1/(2*h) ................ A024820
%C A001000 1/sqrt(h) .............. A024821
%C A001000 1/(3*h-2) .............. A024822
%C A001000 1/(3*h-1) .............. A024823
%C A001000 1/(3*h) ................ A024824
%C A001000 1/(4*h) ................ A024825
%C A001000 1/C(n+1,2) ............. A024826
%C A001000 1/h^2 .................. A024827
%C A001000 h/(1+h^2) .............. A024828
%C A001000 F(2*h-1)/F(2*h)......... A024829
%C A001000 F(2*h)/F(2*h+1) ........ A024830
%C A001000 F(2*h+1)/F(2*h+2)....... A024831
%C A001000 pi/2 - arctan(h) ....... A024832
%C A001000 |F(h+1)-r*F(h)| ........ A024849
%C A001000 fr. parts, h*sqrt(2) ... A214921
%C A001000 fr. parts, h*r ......... A214964
%C A001000 fr. parts, h*e ......... A214965
%C A001000 ...
%C A001000 S(n) ............. 2nd separators
%C A001000 1/h .............. A024833
%C A001000 1/(2*h-1) ........ A024834
%C A001000 1/(2*h) .......... A024835
%C A001000 1/(3*h-2) ........ A024836
%C A001000 1/(3*h-1) ........ A024837
%C A001000 1/(3*h) .......... A024838
%C A001000 1/(4*h) .......... A024839
%C A001000 ...
%C A001000 S(n) ............. 3rd separators
%C A001000 1/h .............. A024840
%C A001000 1/(2*h-1) ........ A024841
%C A001000 1/(2*h) .......... A024842
%C A001000 ...
%C A001000 S(n) ............. 4th separators
%C A001000 1/h .............. A024843
%C A001000 1/(2*h-1) ........ A024844
%C A001000 1/(2*h) .......... A024845
%C A001000 ...
%C A001000 S(n) ............. 5th separators
%C A001000 1/h .............. A024846
%C A001000 1/(2*h-1) ........ A024847
%C A001000 - _Clark Kimberling_, Aug 07 2012
%H A001000 T. D. Noe, <a href="/A001000/b001000.txt">Table of n, a(n) for n = 1..1000</a>
%H A001000 Max Alekseyev, <a href="/A071111/a071111.txt">Proof that A001000 and A071111 are essentially the same sequence</a>
%F A001000 For n >= 2, a(n) = (n-[r])(n-[r+1/2])+1, where r = sqrt(4n-7), [x] = greatest integer <= x. - _David W. Wilson_, Aug 30 2007
%e A001000 The Farey fractions of order 4, 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1, are separated by the fractions k/7: 0/1 < 1/7 <1/4 < 2/7 < 1/3 < 3/7 < 1/2 < 4/7 < 2/3 <5/7 < 3/4 <6/7 < 1 and 7 is the least m for which at least one k/m lies strictly between each pair of Farey fractions.
%t A001000 (* The following program generates a northwest corner of an array in which row k shows the least k-th separator of the set {1/h : h = 1,2,...,n}. *)
%t A001000 leastSeparatorS[seq_, s_] := Module[{n = 1},
%t A001000 Table[While[Or @@ (n #[[1]] <=
%t A001000 s + Floor[n #1[[2]]] &) /@ (Sort[#1, Greater] &) /@
%t A001000 Partition[Take[seq, k], 2, 1], n++]; n, {k, 2, Length[seq]}]];
%t A001000 TableForm[Map[leastSeparatorS[1/Range[15], #] &, Range[10]]]
%t A001000 (* _Peter J. C. Moses_, Aug 07 2012 *)
%Y A001000 Cf. A071111.
%K A001000 nonn,nice
%O A001000 1,1
%A A001000 _Clark Kimberling_
%E A001000 Incompleteness of old definition pointed out by Christopher Carl Heckman, and revised definition supplied by _Clark Kimberling_, Feb 18 2004
%E A001000 Definition of separator, guide to related sequences, and Mathematica program added by _Clark Kimberling_, Aug 07 2012