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).

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

Offset: 1

Author

Antti Karttunen

Keywords

• nonn

Examples

			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
		

Links

• Index entries for sequences related to Stern's sequences
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A047679, A007305, A007306, A054427, A057114. In table form: A054425. Inverse permutation: A054426.

Programs

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

Formula

canonical_fractions_to_whole_SternBrocot_permutation(30);