|
%I #6 Jul 10 2011 18:39:17
%S 1,2,3,4,7,8,5,6,15,16,31,32,9,11,12,14,63,64,10,13,127,128,17,23,24,
%T 30,255,256,19,28,511,512,33,18,20,47,48,27,29,62,1023,1024,22,25,
%U 2047,2048,65,35,39,21,95,96,26,56,60,126,4095,4096,34,40,55,61,8191,8192
%N Permutation of natural numbers: maps the canonical list of fractions (A020652/A020653) to whole Stern-Brocot (Farey) tree (top = 1/1 and both sides < 1 and > 1, but excluding the "fractions" 0/1 and 1/0).
%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F canonical_fractions_to_whole_SternBrocot_permutation(30);
%e Whole Stern-Brocot tree: 1/1 1/2 2/1 1/3 2/3 3/2 3/1 1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1 1/5 2/7
%e Canonical fractions: 1/1 1/2 2/1 1/3 3/1 1/4 2/3 3/2 4/1 1/5 5/1 1/6 2/5 3/4 4/3 5/2 6/1
%p cfrac2binexp := proc(c) local i,e,n; n := 0; for i from 1 to nops(c) do e := c[i]; if(i = nops(c)) then e := e-1; fi; n := ((2^e)*n) + ((i mod 2)*((2^e)-1)); od; RETURN(n); end;
%p frac2position_in_whole_SB_tree := proc(r) local k,msb; if(1 = r) then RETURN(1); else if(r > 1) then k := cfrac2binexp(convert(r,confrac)); else k := ReflectBinTreePermutation(cfrac2binexp(convert(1/r,confrac))); fi; msb := floor_log_2(k); if(r > 1) then RETURN(k + (2^(msb+1))); else RETURN(k + (2^(msb+1)) - (2^msb)); fi; fi; end;
%p canonical_fractions_to_whole_SternBrocot_permutation := proc(u) local a,n,i; a := []; for n from 2 to u do for i from 1 to n-1 do if (1 = igcd(n,i)) then a := [op(a),frac2position_in_whole_SB_tree(i/(n-i))]; fi; od; od; RETURN(a); end; # ReflectBinTreePermutation and floor_log_2 given in A054429
%Y Cf. A047679, A007305, A007306, A054427, A057114. In table form: A054425. Inverse permutation: A054426.
%K nonn
%O 1,2
%A Antti Karttunen
|
