login
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.
37

%I #29 Dec 26 2016 01:50:01

%S 2,3,5,7,13,17,26,31,43,57,65,82,101,111,133,157,183,197,226,257,290,

%T 307,343,381,421,463,485,530,577,626,677,703,757,813,871,931,993,1025,

%U 1090,1157,1226,1297,1370,1407,1483,1561,1641,1723,1807,1893,1937,2026,2117

%N 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 It suffices for (a/b, c/d) to range through the consecutive pairs of Farey fractions of order n.

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

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

%C S(n) ................... 1st separators

%C Farey fractions ........ A001000

%C 1/h .................... A071111

%C 1/(2*h-1) .............. A024819

%C 1/(2*h) ................ A024820

%C 1/sqrt(h) .............. A024821

%C 1/(3*h-2) .............. A024822

%C 1/(3*h-1) .............. A024823

%C 1/(3*h) ................ A024824

%C 1/(4*h) ................ A024825

%C 1/C(n+1,2) ............. A024826

%C 1/h^2 .................. A024827

%C h/(1+h^2) .............. A024828

%C F(2*h-1)/F(2*h)......... A024829

%C F(2*h)/F(2*h+1) ........ A024830

%C F(2*h+1)/F(2*h+2)....... A024831

%C pi/2 - arctan(h) ....... A024832

%C |F(h+1)-r*F(h)| ........ A024849

%C fr. parts, h*sqrt(2) ... A214921

%C fr. parts, h*r ......... A214964

%C fr. parts, h*e ......... A214965

%C ...

%C S(n) ............. 2nd separators

%C 1/h .............. A024833

%C 1/(2*h-1) ........ A024834

%C 1/(2*h) .......... A024835

%C 1/(3*h-2) ........ A024836

%C 1/(3*h-1) ........ A024837

%C 1/(3*h) .......... A024838

%C 1/(4*h) .......... A024839

%C ...

%C S(n) ............. 3rd separators

%C 1/h .............. A024840

%C 1/(2*h-1) ........ A024841

%C 1/(2*h) .......... A024842

%C ...

%C S(n) ............. 4th separators

%C 1/h .............. A024843

%C 1/(2*h-1) ........ A024844

%C 1/(2*h) .......... A024845

%C ...

%C S(n) ............. 5th separators

%C 1/h .............. A024846

%C 1/(2*h-1) ........ A024847

%C - _Clark Kimberling_, Aug 07 2012

%H T. D. Noe, <a href="/A001000/b001000.txt">Table of n, a(n) for n = 1..1000</a>

%H Max Alekseyev, <a href="/A071111/a071111.txt">Proof that A001000 and A071111 are essentially the same sequence</a>

%F 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 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 (* 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 leastSeparatorS[seq_, s_] := Module[{n = 1},

%t Table[While[Or @@ (n #[[1]] <=

%t s + Floor[n #1[[2]]] &) /@ (Sort[#1, Greater] &) /@

%t Partition[Take[seq, k], 2, 1], n++]; n, {k, 2, Length[seq]}]];

%t TableForm[Map[leastSeparatorS[1/Range[15], #] &, Range[10]]]

%t (* _Peter J. C. Moses_, Aug 07 2012 *)

%Y Cf. A071111.

%K nonn,nice

%O 1,1

%A _Clark Kimberling_

%E Incompleteness of old definition pointed out by Christopher Carl Heckman, and revised definition supplied by _Clark Kimberling_, Feb 18 2004

%E Definition of separator, guide to related sequences, and Mathematica program added by _Clark Kimberling_, Aug 07 2012