A240910 -id:A240910 - 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)

A131271 Triangular array T(n,k), n>=0, k=1..2^n, read by rows in bracketed pairs such that highest ranked element is bracketed with lowest ranked.

Original entry on oeis.org

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

Offset: 0

J. Demongeot (Jacques.Demongeot(AT)imag.fr), Jun 24 2007

In a knockout competition with 2^n players, arranging the competition brackets (see Wikipedia) in T(n,k) order, where T(n,k) is the rank of the k-th player, ensures that highest ranked players cannot meet until the later stages of the competition. None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition. At the same time the top ranked players in each match meet the lowest ranked player possible consistent with this rule. The sequence for the top ranked players meeting the highest ranked player possible is A049773. - Colin Hall, Feb 28 2012
Ranks in natural order of 2^n increasing real numbers appearing in limit cycles of interval iterations, or Median Spiral Order. [See the works by Demongeot & Waku]
From Andrey Zabolotskiy, Dec 06 2024 (Start):
For n>0, row n-1 is the permutation relating row n of Kepler's tree of fractions with row n of the left half of Stern-Brocot tree. Specifically, if K_n(k) [resp. SB_n(k)] is the k-th fraction in the n-th row of A294442 [resp. A057432], where 1/2 is in row 1 and k=1..2^(n-1), then K_n(k) = SB_n(T(n-1, k)).
The inverse permutation is row n of A088208.
When 1 is subtracted from each term, rows 3-5 become A240908, A240909, A240910. (End)

			Triangle begins:
1;
1,  2;
1,  4, 2, 3;
1,  8, 4, 5, 2,  7, 3,  6;
1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11;
...

Alois P. Heinz, Table of n, a(n) for n = 0..8190
John M. Campbell, A generalization of Deterministic Finite Automata related to discharging, arXiv:2506.14072 [cs.FL], 2025. See p. 7.
Jacques Demongeot and Jules Waku, Counter-Examples about Lower- and Upper-Bounded Population Growth, Math. Pop. Studies 12 (2005), 199-210.
Jacques Demongeot and Jules Waku, Application of interval iterations to the entrainment problem in respiratory physiology, Phil. Trans. R. Soc. A, 367 (2009), 4717-4739.
Wikipedia, Bracket (tournament)

Cf. A049773, A088208, A294442, A057432.
Cf. A005578 (last elements in rows), A155944 (T(n,2^(n-1)) for n>0).
Cf. A006519, A240908, A240909, A240910.

T:= proc(n,k) option remember;
      `if`({n, k} = {1}, 1,
      `if`(irem(k, 2)=1, T(n-1, (k+1)/2), 2^(n-1)+1 -T(n-1, k/2)))
    end:
seq(seq(T(n, k), k=1..2^(n-1)), n=1..7); # Alois P. Heinz, Feb 28 2012, with offset 1

T[0, 1] = 1;
T[n_, k_] := T[n, k] = If[Mod[k, 2] == 1, T[n, (k + 1)/2], 2^n + 1 - T[n, k/2]];
Table[T[n, k], {n, 0, 6}, {k, 2^n}] // Flatten (* Jean-François Alcover, May 31 2018, after Alois P. Heinz *)

T(0,1) = 1, T(n,2k-1) = T(n-1,k), T(n,2k) = 2^n+1 - T(n-1,k).

T(n,1) = 1; for 1 < k <= 2^n, T(n,k) = 1 + (2^n)/m - T(n,k-m), where m = A006519(k-1). - Mathew Englander, Jun 20 2021

Edited (with new name from Colin Hall) by Andrey Zabolotskiy, Dec 06 2024

A240908 The sequency numbers of the 8 rows of a version of the Hadamard-Walsh matrix of order 8.

Original entry on oeis.org

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

Offset: 1

Ross Drewe, Apr 14 2014

The Hadamard (Hadamard-Walsh) matrix is widely used in telecommunications and signal analysis. It has 3 well-known forms which vary according to the sequency ordering of its rows: "natural" ordering, "dyadic" or Payley ordering, and sequency ordering. In a mathematical context the sequency is the number of zero crossings or transitions in a matrix row (although in a physical signal context, it is half the number of zero crossings per time period). The matrix row sequencies are a permutation of the set [0,1,2,...n-1], where n is the order of the matrix. For spectral analysis of signals the sequency-ordered form is needed. Unlike the dyadic ordering (given by A153141), the natural ordering requires a separate list for each matrix order. This sequence is the natural sequency ordering for an order 8 matrix.

			This is a fixed length sequence of only 8 values, as given.

N. J. A. Sloane, A Library of Hadamard Matrices
Eric Weisstein's World of Mathematics, Hadamard Matrix
Wikipedia, Walsh matrix

Cf. A240909 "natural order" sequencies for Hadamard-Walsh matrix, order 16.
Cf. A240910 "natural order" sequencies for Hadamard-Walsh matrix, order 32.
Cf. A153141 "dyadic order" sequencies for Hadamard-Walsh matrix, all orders.
Cf. A000975(n) is sequency of last row of H(n). - William P. Orrick, Jun 28 2015

Recursion: H(2)=[1 1; 1 -1]; H(n) = H(n-1)*H(2), where * is Kronecker matrix product.

Definition of H(n) corrected by William P. Orrick, Jun 28 2015

A240909 The sequency numbers of the 16 rows of a Hadamard-Walsh matrix of order 16.

Original entry on oeis.org

0, 15, 7, 8, 3, 12, 4, 11, 1, 14, 6, 9, 2, 13, 5, 10

Offset: 1

Ross Drewe, Apr 14 2014

See A240908 for context. This sequence is the natural sequency ordering for an order 16 matrix.

			This is a fixed length sequence of only 16 values, as given.

N. J. A. Sloane, A Library of Hadamard Matrices
Eric Weisstein's World of Mathematics, Hadamard Matrix
Wikipedia, Walsh matrix

Cf. A240908 "natural order" sequencies for Hadamard-Walsh matrix, order 8.
Cf. A240910 "natural order" sequencies for Hadamard-Walsh matrix, order 32.
Cf. A153141 "dyadic order" sequencies for Hadamard-Walsh matrix, all orders.
Cf. A000975(n) is sequency of last row of H(n). - William P. Orrick, Jun 28 2015
Cf. A131271 (row 4, minus 1).

Recursion: H(2)=[1 1; 1 -1]; H(n) = H(n-1)*H(2), where * is Kronecker matrix product.

a(n) = A131271(4,n) - 1. - Mathew Englander, Jun 19 2021

Definition of H(n) corrected by William P. Orrick, Jun 28 2015

A259363 Number of distinct elements in the Gram matrix of the first M rows of the Kronecker product (Sylvester) Hadamard matrix.

Original entry on oeis.org

0, 1, 2, 3, 2, 4, 4, 3, 2, 4, 5, 6, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 5, 8, 9, 10, 9, 12, 11, 10, 7, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 6, 9, 10, 11, 8, 9, 8, 7, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9

Offset: 0

William P. Orrick, Jun 24 2015

Let H(2) = [1, 1; 1, -1]; let H(2^(n+1)) be the Kronecker product of H(2^n) and H(2). For M less than or equal to 2^n, let A(2^n,M) be the submatrix of H(2^n) consisting of its first M rows, and let G(2^n,M)=(A(2^n,M))'A(2^n,M). Then a(M) is the number of distinct elements of G(2^n,M), which depends only on M.

			H(4)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1;1,-1,-1,1], A(4,3)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1], G(4,3)=[3,1,1,-1;1,3,-1,1;1,-1,3,1;-1,1,1,3]. Since G(4,3) has 3 distinct elements, a(3)=3.

Math Stackexchange, Relation between number of unique values in Gramian Matrix (G) and the matrices that created it

Cf. A000975, A240908, A240909, A240910.

mToWord[m_] := Module[{binary, sbin, lst, j},
  binary = IntegerDigits[m, 2];
  sbin = Split[binary];
  lst = {};
  For[j = 1, j <= Length[sbin], j++,
   If[sbin[[j, 1]] == 1 && Length[sbin[[j]]] > 1, AppendTo[lst, 11]];
   If[sbin[[j]] == {1}, AppendTo[lst, 1]];
   If[sbin[[j, 1]] == 0, AppendTo[lst, 0]]
   ];
  lst
  ]
s[{1}]=1
s[{1,0}]=2
s[w_] := Module[{b, newW, a, c},
  If[w[[1]] == 11,
   b = 1,
   b = 0
   ];
  If[w[[-1]] != 0,
   newW = Append[w, 0];
   a = -1,
   newW = w;
   a = 0
   ];
  If[newW[[-2]] == 1,
   c = -3,
   If[newW[[-2]] == 11,
    c = -1
    ]
   ];
  a + b + c + 2 Length[newW]
  ]
numberDistinctGramValues[m_]:=If[m==0,0,s[mToWord[m]]]

Recurrence for M>0: let b be the base-2 representation of M. Map b to a word w on the alphabet {1,I,O} by splitting b into runs of 0's and 1's and letting O represent a string of one or more 0's, I a string of two or more 1's, and 1 an isolated 1. Then a(0)=0, a(n)=s(w), where s(1)=1, s(1O1)=4, s(uO)=s(u)+1, s(vI)=s(v1)+2, s(vIO1)=s(v1)+4, s(v1O1)=s(v1)+4, where u is a nonempty word and v is an arbitrary word.
Closed form: s(1)=1, s(1O)=2, s(w)=4[(|w|+1)/2]+a(w)+b(w)+c(w), where |w| is the length of w, [x] is the greatest integer function, and a, b, c are defined by a(w)=0 if w ends in O, -1 if w ends in 1 or I; b(w)=1 if first letter of w is I, 0 if first letter of w is 1; c(w)=-1 if last non-O letter of w is I, -3 if last non-O letter of w is 1.
Equivalently, for n > 1, a(n) = 4*A069010(n) - A000035(n) + A079944(n-2) + 4 - A099545(n-1) + A036987(n-1).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

R

Formula

A131271 Triangular array T(n,k), n>=0, k=1..2^n, read by rows in bracketed pairs such that highest ranked element is bracketed with lowest ranked.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A240908 The sequency numbers of the 8 rows of a version of the Hadamard-Walsh matrix of order 8.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A240909 The sequency numbers of the 16 rows of a Hadamard-Walsh matrix of order 16.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A259363 Number of distinct elements in the Gram matrix of the first M rows of the Kronecker product (Sylvester) Hadamard matrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula