|
| |
|
|
A054424
|
|
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).
|
|
13
|
|
|
|
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, 30, 255, 256, 19, 28, 511, 512, 33, 18, 20, 47, 48, 27, 29, 62, 1023, 1024, 22, 25, 2047, 2048, 65, 35, 39, 21, 95, 96, 26, 56, 60, 126, 4095, 4096, 34, 40, 55, 61, 8191, 8192
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
canonical_fractions_to_whole_SternBrocot_permutation(30);
|
|
|
EXAMPLE
|
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
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
|
|
|
MAPLE
|
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;
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;
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Antti Karttunen
|
|
|
STATUS
|
approved
|
| |
|
|
