|
|
A054429
|
|
Simple self-inverse permutation of natural numbers: List each block of 2^n numbers (from 2^n to 2^(n+1) - 1) in reverse order.
|
|
214
|
|
|
1, 3, 2, 7, 6, 5, 4, 15, 14, 13, 12, 11, 10, 9, 8, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 127, 126, 125, 124, 123, 122, 121
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The mapping and conversion rules are as follows:
By rows, we have ...
1;
3, 2;
7, 6, 5, 4;
15, 14, 13, 12, 11, 10, 9, 8;
... onto which we are to map one-half of the Stern-Brocot infinite Farey Tree:
1/2
1/3, 2/3
1/4, 2/5, 3/5, 3/4
1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5
...
The conversion rules are: Convert the decimal to binary, adding a duplicate of the rightmost binary term to its right. For example, 10 = 1010, which becomes 10100. Then, from the left, record the number of runs = [1,1,1,2], the continued fraction representation of 5/8. Check: 10 decimal corresponds to 5/8 as shown in the overlaid mapping. Take decimal 9 = 1001 which becomes 10011, with a continued fraction representation of [1,2,2] = 5/7. Check: 9 decimal corresponds to 5/7 in the Farey Tree map. (End)
a(n) is the value generated when n is converted into its Elias gamma code, the 1's and 0's are interchanged and the resultant is converted back to its decimal value for all values of n > 1. For n = 1, A054429(n) = 1 but after converting 1 to Elias gamma code, interchanging the 1's and 0's and converting it back to decimal, the result produced is 0.
For example, let n = 10. The Elias gamma code for 10 is '1110010'. After interchanging the 1's and 0's it becomes "0001101" and 1101_2 = 13_10. So a(10) = 13. (End)
From Yosu Yurramendi, Mar 09 2017 (similar to Zumkeller's comment): (Start)
|
|
LINKS
|
|
|
FORMULA
|
a(n) = ReflectBinTreePermutation(n).
a(n) = if n=1 then 1 else 2*a(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Feb 18 2003
G.f.: 1/(1-x) * ((x-2x^2)/(1-x) + Sum_{k>=0} 3*2^k*x^2^k). - Ralf Stephan, Sep 15 2003
a(1) = 1, a(2^(m+1) + k) = a(2^m+k) + 2^(m+1),
a(2^(m+1) + 2^m+k) = a(2^m+k) + 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Apr 06 2017
|
|
MAPLE
|
A054429 := n -> 3*2^ilog2(n) - n - 1:
|
|
MATHEMATICA
|
Flatten[Table[Range[2^(n+1)-1, 2^n, -1], {n, 0, 6}]] (* Harvey P. Dale, Dec 17 2013 *)
|
|
PROG
|
(Haskell)
a054429 n = a054429_list !! (n-1)
a054429_list = f [1..] where
f xs@(x:_) = reverse us ++ f vs where (us, vs) = splitAt x xs
(R)
maxblock <- 10 # by choice
a <- NULL
for(m in 0:maxblock) a <- c(a, rev(2^m:(2^(m+1)-1)))
a
(Python)
from itertools import count, islice
def A054429_gen(): # generator of terms
return (m for n in count(0) for m in range((1<<n+1)-1, (1<<n)-1, -1))
|
|
CROSSREFS
|
This is Guy Steele's sequence GS(6, 5) (see A135416).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|