A072376 -id:A072376 - cp's OEIS frontend

A266348 a(1) = 1; for n > 1, a(n) = A004001(n+1) - A072376(n).

1, 1, 1, 1, 2, 2, 2, 1, 2, 3, 3, 4, 4, 4, 4, 1, 2, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10, 10, 11, 11, 11, 12, 13, 13, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, 15, 15, 16, 16, 16, 17, 18, 19, 19, 20, 21, 21

Offset: 1

Antti Karttunen, Jan 22 2016

When the terms are arranged as successively larger batches of 2^n, the terms A(n,k), k = 1 .. 2^n, on row n give the cumulative number of 1's encountered since the beginning of the row n of similarly organized irregular table A265754, up to and including the k-th term on that row:
1;
1, 1;
1, 2, 2, 2;
1, 2, 3, 3, 4, 4, 4, 4;
1, 2, 3, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8;
...

Antti Karttunen, Table of n, a(n) for n = 1..8191

Cf. A000523, A004001, A072376, A265754.

lim = 100; b[1] = 1; b[2] = 1; b[n_] := b[n] = b[b[n - 1]] + b[n - b[n - 1]]; s = CoefficientList[Series[1/(2 - 2 x) (2 x - x^2 + Sum[ 2^(k - 1) x^2^k, {k, Floor@ Log2@ lim}]), {x, 0, lim}], x]; {1}~Join~Table[b[n + 1] - s[[n + 1]], {n, 2, lim}] (* Michael De Vlieger, Jan 26 2016, after Robert G. Wilson v at A004001 *)

(define (A266348 n) (if (= 1 n) 1 (- (A004001 (+ 1 n)) (A072376 n))))

a(1) = 1; for n > 1, a(n) = A004001(n+1) - A072376(n) = A004001(n+1) - 2^(A000523(n)-1).

