A072376 -id:A072376 - cp's OEIS frontend

A080541 In binary representation: keep the first digit and left-rotate the others.

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

Offset: 1

Reinhard Zumkeller, Feb 20 2003

Permutation of natural numbers: let r(n,0)=n, r(n,k)=a(r(n,k-1)) for k>0, then r(n,floor(log_2(n))) = n and for n>1: r(n,floor(log_2(n))-1) = A080542(n).

Discarding their most significant bit, binary representations of numbers present in each cycle of this permutation form a distinct equivalence class of binary necklaces, thus there are A000031(n) separate cycles in each range [2^n .. (2^(n+1))-1] (for n >= 0) of this permutation. A256999 gives the largest number present in n's cycle. - Antti Karttunen, May 16 2015

			a(20)=a('10100')='11000'=24; a(24)=a('11000')='10001'=17.

Inverse: A080542.
Cf. A000031, A003986, A053644, A053645, A000523, A007088, A079944, A080413, A080543, A054429, A256999, A257250.
The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.

f:= proc(n) local d;
   d:= ilog2(n);
   if n >= 3/2*2^d then 2*n+1-2^(d+1) else 2*n - 2^d fi
end proc:
map(f, [$1..100]); # Robert Israel, May 19 2015

A080541[n_] := FromDigits[Join[{First[#]}, RotateLeft[Rest[#]]], 2] & [IntegerDigits[n, 2]];
Array[A080541, 100] (* Paolo Xausa, May 13 2025 *)

def A080541(n): return ((n&(m:=1< 1 else n  # Chai Wah Wu, Jan 22 2023

maxlevel <- 6 # by choice
a <- 1:3
for(m in 1:maxlevel) for(k in 0:(2^(m-1)-1)){
a[2^(m+1)       + 2*k    ] = 2*a[2^m           + k]
a[2^(m+1)       + 2*k + 1] = 2*a[2^m + 2^(m-1) + k]
a[2^(m+1) + 2^m + 2*k    ] = 2*a[2^m           + k] + 1
a[2^(m+1) + 2^m + 2*k + 1] = 2*a[2^m + 2^(m-1) + k] + 1
}
a
# Yosu Yurramendi, Oct 12 2020

(define (A080541 n) (if (< n 2) n (A003986bi (A053644 n) (+ (* 2 (A053645 n)) (A079944off2 n))))) ;; A003986bi gives the bitwise OR of its two arguments. See A003986.
;; Where A079944off2 gives the second most significant bit of n. (Cf. A079944):
(define (A079944off2 n) (A000035 (floor->exact (/ n (A072376 n)))))
;; Antti Karttunen, May 16 2015

From Antti Karttunen, May 16 2015: (Start)
a(1) = 1; for n > 1, a(n) = A053644(n) bitwise_OR (2*A053645(n) + second_most_significant_bit_of(n)). [Here bitwise_OR is a 2-argument function given by array A003986 and second_most_significant_bit_of gives the second most significant bit (0 or 1) of n larger than 1. See A079944.]
Other identities. For all n >= 1:
a(n) = A059893(A080542(A059893(n))).
a(n) = A054429(a(A054429(n))).
(End)
A080542(a(n)) = a(A080542(n)) = n. [A080542 is the inverse permutation.]
From Robert Israel, May 19 2015: (Start)
Let d = floor(log[2](n)).  If n >= 3*2^(d-1) then a(n) = 2*n + 1 - 2^(d+1), otherwise a(n) = 2*n - 2^d.
G.f.: 2*x/(x-1)^2 + Sum_{n>=1} x^(2^n)+(2^n-1)*x^(3*2^(n-1)))/(x-1). (End)

A080542 In binary representation: keep the first digit and rotate right the others.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Feb 20 2003

Permutation of natural numbers with inverse = A080541: A080541(a(n)) = a(A080541(n)) = n;
let r(n,0)=n, r(n,k)=a(r(n,k-1)) for k>0, then r(n,floor(log_2(n))) = n and for n>1: r(n,floor(log_2(n))-1) = A080541(n).
Discarding their most significant bit, binary representations of numbers present in each cycle of this permutation form a distinct equivalence class of binary necklaces, thus there are A000031(n) separate cycles in each range [2^n .. (2^(n+1))-1] (for n >= 0) of this permutation.  A256999 gives the largest number present in n's cycle. - Antti Karttunen, May 16 2015

			a(20) = a('10100') = '10010' = 18.
a(25) = a('11001') = '11100' = 28.

Inverse: A080541.
Cf. A000031, A000035, A000523, A004526, A007088, A053644, A053645, A054429, A072376, A080414, A080544, A256999, A257250.
The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.

kfd[n_]:=Module[{a,b},{a,b}=TakeDrop[IntegerDigits[n,2],1];FromDigits[ Join[a,RotateRight[b]],2]]; Array[kfd,80] (* The program uses the TakeDrop function from Mathematica version 10 *) (* Harvey P. Dale, Feb 12 2016 *)

def A080542(n): return (1+(n&1))*(1<>1) if n > 1 else n # Chai Wah Wu, Jan 22 2023

nmax <- 31 # by choice
a <- 1:3
for(n in 1:nmax) for(k in 0:3)
a[4*n + k] = 2*a[2*n + (k == 1 | k == 3)] + (k == 2 | k == 3)
a
# Yosu Yurramendi, Sep 05 2020

(define (A080542 n) (if (< n 2) n (+ (A053644 n) (+ (* (A000035 n) (A072376 n)) (A004526 (A053645 n))))))  ;; Antti Karttunen, May 16 2015

a(n) = 2^log2(n) + floor((n-2^log2(n))/2) + (n mod 2)*2^(log2(n)-1), where log2(n) is the integer part of base-2 logarithm.
From Antti Karttunen, May 16 2015: (Start)
a(1) = 1; for n > 1, a(n) = A053644(n) + (A000035(n)*A072376(n)) + A004526(A053645(n)). [Essentially the same formula but represented with A-numbers.]
Other identities. For all n >= 1:
a(n) = A059893(A080541(A059893(n))).
a(n) = A054429(a(A054429(n))).
(End)

A073137 a(n) is the least number whose binary representation has the same number of 0's and 1's as n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 5, 7, 8, 9, 9, 11, 9, 11, 11, 15, 16, 17, 17, 19, 17, 19, 19, 23, 17, 19, 19, 23, 19, 23, 23, 31, 32, 33, 33, 35, 33, 35, 35, 39, 33, 35, 35, 39, 35, 39, 39, 47, 33, 35, 35, 39, 35, 39, 39, 47, 35, 39, 39, 47, 39, 47, 47, 63, 64, 65, 65, 67, 65, 67, 67, 71, 65

Offset: 0

Reinhard Zumkeller, Jul 16 2002

nonn

A023416(a(n)) = A023416(n), A000120(a(n)) = A000120(n).

Fixed points are { 0 } union { A099627 }. - Alois P. Heinz, Jan 30 2025

			a(20)=17, as 20='10100' and 17 is the smallest number having two 1's and three 0's: 17='10001', 18='10010', 20='10100' and 24='11000'.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A007088, A073138, A000523, A073139, A073140, A073141, A072376, A099627.

a:= n-> (l-> (2^nops(l)+2^add(i, i=l))/2-1)(Bits[Split](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 26 2021

lnb[n_]:=Module[{sidn=Sort[IntegerDigits[n,2]]},FromDigits[Join[{1}, Most[ sidn]],2]]; Join[{0},Array[lnb,80]] (* Harvey P. Dale, Aug 04 2014 *)

a(n) = if(n==0,0, 1<Kevin Ryde, Jun 26 2021

def a(n):
    b = bin(n)[2:]; z = b.count('0'); w = len(b) - z
    return int('1'*(w > 0) + '0'*z + '1'*(w-1), 2)
print([a(n) for n in range(73)]) # Michael S. Branicky, Jun 26 2021

def a(n): b = bin(n)[2:]; return int(b[0] + "".join(sorted(b[1:])), 2)
print([a(n) for n in range(73)]) # Michael S. Branicky, Jun 26 2021

a(0)=0, a(1)=1; for n > 1, let C = 2^(floor(log_2(n))-1) = A072376(n); then a(n) = a(n-C) + C if n < 3*C; otherwise a(n) = 2*a(n - 2*C) + 1. [corrected by Jon E. Schoenfield, Jun 27 2021]

For n > 0: a(n) = (2^(A000120(n) - 1)) * (2^A023416(n) + 1) - 1. - Corrected by Michel Marcus, Nov 15 2013

A154442 Permutation of nonnegative integers: the inverse of A154441.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154441. a(n) = A153141(A154444(n)) = A054429(A154446(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154452 in the group of Catalan bijections.

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A154446 Permutation of nonnegative integers: The inverse of A154445.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154445. a(n) = A153142(A154440(n)) = A054429(A154442(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154456 in the group of Catalan bijections.

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A154440 Permutation of nonnegative integers: the inverse of A154439.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154439. a(n) = A153141(A154446(n)) = A054429(A154444(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154442-A154448. Corresponds to A154450 in the group of Catalan bijections.

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A154441 Permutation of nonnegative integers induced by Basilica group generating wreath recursion: a = (1,b), b = s(1,a), starting from the active (swapping) state b.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

This permutation is induced by the Basilica group generating wreath recursion a = (1,b), b = s(1,a) (i.e. binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on the page 40 of Bartholdi and Virag paper, starting from the active (switching) state b and rewriting bits from the second most significant bit to the least significant end.

			Starting from the second most significant bit, we continue complementing every second bit (in this case, starting from the second most significant bit), as long as the first zero is encountered, which is also complemented if its distance to the most significant bit is odd, after which the remaining bits are left intact. E.g. 121 = 1111001 in binary. Complementing its second and fourth most significant bits (positions 5 & 3) and stopping at the first zero-bit at position 2 (which is not complemented, as its distance to the msb is 6), we obtain "10100.." after which the rest of the bits stay same, so we get 1010001, which is 81's binary representation, thus a(121)=81. On the other hand, 125 = 1111101 in binary and the transducer complements the bits at positions 5, 3 and also the first zero at the position 1 (because at odd distance from the msb), yielding 101011., after which the remaining bit stays same, thus we get 1010111, which is 87's binary representation, thus a(125)=87.

R. I. Grigorchuk and A. Zuk, Spectral properties of a torsion free weakly branch group defined by a three state automaton, Contemporary Mathematics 298 (2002), 57--82.

A. Karttunen, Table of n, a(n) for n = 0..2047
L. Bartholdi and B. Virag, Amenability via random walks, arXiv:math/0305262 [math.GR], 2003.
L. Bartholdi and B. Virag, Amenability via random walks, Duke Math. J. Volume 130, Number 1 (2005), 39--56.
Index entries for sequences that are permutations of the natural numbers

Inverse: A154442. a(n) = A154443(A153142(n)) = A054429(A154445(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154451 in the group of Catalan bijections.

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A154443 Permutation of nonnegative integers induced by Basilica group generating wreath recursion: a = (b,1), b = s(a,1), starting from the inactive (fixing) state a.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154444. a(n) = A154441(A153141(n)) = A054429(A154439(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154453 in the group of Catalan bijections.

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A154445 Permutation of nonnegative integers induced by Basilica group generating wreath recursion: a = (b,1), b = s(a,1), starting from the active (swapping) state b.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154446. a(n) = A154439(A153141(n)) = A054429(A154441(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154455 in the group of Catalan bijections.

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A154444 Permutation of nonnegative integers: The inverse of A154443.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

Inverse: A154443. a(n) = A153142(A154442(n)) = A054429(A154440(A054429(n))). Cf. A072376, A153141-A153142, A154435-A154436, A154439-A154448. Corresponds to A154454 in the group of Catalan bijections.

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

cp's OEIS Frontend

A080541 In binary representation: keep the first digit and left-rotate the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

R

Scheme

Formula

A080542 In binary representation: keep the first digit and rotate right the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

R

Scheme

Formula

A073137 a(n) is the least number whose binary representation has the same number of 0's and 1's as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A154442 Permutation of nonnegative integers: the inverse of A154441.

Views

Author

Keywords

Links

Crossrefs

Extensions

A154446 Permutation of nonnegative integers: The inverse of A154445.

Views

Author

Keywords

Links

Crossrefs

Extensions

A154440 Permutation of nonnegative integers: the inverse of A154439.

Views

Author

Keywords

Links

Crossrefs

Extensions

A154441 Permutation of nonnegative integers induced by Basilica group generating wreath recursion: a = (1,b), b = s(1,a), starting from the active (swapping) state b.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A154443 Permutation of nonnegative integers induced by Basilica group generating wreath recursion: a = (b,1), b = s(a,1), starting from the inactive (fixing) state a.

Views

Author

Keywords