|
%I #87 Jul 27 2023 11:00:38
%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 ReflectBinTreePermutation := n -> (((3*(2^floor_log_2(n)))-n)-1); # floor_log_2(x) gives floor(log_2(x)), but floor(log_2(x)) is not healthy in Maple, so use this:
%p 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;
%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_
|