A266349 a(n) = 1 + A053644(n) - A004001(n+1) = 1 + A072376(n) - A266348(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 1, 1, 1, 1, 8, 7, 6, 5, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 16, 15, 14, 13, 12, 12, 11, 10, 9, 9, 8, 7, 7, 6, 6, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 32, 31, 30, 29, 28, 27, 27, 26, 25, 24, 23, 23, 22, 21, 20, 20, 19, 18, 18, 17, 17, 17, 16, 15, 14, 14, 13, 12, 12, 11, 11, 11, 10

Offset: 1

Antti Karttunen, Jan 22 2016

nonn

Used in a recursive formula of A265754.

Antti Karttunen, Table of n, a(n) for n = 1..8191

Cf. A004001, A053644, A072376, A266348, A265754, A266640.

b[1] = 1; b[2] = 1; b[n_] := b[n] = b[b[n - 1]] + b[n - b[n - 1]]; Table[1 + 2^(Ceiling@ Log2[n + 1] - 1) - b[n + 1], {n, 96}] (* Michael De Vlieger, Jan 26 2016, after Robert G. Wilson v at A004001 *)

a(n) = 1 + A053644(n) - A004001(n+1).

a(n) = 1 + A072376(n) - A266348(n).

A053644 Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64

Offset: 0

Henry Bottomley, Mar 22 2000

Except for the initial term, 2^n appears 2^n times. - Lekraj Beedassy, May 26 2005
a(n) is the smallest k such that row k in triangle A265705 contains n. - Reinhard Zumkeller, Dec 17 2015
a(n) is the sum of totient function over powers of 2 <= n. - Anthony Browne, Jun 17 2016
Given positive n, reverse the bits of n and divide by 2^floor(log_2 n). Numerators are in A030101. Ignoring the initial 0, denominators are in this sequence. - Alonso del Arte, Feb 11 2020

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Transforms
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

See A000035 for least significant bit(n).
MASKTRANS transform of A055975 (prepended with 0), MASKTRANSi transform of A048678.
Bisection of A065267, A065279, A065291, A072376.
First differences of A063915. Cf. A076877, A073121.
This is Guy Steele's sequence GS(5, 5) (see A135416).
Equals for n >= 1 the first right hand column of A160464. - Johannes W. Meijer, May 24 2009
Diagonal of A088370. - Alois P. Heinz, Oct 28 2011
Cf. A265705, A000010.

a053644 n = if n <= 1 then n else 2 * a053644 (div n 2)
-- Reinhard Zumkeller, Aug 28 2014
a053644_list = 0 : concat (iterate (\zs -> map (* 2) (zs ++ zs)) [1])
-- Reinhard Zumkeller, Dec 08 2012, Oct 21 2011, Oct 17 2010

[0] cat [2^Ilog2(n): n in [1..90]]; // Vincenzo Librandi, Dec 11 2018

a:= n-> 2^ilog2(n):
seq(a(n), n=0..80);  # Alois P. Heinz, Dec 20 2016

A053644[n_] := 2^(Length[ IntegerDigits[n, 2]] - 1); A053644[0] = 0; Table[A053644[n], {n, 0, 74}] (* Jean-François Alcover, Dec 01 2011 *)
nv[n_] := Module[{c = 2^n}, Table[c, {c}]]; Join[{0}, Flatten[Array[nv, 7, 0]]] (* Harvey P. Dale, Jul 17 2012 *)

a(n)=my(k=1);while(k<=n,k<<=1);k>>1 \\ Charles R Greathouse IV, May 27 2011

a(n) = if(!n, 0, 2^exponent(n)) \\ Iain Fox, Dec 10 2018

def a(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1) # Indranil Ghosh, May 25 2017

def A053644(n): return 1<Chai Wah Wu, Jul 27 2022

(0 to 127).map(Integer.highestOneBit()) // _Alonso del Arte, Feb 26 2020

a(n) = a(floor(n / 2)) * 2.
a(n) = 2^A000523(n).
From n >= 1 onward, A053644(n) = A062383(n)/2.
a(0) = 0, a(1) = 1 and a(n+1) = a(n)*floor(n/a(n)). - Benoit Cloitre, Aug 17 2002
G.f.: 1/(1 - x) * (x + Sum_{k >= 1} 2^(k - 1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = (A003817(n) + 1)/2 = A091940(n) + 1. - Reinhard Zumkeller, Feb 15 2004
a(n) = Sum_{k = 1..n} (floor(2^k/k) - floor((2^k - 1)/k))*A000010(k). - Anthony Browne, Jun 17 2016
a(2^m+k) = 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 07 2016

A153141 Permutation of nonnegative integers: A059893-conjugate of A153151.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 20 2008

This permutation is induced by a wreath recursion a = s(a,b), b = (b,b) (i.e., binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on page 103 of the Bondarenko, Grigorchuk, et al. paper, starting from the active (swapping) state a and rewriting bits from the second most significant bit to the least significant end, continuing complementing as long as the first 1-bit is reached, which is the last bit to be complemented.
The automorphism group of infinite binary tree (isomorphic to an infinitely iterated wreath product of cyclic groups of two elements) embeds naturally into the group of "size-preserving Catalan bijections". Scheme-function psi gives an isomorphism that maps this kind of permutation to the corresponding Catalan automorphism/bijection (that acts on S-expressions). The following identities hold: *A069770 = psi(A063946) (just swap the left and right subtrees of the root), *A057163 = psi(A054429) (reflect the whole tree), *A069767 = psi(A153141), *A069768 = psi(A153142), *A122353 = psi(A006068), *A122354 = psi(A003188), *A122301 = psi(A154435), *A122302 = psi(A154436) and from *A154449 = psi(A154439) up to *A154458 = psi(A154448). See also comments at A153246 and A153830.
a(1) to a(2^n) is the sequence of row sequency numbers in a Hadamard-Walsh matrix of order 2^n, when constructed to give "dyadic" or Payley sequency ordering. - Ross Drewe, Mar 15 2014
In the Stern-Brocot enumeration system for positive rationals (A007305/A047679), this permutation converts the denominator into the numerator: A007305(n) = A047679(a(n)). - Yosu Yurramendi, Aug 01 2020

			18 = 10010 in binary and after complementing the second, third and fourth most significant bits at positions 3, 2 and 1, we get 1110, at which point we stop (because bit-1 was originally 1) and fix the rest, so we get 11100 (28 in binary), thus a(18)=28. This is the inverse of "binary adding machine". See pages 8, 9 and 103 in the Bondarenko, Grigorchuk, et al. paper.
19 = 10011 in binary. By complementing bits in (zero-based) positions 3, 2 and 1 we get 11101 in binary, which is 29 in decimal, thus a(19)=29.

A. Karttunen, Table of n, a(n) for n = 0..2047
Ievgen Bondarenko, Rostislav Grigorchuk, Rostyslav Kravchenko, Yevgen Muntyan, Volodymyr Nekrashevych, Dmytro Savchuk, and Zoran Sunic, Classification of groups generated by 3-state automata over a 2-letter alphabet, arXiv:0803.3555 [math.GR], 2008, pp. 8--9 & 103.
S. Wolfram and R. Lamy, Discussion on the NKS Forum
Index entries for sequences that are permutations of the natural numbers

Inverse: A153142. a(n) = A059893(A153151(A059893(n))) = A059894(A153152(A059894(n))) = A154440(A154445(n)) = A154442(A154443(n)). Corresponds to A069767 in the group of Catalan bijections. Cf. also A154435-A154436, A154439-A154448, A072376.
Differs from A006068 for the first time at n=14, where a(14)=10 while A006068(14)=11.
A240908-A240910 these give "natural" instead of "dyadic" sequency ordering values for Hadamard-Walsh matrices, orders 8,16,32. - Ross Drewe, Mar 15 2014

def ok(n): return n&(n - 1)==0
def a153151(n): return n if n<2 else 2*n - 1 if ok(n) else n - 1
def A(n): return (int(bin(n)[2:][::-1], 2) - 1)/2
def msb(n): return n if n<3 else msb(n/2)*2
def a059893(n): return A(n) + msb(n)
def a(n): return 0 if n==0 else a059893(a153151(a059893(n))) # Indranil Ghosh, Jun 09 2017

maxlevel <- 5 # by choice
a <- 1
for(m in 1:maxlevel){
a[2^m    ] <- 2^(m+1) - 1
a[2^m + 1] <- 2^(m+1) - 2
for (k in 1:(2^m-1)){
   a[2^(m+1) + 2*k    ] <- 2*a[2^m + k]
   a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1}
}
a <- c(0,a)
# Yosu Yurramendi, Aug 01 2020

Conjecture: a(n) = f(a(f(a(A053645(n)))) + A053644(n)) for n > 0 where f(n) = A054429(n) for n > 0 with f(0) = 0. - Mikhail Kurkov, Oct 02 2023
From Mikhail Kurkov, Dec 22 2023: (Start)
a(n) < 2^k iff n < 2^k for k >= 0.
Conjectured formulas:
a(2^m + k) = f(2^m + f(k)) for m >= 0, 0 <= k < 2^m with a(0) = 0.
a(n) = f(A153142(f(n))) for n > 0 with a(0) = 0. (End)

A153142 Permutation of nonnegative integers: A059893-conjugate of A153152.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 20 2008

This sequence can be also obtained by starting complementing n's binary expansion from the second most significant bit, continuing towards lsb-end until the first 0-bit is reached, which is the last bit to be complemented.

In the Stern-Brocot enumeration system for positive rationals (A007305/A047679), this permutation converts the numerator into the denominator: A047679(n) = A007305(a(n)). - Yosu Yurramendi, Aug 30 2020

			29 = 11101 in binary. By complementing bits in (zero-based) positions 3, 2 and 1 we get 10011 in binary, which is 19 in decimal, thus a(29)=19.

Inverse: A153141. a(n) = A059893(A153152(A059893(n))) = A059894(A153151(A059894(n))). Differs from A003188 for the first time at n=10, where a(10)=14 while A003188(10)=15. Cf. also A072376. Corresponds to A069768 in the group of Catalan bijections.

def ok(n): return n&(n - 1)==0
def a153152(n): return n if n<2 else (n + 1)/2 if ok(n + 1) else n + 1
def A(n): return (int(bin(n)[2:][::-1], 2) - 1)/2
def msb(n): return n if n<3 else msb(n/2)*2
def a059893(n): return A(n) + msb(n)
def a(n): return 0 if n==0 else  a059893(a153152(a059893(n))) # Indranil Ghosh, Jun 09 2017

maxlevel <- 5 # by choice
a <- 1
for(m in 1:maxlevel){
  a[2^(m+1) - 1] <- 2^m
  a[2^(m+1) - 2] <- 2^m + 1
  for (k in 0:(2^m-2)){
    a[2^(m+1) + 2*k    ] <- 2*a[2^m + k]
    a[2^(m+1) + 2*k + 1] <- 2*a[2^m + k] + 1}
}
a <- c(0, a)
# Yosu Yurramendi, Aug 30 2020

A154435 Permutation of nonnegative integers induced by Lamplighter group generating wreath recursion, variant 3: a = s(b,a), b = (a,b), starting from the state a.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

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

			475 = 111011011 in binary. Starting from the second most significant bit and, as we begin with the swapping state a, we complement the bits up to and including the first zero encountered and so the beginning of the binary expansion is complemented as 1001....., then, as we switch to the inactive state b, the following bits are kept same, again up to and including the first zero encountered, after which the binary expansion is 1001110.., after which we switch again to the active state (state a), which complements the two rightmost 1's and we obtain the final answer 100111000, which is 312's binary representation, thus a(475)=312.

A. Karttunen, Table of n, a(n) for n = 0..2047
I. Bondarenko, R. Grigorchuk, R. Kravchenko, Y. Muntyan, V. Nekrashevych, D. Savchuk, Z. Sunic, Classification of groups generated by 3-state automata over a 2-letter alphabet, pp. 8--9 & 103, arXiv:0803.3555 [math.GR], 2008.
R. I. Grigorchuk and A. Zuk, The lamplighter group as a group generated by a 2-state automaton and its spectrum, Geometriae Dedicata, vol. 87 (2001), no. 1-3, pp. 209-244.
S. Wolfram, R. Lamy, Discussion on the NKS Forum
Index entries for sequences related to groups
Index entries for sequences that are permutations of the natural numbers

Inverse: A154436. a(n) = A059893(A154437(A059893(n))) = A054429(A006068(A054429(n))). Corresponds to A122301 in the group of Catalan bijections. Cf. also A153141-A153142, A154439-A154448, A072376.

from sympy import floor
def a006068(n):
    s=1
    while True:
        ns=n>>s
        if ns==0: break
        n=n^ns
        s<<=1
    return n
def a054429(n): return 1 if n==1 else 2*a054429(floor(n/2)) + 1 - n%2
def a(n): return 0 if n==0 else a054429(a006068(a054429(n))) # Indranil Ghosh, Jun 11 2017

maxn <- 63 # by choice
a <- c(1,3,2) # If it were a <- 1:3, it would be A180200
for(n in 2:maxn){
  a[2*n  ] <- 2*a[n] + (a[n]%%2 == 0)
  a[2*n+1] <- 2*a[n] + (a[n]%%2 != 0)  }
a
# Yosu Yurramendi, Jun 21 2020

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

A154436 Permutation of nonnegative integers induced by Lamplighter group generating wreath recursion, variant 1: a = s(a,b), b = (a,b), starting from the state a.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

This permutation is induced by the first Lamplighter group generating wreath recursion a = s(a,b), b = (a,b) (i.e. binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on page 104 of Bondarenko, Grigorchuk, et al. paper, starting from the active (swapping) state a and rewriting bits from the second most significant bit to the least significant end. It is the same automaton as given in figure 1 on page 211 of Grigorchuk and Zuk paper. Note that the fourth wreath recursion on page 104 of Bondarenko, et al. paper induces similarly the binary reflected Gray code A003188 (A054429-reflected conjugate of this permutation) and the second one induces Gray Code's inverse permutation A006068.

			312 = 100111000 in binary. Starting from the second most significant bit and, as we begin with the swapping state a, we complement the bits up to and including the first one encountered and so the beginning of the binary expansion is complemented as 1110....., then, as we switch to the inactive state b, the following bits are kept same, up to and including the first zero encountered, after which the binary expansion is 1110110.., after which we switch again to the complementing mode (state a) and we obtain 111011011, which is 475's binary representation, thus a(312)=475.

A. Karttunen, Table of n, a(n) for n = 0..2047
S. Wolfram, R. Lamy, Discussion on the NKS Forum
Index entries for sequences related to groups
Index entries for sequences that are permutations of the natural numbers

Inverse: A154435.
a(n) = A059893(A154438(A059893(n))) = A054429(A003188(A054429(n))).
Corresponds to A122302 in the group of Catalan bijections.
Cf. also A153141-A153142, A154439-A154448, A072376.

Function[s, Map[s[[#]] &, BitXor[#, Floor[#/2]] & /@ s]]@ Flatten@ Table[Range[2^(n + 1) - 1, 2^n, -1], {n, 0, 6}] (* Michael De Vlieger, Jun 11 2017 *)

a003188(n) = bitxor(n, n>>1);
a054429(n) = 3<<#binary(n\2) - n - 1;
a(n) = if(n==0, 0, a054429(a003188(a054429(n)))); \\ Indranil Ghosh, Jun 11 2017

from sympy import floor
def a003188(n): return n^(n>>1)
def a054429(n): return 1 if n==1 else 2*a054429(floor(n/2)) + 1 - n%2
def a(n): return 0 if n==0 else a054429(a003188(a054429(n))) # Indranil Ghosh, Jun 11 2017

maxn <- 63 # by choice
a <- c(1, 3, 2)
for(n in 2:maxn){
  if(n%%2 == 0) {a[2*n] <- 2*a[n]+1 ; a[2*n+1] <- 2*a[n]}
  else          {a[2*n] <- 2*a[n]   ; a[2*n+1] <- 2*a[n]+1}
}
(a <- c(0,a))
# Yosu Yurramendi, Apr 10 2020

a(0) = 0, a(1) = 1, a(2) = 3, a(3) = 2,
if n > 3 and n even a(2*n) = 2*n + 1, a(2*n+1) = 2*a(n),
if n > 3 and n odd  a(2*n) = 2*a(n) , a(2*n+1) = 2*a(n) + 1. - Yosu Yurramendi, Apr 10 2020

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

A255071 Number of steps required to reach (2^n)-2 from 2^(n+1)-2 by iterating the map x -> x - (number of runs in binary representation of x).

Original entry on oeis.org

1, 2, 3, 5, 9, 16, 29, 53, 97, 178, 328, 608, 1134, 2126, 4001, 7552, 14292, 27115, 51565, 98274, 187657, 358982, 687944, 1320793, 2540702, 4896919, 9456143, 18291753, 35435799, 68731296, 133436379, 259238717, 503912508, 979923792, 1906297165, 3709809375, 7222584181

Offset: 1

Antti Karttunen, Feb 14 2015

nonn

First differences of A255061 and A255062.
A255069 gives the first differences of this sequence.
Cf. A005811, A079944, A236840, A255056, A255120, A255121, A255063, A255064, A255072, A255125, A255126, A254119.
Analogous sequences: A213709, A219661.
a(n) differs from A192804(n+1) for the first time at n=11, where a(11) = 328, while A192804(12) = 327.

A005811(n) = hammingweight(bitxor(n,n\2));
A255071(n) = { my(k, i); k = (2^(n+1))-2; i = 1; while(1, k = k - A005811(k); if(!bitand(k+1,k+2),return(i),i++)); };
for(n=1, 48, write("b255071.txt", n, " ", A255071(n)));

(define (A255071 n) (- (A255072 (- (expt 2 (+ n 1)) 2)) (A255072 (- (expt 2 n) 2))))
(define (A255071shifted n) (add (COMPOSE A079944off2 A255056) (A255062 n) (A255061 (+ 1 n))))
(define (A079944off2 n) (A000035 (floor->exact (/ n (A072376 n))))) ;; Cf.
A079944.
;; Shifted variant gives: (map A255071shifted (iota 16)) --> (0 1 2 3 5 9 16 29 53 97 178 328 608 1134 2126 4001)

a(n) = A255072((2^(n+1))-2) - A255072((2^n)-2).
a(n) = A255061(n+1) - A255061(n).
a(n) = A255125(n) + A255126(n).
a(n) = A255063(n) + A255064(n).
Other identities and observations:
It seems that a(n) <= A213709(n) for all n >= 1. A254119 gives the difference between these two sequences.
From Antti Karttunen, Feb 21 2015: (Start)
For n>1, a(n-1) = Sum_{k=A255062(n) .. A255061(n+1)} secondmsb(A255056(k)).
Here secondmsb is implemented by the starting offset 2 version of A079944, and effectively gives the second most significant bit in the binary expansion of n. The formula follows from the semi-regular nature of number-of-runs beanstalk, as in the upper half of any next higher range [A255062(n+1) .. A255061(n+2)] of its infinite trunk (A255056), the beanstalk imitates its behavior in the range [A255062(n) .. A255061(n+1)].
(End)

a(37) added by Antti Karttunen, Feb 19 2015

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

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, 30, 31, 24, 25, 27, 26, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 56, 57, 58, 59, 60, 61, 62, 63, 48, 49, 50, 51, 54, 55, 52, 53, 64, 65, 66, 67, 68, 69, 70, 71

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 inactive (fixing) state a 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, not starting before at the thirdmost significant bit), as long as the first zero is encountered, which is also complemented if its distance to the most significant bit is even, after which the remaining bits are left intact. E.g. 121 = 1111001 in binary. Complementing its thirdmost significant bit and the first zero-bit two positions right of it (i.e. bit-2, 4 steps to the most significant bit, bit-6), we obtain "11011.." after which the rest of the bits stay same, so we get 1101101, which is 109's binary representation, thus a(121)=109. On the other hand, 125 = 1111101 in binary and the transducer complements the bits at positions 4 and 2, yielding 11010.. and then switches to the fixing state at the zero encounted at bit-position 1, without complementing it (as it is 5 steps from the msb) and the rest are fixed, so we get 1101001, which is 105's binary representation, thus a(125)=105.

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 related to groups
Index entries for sequences that are permutations of the natural numbers

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

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

A154448 Permutation of nonnegative integers induced by wreath recursion a=s(b,c), b=s(c,a), c=(c,c), starting from state a, rewriting bits from the second most significant bit toward the least significant end.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

This permutation of natural numbers is induced by the first generator of group 2861 mentioned on page 144 of "Classification of groups generated by 3-state automata over a 2-letter alphabet" paper. It can be computed by starting scanning n's binary expansion rightward from the second most significant bit, complementing every bit down to and including A) either the first 0-bit at even distance from the most significant bit or B) the first 1-bit at odd distance from the most significant bit.

			25 = 11001 in binary, the first zero-bit at odd distance from the msb is immediately at where we start (at the second most significant bit), so we complement it and fix the rest, yielding 10001 (17 in binary), thus a(25)=17.

Antti Karttunen, Table of n, a(n) for n = 0..2047
Bondarenko, Grigorchuk, Kravchenko, Muntyan, Nekrashevych, Savchuk, and Sunic, Classification of groups generated by 3-state automata over a 2-letter alphabet, arXiv:0803.3555 [math.GR], 2008, p. 144.
Index entries for sequences that are permutations of the natural numbers

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

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

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

cp's OEIS Frontend

A266348 a(1) = 1; for n > 1, a(n) = A004001(n+1) - A072376(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A266349 a(n) = 1 + A053644(n) - A004001(n+1) = 1 + A072376(n) - A266348(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A053644 Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Scala

Formula

A153141 Permutation of nonnegative integers: A059893-conjugate of A153151.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

Formula

A153142 Permutation of nonnegative integers: A059893-conjugate of A153152.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

A154435 Permutation of nonnegative integers induced by Lamplighter group generating wreath recursion, variant 3: a = s(b,a), b = (a,b), starting from the state a.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

Extensions

A154436 Permutation of nonnegative integers induced by Lamplighter group generating wreath recursion, variant 1: a = s(a,b), b = (a,b), starting from the state a.

Views

Author

Keywords

Comments