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)
From Yosu Yurramendi, Mar 29 2017: (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
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
MAPLE
A054429 := n -> 3*2^ilog2(n) - n - 1:
seq(A054429(n), n = 1..70); # [Updated by Peter Luschny, Apr 24 2024]
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
(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