A154437 -id:A154437 - cp's OEIS frontend

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.

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

A153154 Permutation of natural numbers: A059893-conjugate of A006068.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 20 2008

A002487(1+a(n)) = A020651(n) and A002487(a(n)) = A020650(n). So, it generates the enumeration system of positive rationals based on Stern's sequence A002487. - Yosu Yurramendi, Feb 26 2020

Inverse: A153153. a(n) = A059893(A006068(A059893(n))).

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

# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 8 # by choice
a <- c(1, 3, 2)
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
  for(i in 2:(length(anbit) - 1))
    anbit[i] <- bitwXor(anbit[i], anbit[i - 1])  # ?bitwXor
  anbit[0:(length(anbit) - 1)] <- 1 - anbit[0:(length(anbit) - 1)]
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
(a <- c(0, a))
# Yosu Yurramendi, Oct 04 2021

From Yosu Yurramendi, Feb 26 2020: (Start)
a(1) = 1, for all n > 0 a(2*n) = 2*a(n) + 1, a(2*n+1) = 2*a(A065190(n)).
a(1) = 1, a(2) = 3, a(3) = 2, for all n > 1 a(2*n) = 2*a(n) + 1, and if n even a(2*n+1) = 2*a(n+1), else a(2*n+1) = 2*a(n-1).
a(n) = A054429(A231551(n)) = A231551(A065190(n)) = A284459(A054429(n)) =
       A332769(A284459(n)) = A258996(A154437(n)). (End)

A332769 Permutation of the positive integers: a(n) = A258996(A054429(n)) = A054429(A258996(n)).

Original entry on oeis.org

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

Offset: 1

Yosu Yurramendi, Feb 23 2020

nonn

Sequence is self-inverse: a(a(n)) = n.
A002487(1+a(n)) = A162911(n) and A002487(a(n)) = A162912(n). So, a(n) generates the enumeration system of positive rationals based on Stern's sequence A002487 called 'drib'.
Given n, one can compute a(n) by taking into account the binary representation of n, and by flipping every second bit starting from the lowest until reaching the highest 1, which is not flipped.

			n = 23 =  10111_2
            x x
          10010_2 = 18 = a(n).
n = 33 = 100001_2
          x x x
         110100_2 = 52 = a(n).

Yosu Yurramendi, Table of n, a(n) for n = 1..8191

Similar R-programs: A258996, A284447.

a(n) = bitxor(n, 2<Kevin Ryde, Mar 30 2021

maxrow <- 6 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)){
a[2^(m+1)+2*k  ] <- 2*a[2^(m+1)-1-k] + 1
a[2^(m+1)+2*k+1] <- 2*a[2^(m+1)-1-k]
}
a

# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # by choice
a <- c(1, 3, 2)
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
  anbit[seq(1, length(anbit) - 1, 2)] <- 1 - anbit[seq(1, length(anbit) - 1, 2)]
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
# Yosu Yurramendi, Mar 30 2021

a(A054429(n)) = A054429(a(n)) = A258996(n),
a(A258996(n)) = A258996(a(n)) = A054429(n).
a(n) = A284447(A065190(n)) = A065190(A284447(n)),
a(A065190(n)) = A065190(a(n)) = A284447(n),
a(A284447(n)) = A284447(a(n)) = A065190(n).
a(A231551(n)) = A154437(n), a(A154437(n)) = A231551(n).
a(A153154(n)) = A284459(n), a(A284459(n)) = A153154(n).
a(1) = 1, a(2) = 3, a(3) = 2; for n > 3, a(2*n) = 2*a(A054429(n)) + 1, a(2*n+1) = 2*a(A054429(n)).
a(1) = 1; for m >= 0 and 0 <= k < 2^m, a(2^(m+1)+2*k) = 2*a(2^(m+1)-1-k) + 1, a(2^(m+1)+2*k+1) = 2*a(2^(m+1)-1-k).

A154438 Permutation of nonnegative integers: A059893-conjugate of A154436.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

This permutation is induced by the same Lamplighter group generating wreath recursion (binary transducer) as A154436, starting from the active (swapping) state a, but in contrast to it, this one rewrites the bits from the least significant end up to the second most significant bit.

Inverse: A154437.

a(n) = A059893(A154436(A059893(n))) = A054429(A153153(A054429(n))).

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

a(0) = 0, a(1) = 1, m > 0, 0 <= k < 2^m a(2^(m+2)-1-2*k) = 2*a(2^m+k),

a(2^(m+1)+2*k) = 2*a(2^m+k) + 1. - Yosu Yurramendi, Apr 10 2020

cp's OEIS Frontend

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

A153154 Permutation of natural numbers: A059893-conjugate of A006068.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

R

R

Formula

A332769 Permutation of the positive integers: a(n) = A258996(A054429(n)) = A054429(A258996(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

R

R

Formula

A154438 Permutation of nonnegative integers: A059893-conjugate of A154436.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

R

Formula