login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 144
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

a(n) gives the position of the inverse of the n-th term in the full Stern Brocot tree: A007305(a(n)+2) = A047679(n) and A047679(a(n)) = A007305(n+2). - Reinhard Zumkeller, Dec 22 2008

From Gary W. Adamson, Jun 21 2012: (Start)

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)

From Indranil Ghosh, Jan 19 2017: (Start)

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)

A002487(a(n)) = A002487(n+1), A002487(a(n)+1) = A002487(n), n > 0.

A162909(a(n)) = A162910(n), A162910(a(n)) = A162909(n), n > 0.

A162911(a(n)) = A162912(n), A162912(a(n)) = A162911(n), n > 0.

A071766(a(n)) = A245326(n), A245326(a(n)) = A071766(n), n > 0.

A229742(a(n)) = A245325(n), A245325(a(n)) = A229742(n), n > 0.

A020651(a(n)) = A245327(n), A245327(a(n)) = A020651(n), n > 0.

A020650(a(n)) = A245328(n), A245328(a(n)) = A020650(n), n > 0. (End)

From Yosu Yurramendi, Mar 29 2017 : (Start)

A063946(a(n)) = a(A063946(n)) = A117120(n), n > 0.

A065190(a(n)) = a(A065190(n)) = A092569(n), n > 0.

A258746(a(n)) = a(A258746(n)) = A165199(n), n > 0.

A258996(a(n)) = a(A258996(n)), n > 0.

A117120(a(n)) = a(A117120(n)), n > 0.

A092569(a(n)) = a(A092569(n)), n > 0. (End)

LINKS

R. Zumkeller, Table of n, a(n) for n = 1..10000

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

Index entries for sequences that are permutations of the natural numbers

Index entries for sequences related to binary expansion of n

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

1/(1-x) * ((x-2x^2)/(1-x) + Sum_{k>=0} 3*2^k*x^2^k). - Ralf Stephan, Sep 15 2003

A000120(a(n)) = A000120(A059894(n)) = A023416(n) + 1. - Ralf Stephan, Oct 05 2003

A115310(n, 1) = a(n). - Reinhard Zumkeller, Jan 20 2006

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

a(n) = A117120(A063946(n)) = A063946(A117120(n)) = A092569(A065190(n)) = A065190(A092569(n)), n > 0. - Yosu Yurramendi, Apr 10 2017

MAPLE

ReflectBinTreePermutation := n -> (((3*(2^floor_log_2(n)))-n)-1); # floor_log_2(x) gives [log2(x)], but floor(log[2](x)) is not healthy in Maple, so use this:

floor_log_2 := proc(n) local nn, i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi: nn := floor(nn/2); od; end;

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

-- Reinhard Zumkeller, Jun 01 2015, Feb 21 2014

(PARI) A054429(n)= 3<<#binary(n\2)-n-1 \\ M. F. Hasler, Aug 18 2014

(R)

maxblock <- 10 # by choice

a <- NULL

for(m in 0:maxblock) a <- c(a, rev(2^m:(2^(m+1)-1)))

a

# Yosu Yurramendi, Mar 10 2017

CROSSREFS

See also A054424, A054430.

{A000027, A054429, A059893, A059894} form a 4-group.

Cf. A115303, A115304, A115305, A115306, A115307, A115308, A115309, A106649.

This is Guy Steele's sequence GS(6, 5) (see A135416).

Sequence in context: A071574 A276344 A276343 * A269398 A269397 A267107

Adjacent sequences:  A054426 A054427 A054428 * A054430 A054431 A054432

KEYWORD

nonn,easy,look

AUTHOR

Antti Karttunen

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 18 20:32 EST 2018. Contains 299330 sequences. (Running on oeis4.)