A154435 -id:A154435 - cp's OEIS frontend

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

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)

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)

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

A233279 Permutation of nonnegative integers: a(n) = A054429(A006068(n)).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 18 2013

nonn

This permutation transforms the enumeration system of positive irreducible fractions A007305/A047679 (Stern-Brocot) into the enumeration system A071766/A229742 (HCS), and the enumeration system A162909/A162910 (Bird) into A245325/A245326. - Yosu Yurramendi, Jun 09 2015

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

Inverse permutation: A233280.

Cf. A006068, A054429, A063946, A154435.

Module[{nn = 6, s}, s = Flatten[Table[Range[2^(n + 1) - 1, 2^n, -1], {n, 0, nn}]]; Map[If[# == 0, 0, s[[#]]] &, Table[Fold[BitXor, n, Quotient[n, 2^Range[BitLength[n] - 1]]], {n, 0, 2^nn}]]] (* Michael De Vlieger, Apr 06 2017, after Harvey P. Dale at A054429 and Jan Mangaldan at A006068 *)

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(n)) # Indranil Ghosh, Jun 11 2017

maxrow <- 8 # by choice
a <- 1:3
for(m in 0:maxrow) for(k in 0:(2^m-1)){
a[2^(m+2)+            k] <- a[2^(m+1)+    k] + 2^(m+1)
a[2^(m+2)+        2^m+k] <- a[2^(m+1)+2^m+k] + 2^(m+1)
a[2^(m+2)+2^(m+1)+    k] <- a[2^(m+1)+2^m+k] + 2^(m+2)
a[2^(m+2)+2^(m+1)+2^m+k] <- a[2^(m+1)+   +k] + 2^(m+2)
}
(a <- c(0,a))
# Yosu Yurramendi, Apr 05 2017

# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # by choice
a <- 1
for(n in 2:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  anbit <- nbit
  for(k in 2^(0:floor(log2(length(nbit))))  )
    anbit <- bitwXor(anbit, c(anbit[-(1:k)], rep(0,k))) # ?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, May 29 2021

(define (A233279 n) (A054429 (A006068 n)))

a(n) = A054429(A006068(n)).
a(n) = A006068(A063946(n)).
a(n) = A154435(A054429(n)).
a(n) = A180200(A258746(n)) = A117120(A180200(n)), n > 0. - Yosu Yurramendi, Apr 10 2017

A245326 Denominators of an enumeration system of the reduced nonnegative rational numbers.

Original entry on oeis.org

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

Offset: 1

Yosu Yurramendi, Jul 18 2014

A245325(n)/a(n) enumerates all the reduced nonnegative rational numbers exactly once.
If the terms (n>0) are written as an array (in a left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
1,
2, 1,
3, 3, 2,1,
5, 4, 5,4, 3, 3,2,1,
8, 7, 7,5, 8, 7,7,5, 5, 4, 5,4, 3, 3,2,1,
13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,
then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence. These Fibonacci sequences are equal to Fibonacci sequences from A...... except for the first terms of those sequences.
If the rows are written in a right-aligned fashion:
                                                                        1,
                                                                      2,1,
                                                                  3,3,2,1,
                                                          5,4,5,4,3,3,2,1,
                                          8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,
13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,
then each column is constant and the terms are from A071585 (a(2^m-1-k) = A071585(k), k = 0,1,2,...).
If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are permutations of terms of blocks from A002487 (Stern's diatomic series or the Stern-Brocot sequence), and, more precisely, the reverses of blocks of A071766 (a(2^m+k) = A071766(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). Moreover, each block is the bit-reversed permutation of the corresponding block of A245328.

Index entries for fraction trees

Cf. A245325, A002487, A071585, A071766, A273494.

Cf. A002487, A059893, A154435.

a(n) = my(A=1); for(i=0, logint(n, 2), if(bittest(2*n, i), A++, A=(A+1)/A)); denominator(A) \\ Mikhail Kurkov, Feb 20 2023

blocklevel <- 6 # arbitrary
a <- 1
for(m in 0:blocklevel) for(k in 0:(2^(m-1)-1)){
  a[2^(m+1)+k]             <- a[2^m+k] + a[2^m+2^(m-1)+k]
  a[2^(m+1)+2^(m-1)+k]     <- a[2^(m+1)+k]
  a[2^(m+1)+2^m+k]         <- a[2^m+k]
  a[2^(m+1)+2^m+2^(m-1)+k] <- a[2^m+2^(m-1)+k]
}
a

a(n) = A002487(1+A059893(A180200(n))) = A002487(A059893(A154435(n))). - Yosu Yurramendi, Sep 20 2021

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

A180200 a(0)=0, a(1)=1; for n > 1, a(n) = 2*m + 1 - (n mod 2 + m mod 2) mod 2, where m = a(floor(n/2)).

Original entry on oeis.org

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

Offset: 0

Reinhard Zumkeller, Aug 15 2010

Permutation of the natural numbers with inverse A180201;
A180198(n) = a(a(n));
a(A180199(n)) = A180199(a(n)) = A180201(n);
a(A075427(n)) = A075427(n).
This permutation transforms the enumeration system of positive irreducible fractions A007305/A047679 (Stern-Brocot) into the enumeration system A245325/A245326, and enumeration system A162909/A162910 (Bird) into A071766/A229742 (HCS). - Yosu Yurramendi, Jun 09 2015

Reinhard Zumkeller, Table of n, a(n) for n = 0..1023
Index entries for sequences that are permutations of the natural numbers

Cf. A006068, A054429, A154435.

#include 
int a(int n){
    int m;
    if (n<2){return n;}
    else{
        m=a(n/2);
        return 2*m  + 1 - (n%2 + m%2)%2;
    }
}
int main()
{
    int n=0;
    for(; n<=100; n++)
    printf("%d, ", a(n));
    return 0;
} /* Indranil Ghosh, Apr 05 2017 */

a:= proc(n) option remember; `if`(n<2, n, (m->
      2*m+1-irem(m+n, 2))(a(iquo(n, 2))))
    end:
seq(a(n), n=0..72);  # Alois P. Heinz, May 29 2021

a[0] = 0; a[1] = 1; a[n_] := a[n] = 2 # + 1 - Mod[Mod[n, 2] + Mod[#, 2], 2] &@ a[Floor[n/2]]; Table[a@ n, {n, 0, 72}] (* Michael De Vlieger, Apr 02 2017 *)

a(n) = if(n<2, n, my(m=a(n\2)); 2*m + 1 - (n%2 + m%2)%2); \\ Indranil Ghosh, Apr 05 2017

def a(n):
    if n<2:return n
    else:
        m=a(n//2)
        return 2*m + 1 - (n%2 + m%2)%2 # Indranil Ghosh, Apr 05 2017

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

a(n) = A258746(A233279(n)) = A233279(A117120(n)), n > 0. - Yosu Yurramendi, Apr 10 2017 [Corrected by Yosu Yurramendi, Mar 14 2025]
a(0) = 0, a(1) = 1, for n > 0 a(2*n) = 2*a(n) + [a(n) even], a(2*n + 1) = 2*a(n) + [a(n) odd]. - Yosu Yurramendi, May 23 2020
a(n) = A054429(A154435(n)) = A006068(A054429(n)), n > 0. - Yosu Yurramendi, Jun 05 2021

Name edited by Jon E. Schoenfield, Apr 05 2017

A245325 Numerators of an enumeration system of the reduced nonnegative rational numbers.

Original entry on oeis.org

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

Offset: 1

Yosu Yurramendi, Jul 18 2014

a(n)/A245326(n) enumerates all the reduced nonnegative rational numbers exactly once.
If the terms (n>0) are written as an array (in a left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
  1,
  1,2,
  2,1,3,3,
  3,3,2,1,5,4,5,4,
  5,4,5,4,3,3,2,1,8,7,7,5,8,7,7,5,
  8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,
then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence.
If the rows are written in a right-aligned fashion:
                                                                        1,
                                                                      1,2,
                                                                 2, 1,3,3,
                                                      3, 3, 2,1, 5, 4,5,4,
                                 5, 4, 5,4, 3, 3,2,1, 8, 7, 7,5, 8, 7,7,5,
8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,
then each column is an arithmetic sequence. The differences of the arithmetic sequences give the sequence A071585 (a(2^(m+1)-1-k) - a(2^m-1-k) = A071585(k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).
If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are permutations of terms of blocks from A002487 (Stern's diatomic series or the Stern-Brocot sequence), and, more precisely, the reverses of blocks of A229742 (a(2^m+k) = A229742(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). Moreover, each block is the bit-reversed permutation of the corresponding block of A245327.

Index entries for fraction trees

Cf. A245326, A002487, A071585, A229742, A273494.

blocklevel <- 6 # arbitrary
a <- 1
for(m in 0:blocklevel) for(k in 0:(2^(m-1)-1)){
  a[2^(m+1)+k]             <- a[2^m+2^(m-1)+k]
  a[2^(m+1)+2^(m-1)+k]     <- a[2^m+k]
  a[2^(m+1)+2^m+k]         <- a[2^(m+1)+k] +  a[2^m+k]
  a[2^(m+1)+2^m+2^(m-1)+k] <- a[2^(m+1)+2^m+k]
}
a

a(n) = A002487(A059893(A180200(n))) = A002487(1+A059893(A154435(n))). - Yosu Yurramendi, Sep 20 2021

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

R

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

Formula

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

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

R

Formula

Extensions

A233279 Permutation of nonnegative integers: a(n) = A054429(A006068(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

R

R

Scheme

Formula

A245326 Denominators of an enumeration system of the reduced nonnegative rational numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

R

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links