|
%I #74 Oct 06 2022 04:28:04
%S 1,1,1,2,1,3,2,1,4,3,2,3,1,5,4,3,4,2,5,3,1,6,5,4,5,3,7,4,2,7,5,3,5,1,
%T 7,6,5,6,4,9,5,3,10,7,4,7,2,9,7,5,7,3,8,5,1,8,7,6,7,5,11,6,4,13,9,5,9,
%U 3,13,10,7,10,4,11,7,2,11,9,7,9,5,12,7
%N Denominators in the Fibonacci (or rabbit) ordering of the positive rational numbers.
%C Let S be the set of numbers defined by these rules: 1 is in S, and if x is in S, then x+1 and 1/x are in S. Then S is the set of positive rational numbers, which arise in generations as follows: g(1) = (1/1), g(2) = (1+1) = (2), g(3) = (2+1, 1/2) = (3/1, 1/2), g(4) = (4/1, 1/3, 3/2), ... . Once g(n-1) = (g(1), ..., g(z)) is defined, g(n) is formed from the vector (g(1) + 1, 1/g(1), g(2) + 1, 1/g(2), ..., g(z) + 1, 1/g(z)) by deleting all elements that are in a previous generation. A226080 is the sequence of denominators formed by concatenating the generations g(1), g(2), g(3), ... . It is easy to prove the following:
%C (1) Every positive rational is in S.
%C (2) The number of terms in g(n) is the n-th Fibonacci number, F(n) = A000045(n).
%C (3) For n > 2, g(n) consists of F(n-2) numbers < 1 and F(n-1) numbers > 1, hence the name "rabbit ordering" since the n-th generation has F(n-2) reproducing pairs and F(n-1) non-reproducing pairs, as in the classical rabbit-reproduction introduction to Fibonacci numbers.
%C (4) The positions of integers in S are the Fibonacci numbers.
%C (5) The positions of 1/2, 3/2, 5/2, ..., are Lucas numbers (A000032).
%C (6) Continuing from (4) and (5), suppose that n > 0 and 0 < r < n, where gcd(n,r) = 1. The positions in A226080 of the numbers congruent to r mod n comprise a row of the Wythoff array, W = A035513. The correspondence is sampled here:
%C row 1 of W: positions of n+1 for n>=0,
%C row 2 of W: positions of n+1/2,
%C row 3 of W: positions of n+1/3,
%C row 4 of W: positions of n+1/4,
%C row 5 of W: positions of n+2/3,
%C row 6 of W: positions of n+1/5,
%C row 7 of W: positions of n+3/4.
%C (7) If the numbers <=1 in S are replaced by 1 and those >1 by 0, the resulting sequence is the infinite Fibonacci word A003849 (except for the 0-offset first term).
%C (8) The numbers <=1 in S occupy positions -1 + A001950, where A001950 is the upper Wythoff sequence; those > 1 occupy positions given by -1 + A000201, where A000201 is the lower Wythoff sequence.
%C (9) The rules (1 is in S, and if x is in S, then 1/x and 1/(x+1) are in S) also generate all the positive rationals.
%C A variant which extends this idea to an ordering of all rationals is described in A226130. - _M. F. Hasler_, Jun 03 2013
%C The updown and downup zigzag limits are (-1 + sqrt(5))/2 and (1 + sqrt(5))/2; see A020651. - _Clark Kimberling_, Nov 10 2013
%C From _Clark Kimberling_, Jun 19 2014: (Start)
%C Following is a guide to related trees and sequences; for example, the tree A226080 is represented by (1, x+1, 1/x), meaning that 1 is in S, and if x is in S, then x+1 and 1/x are in S (except for x = 0).
%C All the positive integers:
%C A243571, A243572, A232559 (1, x+1, 2x)
%C A232561, A242365, A243572 (1, x+1, 3x)
%C A243573 (1, x+1, 4x)
%C All the integers:
%C A243610 (1, 2x, 1-x)
%C A232723, A242364
%C All the positive rationals:
%C A226080, A226081, A242359, A242360 (1, x+1, 1/x)
%C A243848, A243849, A243850 (1, x+1, 2/x)
%C A243851, A243852, A243853 (1, x+1, 3/x)
%C A243854, A243855, A243856 (1, x+1, 4/x)
%C A243574, A242308 (1, 1/x, 1/(x+1))
%C A241837, A243575 ({1,2,3}, x+4, 12/x)
%C A242361, A242363 (1, 1 + 1/x, 1/x)
%C A243613, A243614 (0, x+1, x/(x+1))
%C All the rationals:
%C A243611, A243612 (0, x+1, -1/(x+1))
%C A226130, A226131 (1, x+1, -1/x)
%C A243712, A243713 ({1,2,3}, x+1, 1/(x+1))
%C A243730, A243731 ({1,2,3,4}, x+1, 1/(x+1))
%C A243732, A243733 ({1,2,3,4,5}, x+1, 1/(x+1))
%C A243714, A243715
%C A243925, A243926, A243927 (1, x+1, -2/x)
%C A243928, A243929, A243930 (1, x+1, -3/x)
%C All the Gaussian integers:
%C A243924 (1, x+1, i*x)
%C All the Gaussian rational numbers:
%C A233694, A233695, A233696 (1, x+1, i*x, 1/x).
%C (End)
%H Clark Kimberling, <a href="/A226080/b226080.txt">Table of n, a(n) for n = 1..6000</a>
%H Clark Kimberling, <a href="http://www.fq.math.ca/Papers1/52-5/Kimberling.pdf">The infinite Fibonacci tree and other trees generated by rules</a>, Proceedings of the 16th International Conference on Fibonacci Numbers and Their Applications, Fibonacci Quarterly 52 (2014), no. 5, pp. 136-149.
%H <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%e The denominators are read from the rationals listed in "rabbit order":
%e 1/1, 2/1, 3/1, 1/2, 4/1, 1/3, 3/2, 5/1, 1/4, 4/3, 5/2, 2/3, 6/1, ...
%t z = 10; g[1] = {1}; g[2] = {2}; g[3] = {3, 1/2};
%t j[3] = Join[g[1], g[2], g[3]]; j[n_] := Join[j[n - 1], g[n]];
%t d[s_List, t_List] := Part[s, Sort[Flatten[Map[Position[s, #] &, Complement[s, t]]]]]; j[3] = Join[g[1], g[2], g[3]]; n = 3; While[n <= z, n++; g[n] = d[Riffle[g[n - 1] + 1, 1/g[n - 1]], g[n - 2]]];
%t Table[g[n], {n, 1, z}]; j[z] (* rabbit-ordered rationals *)
%t Denominator[j[z]] (* A226080 *)
%t Numerator[j[z]] (* A226081 *)
%t Flatten[NestList[(# /. x_ /; x > 1 -> Sequence[x, 1/x - 1]) + 1 &, {1}, 9]] (* rabbit-ordered rationals, _Danny Marmer_, Dec 07 2014 *)
%o (PARI) A226080_vec(N=100)={my(T=[1],S=T,A=T); while(N>#A=concat(A, apply(denominator, T=select(t->!setsearch(S,t), concat(apply(t->[t+1,1/t],T))))), S=setunion(S,Set(T)));A} \\ _M. F. Hasler_, Nov 30 2018
%o (PARI) (A226080(n)=denominator(RabbitOrderedRational(n))); ROR=List(1); RabbitOrderedRational(n)={if(n>#ROR, local(S=Set(ROR), i=#ROR*2\/(sqrt(5)+1), a(t)=setsearch(S,t)||S=setunion(S,[listput(ROR,t)])); until( type(ROR[i+=1])=="t_INT" && n<=#ROR, a(ROR[i]+1); a(1/ROR[i])));ROR[n]} \\ _M. F. Hasler_, Nov 30 2018
%Y Cf. A000045, A035513, A226081 (numerators), A226130, A226247, A020651.
%K nonn,frac
%O 1,4
%A _Clark Kimberling_, May 25 2013
|
