A165199 -id:A165199 - cp's OEIS frontend

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.

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

Offset: 1

Antti Karttunen

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)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf 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

See also A054424, A054430.
{A000027, A054429, A059893, A059894} form a 4-group.
Cf. A053644, A115303, A115304, A115305, A115306, A115307, A115308, A115309, A106649.
This is Guy Steele's sequence GS(6, 5) (see A135416).

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

A054429 := n -> 3*2^ilog2(n) - n - 1:
seq(A054429(n), n = 1..70); # [Updated by Peter Luschny, Apr 24 2024]

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

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

from itertools import count, islice
def A054429_gen(): # generator of terms
    return (m for n in count(0) for m in range((1<A054429_list = list(islice(A054429_gen(),30)) # Chai Wah Wu, Jul 27 2023

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

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
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
a(n) = 3*A053644(n) - n - 1. - Alan Michael Gómez Calderón, Feb 28 2025

A258746 Permutation of the positive integers: this permutation transforms the enumeration system of positive irreducible fractions A007305/A047679 (Stern-Brocot) into the enumeration system A162909/A162910 (Bird), and vice versa.

Original entry on oeis.org

1, 2, 3, 5, 4, 7, 6, 10, 11, 8, 9, 14, 15, 12, 13, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 42, 43, 40, 41, 46, 47, 44, 45, 34, 35, 32, 33, 38, 39, 36, 37, 58, 59, 56, 57, 62

Offset: 1

Yosu Yurramendi, Jun 09 2015

nonn

As A117120 the permutation is self-inverse. Except for fixed points 1, 2, 3 it consists completely of 2-cycles: (4,5), (6,7), (8,10), (9,11), (12,14), (13,15), (16,21), (17,20), ..., (24,29), ..., (32,42), ... .

Yosu Yurramendi, Table of n, a(n) for n = 1..20001
Index entries for sequences that are permutations of the natural numbers

Cf. A117120.

a <- 1:3
maxn <- 50 # by choice
#
for(n in 2:maxn){
  m <- floor(log2(n))
  if(m%%2 == 0) {
    a[2*n  ] <- 2*a[n]
    a[2*n+1] <- 2*a[n]+1 }
  else {
    a[2*n  ] <- 2*a[n]+1
    a[2*n+1] <- 2*a[n]   }
}
#
a
# Yosu Yurramendi, Jun 09 2015

# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # by choice
a <- 1:3
for(n in 4:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
anbit <- nbit
ifelse(floor(log2(n)) %% 2 == 0,
   anbit[seq(1, length(anbit)-1, 2)] <- 1 - anbit[seq(1, length(anbit)-1, 2)],
   anbit[seq(2, length(anbit) - 1, 2)] <- 1 - anbit[seq(2, length(anbit)-1, 2)])
a <- c(a, sum(anbit*2^(0:(length(anbit)-1))))
}
a
# Yosu Yurramendi, May 29 2021

a(1) = 1, a(2) = 2, a(3) = 3. For n >= 2, m = floor(log_2(n)). If m even, then a(2*n) = 2*a(n) and a(2*n+1) = 2*a(n)+1. If m odd, then a(2*n) = 2*a(n)+1 and a(2*n+1) = 2*a(n).
From Yosu Yurramendi, Mar 23 2017: (Start)
A258996(a(n)) = a(A258996(n)) for n > 0;
A117120(a(n)) = a(A117120(n)) for n > 0;
A092569(a(n)) = a(A092569(n)) for n > 0;
A063946(a(n)) = a(A063946(n)) for n > 0;
A054429(a(n)) = a(A054429(n)) = A165199(n) for n > 0;
A065190(a(n)) = a(A065190(n)) for n > 0. (End)
a(n) = A054429(A165199(n)). - Alan Michael Gómez Calderón, Mar 08 2025

A371442 For any positive integer n with binary digits (b_1, ..., b_w) (where b_1 = 1), the binary digits of a(n) are (b_1, b_3, ..., b_{2*ceiling(w/2)-1}); a(0) = 0.

Original entry on oeis.org

0, 1, 1, 1, 2, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 3, 4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 8, 9, 8, 9, 10, 11, 10, 11, 8, 9, 8, 9, 10, 11, 10, 11, 12, 13, 12

Offset: 0

Rémy Sigrist, Mar 24 2024

In other words, we keep odd-indexed bits.

For any v > 0, the value v appears A003945(A070939(v)) times in the sequence.

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     1       1          1
   2     1      10          1
   3     1      11          1
   4     2     100         10
   5     3     101         11
   6     2     110         10
   7     3     111         11
   8     2    1000         10
   9     2    1001         10
  10     3    1010         11
  11     3    1011         11
  12     2    1100         10
  13     2    1101         10
  14     3    1110         11
  15     3    1111         11

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

See A371459 for the sequence related to even-indexed bits.
See A059905 and A063694 for similar sequences.
Cf. A000695, A001196, A003945, A070939, A165199, A371461.

A371442[n_] := FromDigits[IntegerDigits[n, 2][[1;;-1;;2]], 2];
Array[A371442, 100, 0] (* Paolo Xausa, Mar 28 2024 *)

a(n) = { my (b = binary(n)); fromdigits(vector(ceil(#b/2), k, b[2*k-1]), 2); }

Python
```
def a(n): return int(bin(n)[::2], 2)
```

a(A000695(n)) = n.
a(A001196(n)) = n.
a(A165199(n)) = a(n).

A375183 In the binary expansion of n, complement bits at even positions and to the right of a 1 (the most significant bit corresponding to position 1).

Original entry on oeis.org

0, 1, 3, 2, 6, 7, 4, 5, 12, 13, 15, 14, 8, 9, 11, 10, 24, 25, 26, 27, 30, 31, 28, 29, 16, 17, 18, 19, 22, 23, 20, 21, 48, 49, 51, 50, 52, 53, 55, 54, 60, 61, 63, 62, 56, 57, 59, 58, 32, 33, 35, 34, 36, 37, 39, 38, 44, 45, 47, 46, 40, 41, 43, 42, 96, 97, 98, 99

Offset: 0

Rémy Sigrist, Aug 03 2024

This sequence is a self-inverse permutation of the nonnegative integers.

			For n = 9: the binary expansion of 9 is "1001": the bit at position 2 (0) sits to the right of a 1 so we complement it, the bit at position 4 (1) sits to the right of a 0 so we keep it; the binary expansion of a(9) is "1101" and a(9) = 13.

Cf. A063946, A165199, A375184.

a(n) = { my (b = binary(n)); forstep (k = 2, #b, 2, if (b[k-1], b[k] = 1-b[k];);); fromdigits(b, 2); }

a(floor(n/2)) = floor(a(n)/2).

A375184 In the binary expansion of n, complement bits at even positions and to the right of a 0 (the most significant bit corresponding to position 1).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 10, 11, 13, 12, 14, 15, 18, 19, 16, 17, 20, 21, 22, 23, 26, 27, 24, 25, 28, 29, 30, 31, 37, 36, 38, 39, 33, 32, 34, 35, 41, 40, 42, 43, 45, 44, 46, 47, 53, 52, 54, 55, 49, 48, 50, 51, 57, 56, 58, 59, 61, 60, 62, 63, 74, 75, 72, 73

Offset: 0

Rémy Sigrist, Aug 03 2024

This sequence is a self-inverse permutation of the nonnegative integers.

			For n = 9: the binary expansion of 9 is "1001": the bit at position 2 (0) sits to the right of a 1 so we keep it, the bit at position 4 (1) sits to the right of a 0 so we complement it; the binary expansion of a(9) is "1000" and a(9) = 8.

Cf. A063946, A165199, A375183.

a(n) = { my (b = binary(n)); forstep (k = 2, #b, 2, if (!b[k-1], b[k] = 1-b[k];);); fromdigits(b, 2); }

a(floor(n/2)) = floor(a(n)/2).

cp's OEIS Frontend

A245443 Permutation of nonnegative integers: a(n) = A165199(A193231(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A245444 Permutation of nonnegative integers: a(n) = A193231(A165199(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

R

Formula

A258746 Permutation of the positive integers: this permutation transforms the enumeration system of positive irreducible fractions A007305/A047679 (Stern-Brocot) into the enumeration system A162909/A162910 (Bird), and vice versa.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

R

R

Formula

A371442 For any positive integer n with binary digits (b_1, ..., b_w) (where b_1 = 1), the binary digits of a(n) are (b_1, b_3, ..., b_{2*ceiling(w/2)-1}); a(0) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A375183 In the binary expansion of n, complement bits at even positions and to the right of a 1 (the most significant bit corresponding to position 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A375184 In the binary expansion of n, complement bits at even positions and to the right of a 0 (the most significant bit corresponding to position 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula