A054429 -id:A054429 - cp's OEIS frontend

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

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

A233280 Permutation of nonnegative integers: a(n) = A003188(A054429(n)).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 18 2013

nonn

This permutation transforms the enumeration system of positive irreducible fractions A071766/A229742 (HCS) into the enumeration system A007305/A047679 (Stern-Brocot), and the enumeration system A245325/A245326 into A162909/A162910 (Bird). - 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: A233279.
Cf. A000069, A001969, A003188, A054429, A063946, A154436.
Similarly constructed permutation pairs: A003188/A006068, A135141/A227413, A232751/A232752, A233275/A233276, A233277/A233278, A193231 (self-inverse).

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

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

(define (A233280 n) (A003188 (A054429 n)))
;; Alternative version, based on entangling even & odd numbers with odious and evil numbers:
(definec (A233280 n) (cond ((< n 2) n) ((even? n) (A000069 (+ 1 (A233280 (/ n 2))))) (else (A001969 (+ 1 (A233280 (/ (- n 1) 2)))))))

a(n) = A003188(A054429(n)).
a(n) = A063946(A003188(n)).
a(n) = A054429(A154436(n)).
a(0)=0, a(1)=1, and otherwise, a(2n) = A000069(1+a(n)), a(2n+1) = A001969(1+a(n)). [A recurrence based on entangling even & odd numbers with odious and evil numbers]
a(n) = A258746(A180201(n)) = A180201(A117120(n)), n > 0. - Yosu Yurramendi, Apr 10 2017

A304083 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of A054429.

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 8, 13, 9, 11, 10, 31, 30, 28, 24, 16, 29, 25, 17, 27, 26, 18, 23, 22, 20, 21, 63, 19, 59, 58, 56, 48, 32, 62, 60, 52, 36, 61, 57, 49, 33, 55, 54, 50, 34, 51, 35, 47, 46, 44, 40, 45, 41, 43, 42, 127, 53, 37, 39, 38, 126, 124, 120, 112, 96, 64, 125, 121, 113, 97, 65, 123, 122, 114, 98, 66, 119, 118, 116, 100, 68, 117, 101

Offset: 0

Antti Karttunen, May 06 2018

In "minimal subset/superset bitmask transform", applicable to any N -> N injection f, we start from a(0) = 0, after which for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i for which f(k_i) is minimized; otherwise, a(n) = that h_i for which f(h_i) is minimized among the infinite set of numbers h_i for which bitand(h_i,a(n-1)) = a(n-1) and that are not yet present in the sequence. In this case f(n) = A054429(n).

Shares with permutations like A003188, A006068, A163252, A300838, A302846, A303763, A303765, A303767, A303773 and A303775 the property that when moving from any a(n) to a(n+1) either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes may occur at the same step. Note that A303767 is obtained when the same transform is applied to A001477, and A303775 when it is applied to A193231.

			After a(3) = 2, "10" in binary, there are no submasks that wouldn't have been used, so one selects from supermasks h_i = "110" (6), "111" (7), "1010" (10), "1011" (11), "1110" (14), "1111" (15), "10010" (18), "10011" (19), etc. that one for which A054429(h_i) is minimized, which happens to be at 6 (as A054429(6) = 5, but A054429(7) = 4, and for n >= 8, A054429(n) >= 8), thus a(4) = 7.
After a(4) = 7, "111" in binary, the submasks "1", "10", and "11" (1-3) are already present in sequence, while submasks "100", "101", "110" (4-6) are not present, and because A054429 is minimized on these three at 6, a(5) = 6.

Cf. A304084 (inverse).
Cf. A054429.
Cf. also A303767, A303775, A304085, A304087, A304088, A304089.

allocatemem(2^30);
default(parisizemax,2^31);
up_to = (2^17)+2;
A054429(n) = ((3<<#binary(n\2))-n-1);
find_minimal_submask_for_A054429(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,n,if((bitor(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A054429(m) < minval)), minval = A054429(m); minmask = m)); (minmask); };
find_minimal_supermask_for_A054429(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,(1<<(1+#binary(n)))-1,if((bitand(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A054429(m) < minval)), minval = A054429(m); minmask = m)); (minmask); };
v304083 = vector(up_to);
m304084 = Map();
w=1; for(n=1,up_to,s = Set([]); if((submask = find_minimal_submask_for_A054429(w,m304084)), w = submask, w = find_minimal_supermask_for_A054429(w,m304084)); v304083[n] = w; mapput(m304084,w,n));
A304083(n) = if(!n,n,v304083[n]);
A304084(n) = if(!n,n,mapget(m304084,n));

Derived sequences:
A052330(a(n)) = A304085(n).
A019565(a(n)) = A304087(n).
A000120(a(n)) = A304089(n).

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

Original entry on oeis.org

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

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. A054429, A059894, A193231, A234024-A234026.

def a065621(n): return n^(2*(n - (n&-n)))
def a048724(n): return n^(2*n)
def a054429(n): return 1 if n==1 else 2*a054429(int(n/2)) + 1 - n%2
def a193231(n):
    if n<2: return n
    if n%2==0: return a048724(a193231(n/2))
    else: return a065621(1 + a193231((n - 1)/2))
def a(n): return n if n<2 else a054429(a193231(a054429(n))) # Indranil Ghosh, Jun 05 2017

(define (A234027 n) (A054429 (A193231 (A054429 n))))

a(n) = A054429(A193231(A054429(n))).
a(n) = A234025(A054429(n)).
a(n) = A054429(A234026(n)).
a(n) = A059894(A234024(A059894(n))).

A234025 Permutation of nonnegative integers: a(n) = A054429(A193231(n)).

Original entry on oeis.org

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

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

Inverse permutation: A234026.

def a065621(n): return n^(2*(n - (n&-n)))
def a048724(n): return n^(2*n)
def a054429(n): return 1 if n==1 else 2*a054429(int(n/2)) + 1 - n%2
def a193231(n):
    if n<2: return n
    if n%2==0: return a048724(a193231(n/2))
    else: return a065621(1 + a193231((n - 1)/2))
def a(n): return n if n<2 else a054429(a193231(n)) # Indranil Ghosh, Jun 05 2017

(define (A234025 n) (A054429 (A193231 n)))

a(n) = A054429(A193231(n)).

a(n) = A234027(A054429(n)).

A234026 Permutation of nonnegative integers: a(n) = A193231(A054429(n)).

Original entry on oeis.org

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

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

Inverse permutation: A234025. Cf. A234024.

(define (A234026 n) (A193231 (A054429 n)))

a(n) = A193231(A054429(n)).

a(n) = A054429(A234027(n)).

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).

A266640 Reversed reduced frequency counts for A004001: a(n) = A265754(A054429(n)).

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 1, 4, 3, 2, 1, 2, 1, 1, 1, 5, 4, 3, 2, 1, 3, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 3, 2, 1, 2, 1, 1, 3, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 7, 6, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 4, 3, 2, 1, 3, 2, 1, 2, 1, 1, 4, 3, 2, 1, 3, 2, 1, 2, 1, 1, 3, 2, 1, 2, 1, 1, 2, 1, 1, 1

Offset: 1

Antti Karttunen, Jan 22 2016

Deleting all 1's and decrementing the remaining terms by one gives the sequence back.

			Illustration how the sequence can be constructed by concatenating the reversed reduced frequency counts R_n of each successive level n of A004001-tree:
                              1
                             / \
                            2   1
                           /|\   \
              ____________3 2 1   1
             /    /    /  | |\ \   \
    ________4  __3    2   1 2 1 1   1
   / / / / /  / /|   /|   | |\ \ \   \
  5 4 3 2 1  3 2 1  2 1   1 2 1 1 1   1
etc.

Antti Karttunen, Table of n, a(n) for n = 1..8191
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.

Cf. A004001, A054429.
Cf. A000079 (positions of records, where n appears for the first time).
Cf. A265754 (obtained from the mirror image of the same tree).

(define (A266640 n) (A265754 (A054429 n)))

a(n) = A265754(A054429(n)).
Other identities. For all n >= 0:
a(2^n) = n+1.

A369045 LCM-transform of binary invert permutation (A054429).

Original entry on oeis.org

1, 3, 2, 7, 1, 5, 2, 1, 1, 13, 1, 11, 1, 3, 2, 31, 1, 29, 1, 3, 1, 5, 1, 23, 1, 1, 1, 19, 1, 17, 2, 1, 1, 61, 1, 59, 1, 1, 1, 1, 1, 53, 1, 1, 1, 7, 1, 47, 1, 1, 1, 43, 1, 41, 1, 1, 1, 37, 1, 1, 1, 1, 2, 127, 1, 5, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 113, 1, 1, 1, 109, 1, 107, 1, 1, 1, 103, 1, 101, 1, 1, 1, 97, 1, 1, 1

Offset: 1

Antti Karttunen, Jan 12 2024

nonn

Binary invert permutation, A054429, is a self-inverse permutation related to the binary expansion of n that keeps all the numbers of range [2^k, 2^(1+k)[ in the same range, i.e., for all n >= 1, A000523(A054429(n)) = A000523(n), from which it immediately follows that A054429 has the property S mentioned in the comments of A368900, and therefore this sequence is equal to A014963(A054429(n)), for n >= 1.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to binary expansion of n

Cf. A014963, A054429, A368900, A369041, A369042, A369043, A369044.

up_to = 65537;
LCMtransform(v) = { my(len = length(v), b = vector(len), g = vector(len)); b[1] = g[1] = 1; for(n=2,len, g[n] = lcm(g[n-1],v[n]); b[n] = g[n]/g[n-1]); (b); };
A054429(n) = ((3<<#binary(n\2))-n-1);
v369045 = LCMtransform(vector(up_to,i,A054429(i)));
A369045(n) = v369045[n];

A014963(n) = { ispower(n, , &n); if(isprime(n), n, 1); };
A054429(n) = ((3<<#binary(n\2))-n-1);
A369045(n) = A014963(A054429(n));

a(n) = lcm {1..A054429(n)} / lcm {1..A054429(n-1)}.
a(n) = A014963(A054429(n)). [See comments.]
For n >= 1, Product_{d|n} a(A054429(d)) = n. [Implied by above.]

A270198 a(n) = A054429(A055938(A054429(n))).

Original entry on oeis.org

3, 5, 6, 9, 10, 11, 14, 17, 18, 19, 20, 23, 26, 27, 30, 33, 34, 35, 36, 37, 40, 43, 44, 47, 50, 51, 52, 55, 58, 59, 62, 65, 66, 67, 68, 69, 70, 73, 76, 77, 80, 83, 84, 85, 88, 91, 92, 95, 98, 99, 100, 101, 104, 107, 108, 111, 114, 115, 116, 119, 122, 123, 126, 129, 130, 131, 132, 133, 134, 135, 138, 141, 142, 145

Offset: 1

Antti Karttunen, May 31 2016

Positive natural numbers not in the range of A233272.

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

Complement: A270200.

Cf. A054429, A055938, A233272.

s = Range[2^(# + 1) - 1, 2^#, -1] & /@ Range[0, 12] // Flatten; t = Complement[#, 2 # - DigitCount[2 #, 2, 1] & /@ #] &@ Range[20007]; Table[s[[ t[[ s[[n]] ]] ]], {n, 74}] (* Michael De Vlieger, Jun 01 2016, after Harvey P. Dale at A005187 and A054429 *)

(define (A270198 n) (A054429 (A055938 (A054429 n))))

a(n) = A054429(A055938(A054429(n))).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

R

R

Scheme

Formula

A233280 Permutation of nonnegative integers: a(n) = A003188(A054429(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

R

Scheme

Formula

A304083 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of A054429.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Scheme

Formula

A234025 Permutation of nonnegative integers: a(n) = A054429(A193231(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Scheme

Formula

A234026 Permutation of nonnegative integers: a(n) = A193231(A054429(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

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