A059893 -id:A059893 - cp's OEIS frontend

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

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

A065260 A057115 conjugated with A059893, inverse of A065259.

Original entry on oeis.org

2, 4, 1, 8, 6, 12, 3, 16, 10, 20, 5, 24, 14, 28, 7, 32, 18, 36, 9, 40, 22, 44, 11, 48, 26, 52, 13, 56, 30, 60, 15, 64, 34, 68, 17, 72, 38, 76, 19, 80, 42, 84, 21, 88, 46, 92, 23, 96, 50, 100, 25, 104, 54, 108, 27, 112, 58, 116, 29, 120, 62, 124, 31, 128, 66, 132, 33, 136, 70

Offset: 1

Antti Karttunen, Oct 28 2001

This permutation of N induces also such permutation of Z, that p(i)-i >= 0 for all i.

			G.f. = 2*x + 4*x^2 + x^3 + 8*x^4 + 6*x^5 + 12*x^6 + 3*x^7 + 16*x^8 + ...

Colin Barker, Table of n, a(n) for n = 1..1000
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers
Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

Cf. also A065171. The siteswap sequence (deltas) is A065261.

Vec(x*(2+4*x+x^2+8*x^3+2*x^4+4*x^5+x^6)/((1-x)^2*(1+x)^2*(1+x^2)^2) + O(x^100)) \\ Colin Barker, Oct 29 2016

{a(n) = if( n%2==0, n*2, n%4==1, n+1, n\2)}; /* Michael Somos, Nov 06 2016 */

a(n) = A059893(A057115(A059893(n))).
a(2*k+2) = 4*k+4, a(4*k+1) = 4*k+2, a(4*k+3) = 2*k+1. - Ralf Stephan, Jun 10 2005
G.f.: x*(x^6+4*x^5+2*x^4+8*x^3+x^2+4*x+2) / ((x-1)^2*(x+1)^2*(x^2+1)^2). - Colin Barker, Feb 18 2013
a(n) = 2*a(n-4) - a(n-8) for n>8. - Colin Barker, Oct 29 2016
a(n) = (11*n+1+(5*n-1)*(-1)^n-(n+3)*(1-(-1)^n)*(-1)^((2*n+3+(-1)^n)/4))/8. - Luce ETIENNE, Oct 20 2016

A116640 a(n) = A116623(A059893(n)).

Original entry on oeis.org

1, 5, 7, 19, 11, 23, 29, 65, 19, 31, 37, 73, 49, 85, 103, 211, 35, 47, 53, 89, 65, 101, 119, 227, 89, 125, 143, 251, 179, 287, 341, 665, 67, 79, 85, 121, 97, 133, 151, 259, 121, 157, 175, 283, 211, 319, 373, 697, 169, 205, 223, 331, 259, 367, 421, 745, 331

Offset: 0

Antti Karttunen, Feb 20 2006. Proposed by Pierre Lamothe (plamothe(AT)aei.ca), May 21 2004

Viewed as a binary tree, this is (1); 5; 7,19; 11,23,29,65; ... Cf. A116623.

If we treat (2n+1) as a binary number with the nonzero bits numbered (highest bit first) from 0..k and the regular binary place value of each nonzero bit numbered from b(0) to b(k) then a(n) = 3^0 * b(0) + 3^1 * b(1) + .. + 3^k. For instance, if n=6 then 2n+1 = 13, which is equal to 8+4+1 or 1101 base(2); and a(n)=29 which is 8*1 + 4*3 + 1*9. - Joe Slater, Jan 23 2016

Cf. A000079, A000225, A001047, A062709.

a:= proc(n) option remember; piecewise(
    n mod 4 = 0, 3*procname(n/2) - 2*procname(n/4),
  n mod 4 = 1, 6*procname((n-1)/4) - procname((n-1)/2),
  n mod 4 = 2, procname(n/2) + 2*procname((n-2)/4),
  5*procname((n-1)/2) - 6*procname((n-3)/4))
end proc:
a(0):= 1:
map(a, [$0..100]); # Robert Israel, Jan 19 2016

a[n_] := a[n] = Switch[Mod[n, 4], 0, 3a[Floor[n/2]] - 2a[Floor[n/4]], 1, 6a[Floor[n/4]] - a[Floor[n/2]], 2, a[Floor[n/2]] + 2a[Floor[n/4]], 3, 5a[Floor[n/2]] - 6a[Floor[n/4]]]; a[0]=1; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 28 2016 *)

a(n) = if(n==0, return(1)); 2*a(n\2) - (-1)^n * 3^hammingweight(n) \\ Charles R Greathouse IV, Jan 21 2016

a(n) = my(p=2*n+1,v=vecextract(vector(#binary(p),j,2^(j-1)),p));sum(i=0,#v-1,3^i*v[#v-i]) \\ Joe Slater, May 09 2017

a(A000225(n)) = A001047(n+1).
For n>= 1 a(A000079(n)) = A062709(n+1).
From Joe Slater, Jan 19 2016: (Start)
a(0) = 1,
a(n) = 3*a(floor(n/2)) - 2*a(floor(n/4)) for n=0 (mod 4) and n>0,
a(n) = 6*a(floor(n/4)) - a(floor(n/2)) for n=1 (mod 4),
a(n) = a(floor(n/2)) + 2*a(floor(n/4)) for n=2 (mod 4),
a(n) = 5*a(floor(n/2)) - 6*a(floor(n/4)) for n=3 (mod 4)
(End)
a(0) = 1, a(n) = 2*a(floor(n/2)) - A033999(n) * A048883(n) for n>0. -
Joe Slater, Jan 22 2016

A234024 Self-inverse permutation of nonnegative integers, A059893-conjugate of blue code: a(n) = A059893(A193231(A059893(n))).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 28 2013

nonn

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences that are permutations of the natural numbers

Cf. A059893, A059894, A193231, A234025-A234027.

(define (A234024 n) (A059893 (A193231 (A059893 n))))

a(n) = A059893(A193231(A059893(n))).

a(n) = A059894(A234027(A059894(n))).

A344682 a(0) = 0, and for any n > 0, a(n) = A022290(A059893(A003754(n+1))).

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 6, 7, 10, 9, 8, 11, 15, 13, 18, 12, 17, 16, 14, 19, 20, 28, 26, 23, 31, 25, 22, 30, 21, 29, 27, 24, 32, 41, 36, 49, 34, 47, 44, 39, 52, 33, 46, 43, 38, 51, 42, 37, 50, 35, 48, 45, 40, 53, 54, 75, 70, 62, 83, 68, 60, 81, 57, 78, 73, 65, 86, 67

Offset: 0

Rémy Sigrist, Jun 08 2021

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

The construction of this sequence is similar to that of A343150; we start with a representation of a number n as a sum of distinct positive Fibonacci numbers, through some binary encoding, and we reverse some of the bits in a bijective way to obtain a(n).

Rémy Sigrist, Table of n, a(n) for n = 0..10944
Rémy Sigrist, PARI program for A344682
Index entries for sequences that are permutations of the natural numbers

Cf. A003754, A059893, A022290, A343150.

# after renaming a(n) to A059893(n) in A059893...
A344682 := proc(n)
    if n = 0 then
        0;
    else
        A022290(A059893(A003754(n+1))) ;
    end if;
end proc:
seq(A344682(n),n=0..70) ; # R. J. Mathar, Jul 29 2021

PARI
```
See Links section.
```

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)

A154437 Permutation of nonnegative integers: A059893-conjugate of A154435.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 17 2009

This permutation is induced by the same Lamplighter group generating wreath recursion (binary transducer) as A154435, 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: A154438. a(n) = A059893(A154435(A059893(n))) = A054429(A153154(A054429(n))).

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

From Yosu Yurramendi, Feb 23 2020: (Start)
a(n) = A054429(A284459(n)) = A258996(A153154(n)) = A284459(A065190(n)).
a(1) = 1; for n > 0, a(2*n) = 2*a(A065190(n)) + 1, a(2*n+1) = 2*a(n). (End)

A065266 A065264 conjugated with A059893, inverse of A065265.

Original entry on oeis.org

2, 4, 1, 8, 6, 10, 3, 16, 14, 18, 12, 20, 5, 22, 7, 32, 30, 34, 28, 36, 26, 38, 24, 40, 9, 42, 11, 44, 13, 46, 15, 64, 62, 66, 60, 68, 58, 70, 56, 72, 54, 74, 52, 76, 50, 78, 48, 80, 17, 82, 19, 84, 21, 86, 23, 88, 25, 90, 27, 92, 29, 94, 31, 128, 126, 130, 124, 132, 122, 134

Offset: 1

Antti Karttunen, Oct 28 2001

nonn

This permutation of N induces also such permutation of Z, that p(i)-i >= 0 for all i.

Index entries for sequences that are permutations of the natural numbers
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.

The associated siteswap sequence is A065267.

a(n) = A059893(A065264(A059893(n)))

A065272 A065270 conjugated with A059893, inverse of A065271.

Original entry on oeis.org

1, 6, 2, 12, 3, 14, 4, 24, 5, 26, 7, 28, 10, 30, 8, 48, 9, 50, 11, 52, 13, 54, 15, 56, 22, 58, 20, 60, 18, 62, 16, 96, 17, 98, 19, 100, 21, 102, 23, 104, 25, 106, 27, 108, 29, 110, 31, 112, 46, 114, 44, 116, 42, 118, 40, 120, 38, 122, 36, 124, 34, 126, 32, 192, 33, 194, 35

Offset: 1

Antti Karttunen, Oct 28 2001

nonn

This permutation of N induces also such permutation of Z, that p(i)-i >= 0 for all i.

Index entries for sequences that are permutations of the natural numbers
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.

The associated siteswap sequence is A065273.

a(n) = A059893(A065270(A059893(n)))

cp's OEIS Frontend

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

A065260 A057115 conjugated with A059893, inverse of A065259.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A116640 a(n) = A116623(A059893(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A234024 Self-inverse permutation of nonnegative integers, A059893-conjugate of blue code: a(n) = A059893(A193231(A059893(n))).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A344682 a(0) = 0, and for any n > 0, a(n) = A022290(A059893(A003754(n+1))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

R

R

Formula

A154437 Permutation of nonnegative integers: A059893-conjugate of A154435.