login
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.
213

%I #93 Apr 24 2024 12:45:33

%S 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,

%T 20,19,18,17,16,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,

%U 45,44,43,42,41,40,39,38,37,36,35,34,33,32,127,126,125,124,123,122,121

%N 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.

%C 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

%C From _Gary W. Adamson_, Jun 21 2012: (Start)

%C The mapping and conversion rules are as follows:

%C By rows, we have ...

%C 1;

%C 3, 2;

%C 7, 6, 5, 4;

%C 15, 14, 13, 12, 11, 10, 9, 8;

%C ... onto which we are to map one-half of the Stern-Brocot infinite Farey Tree:

%C 1/2

%C 1/3, 2/3

%C 1/4, 2/5, 3/5, 3/4

%C 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5

%C ...

%C 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)

%C From _Indranil Ghosh_, Jan 19 2017: (Start)

%C 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.

%C 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)

%C From _Yosu Yurramendi_, Mar 09 2017 (similar to Zumkeller's comment): (Start)

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

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

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

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

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

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

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

%C From _Yosu Yurramendi_, Mar 29 2017: (Start)

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

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

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

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

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

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

%H Reinhard Zumkeller, <a href="/A054429/b054429.txt">Table of n, a(n) for n = 1..10000</a>

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = ReflectBinTreePermutation(n).

%F a(n) = if n=1 then 1 else 2*a(floor(n/2)) + 1 - n mod 2. - _Reinhard Zumkeller_, Feb 18 2003

%F G.f.: 1/(1-x) * ((x-2x^2)/(1-x) + Sum_{k>=0} 3*2^k*x^2^k). - _Ralf Stephan_, Sep 15 2003

%F A000120(a(n)) = A000120(A059894(n)) = A023416(n) + 1. - _Ralf Stephan_, Oct 05 2003

%F A115310(n, 1) = a(n). - _Reinhard Zumkeller_, Jan 20 2006

%F a(1) = 1, a(2^(m+1) + k) = a(2^m+k) + 2^(m+1),

%F a(2^(m+1) + 2^m+k) = a(2^m+k) + 2^m, m >= 0, 0 <= k < 2^m. - _Yosu Yurramendi_, Apr 06 2017

%F a(n) = A117120(A063946(n)) = A063946(A117120(n)) = A092569(A065190(n)) = A065190(A092569(n)), n > 0. - _Yosu Yurramendi_, Apr 10 2017

%p A054429 := n -> 3*2^ilog2(n) - n - 1:

%p seq(A054429(n), n = 1..70); # [Updated by _Peter Luschny_, Apr 24 2024]

%t Flatten[Table[Range[2^(n+1)-1,2^n,-1],{n,0,6}]] (* _Harvey P. Dale_, Dec 17 2013 *)

%o (Haskell)

%o a054429 n = a054429_list !! (n-1)

%o a054429_list = f [1..] where

%o f xs@(x:_) = reverse us ++ f vs where (us, vs) = splitAt x xs

%o -- _Reinhard Zumkeller_, Jun 01 2015, Feb 21 2014

%o (PARI) A054429(n)= 3<<#binary(n\2)-n-1 \\ _M. F. Hasler_, Aug 18 2014

%o (R)

%o maxblock <- 10 # by choice

%o a <- NULL

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

%o a

%o # _Yosu Yurramendi_, Mar 10 2017

%o (Python)

%o from itertools import count, islice

%o def A054429_gen(): # generator of terms

%o return (m for n in count(0) for m in range((1<<n+1)-1,(1<<n)-1,-1))

%o A054429_list = list(islice(A054429_gen(),30)) # _Chai Wah Wu_, Jul 27 2023

%Y See also A054424, A054430.

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

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

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

%K nonn,easy,look

%O 1,2

%A _Antti Karttunen_