Ross Drewe - cp's OEIS frontend

A385185 Number of permutations of 0..n-1 which are binary Gray codes.

1, 2, 2, 8, 4, 16, 24, 144, 36, 164, 192, 1168, 976, 5688, 10656, 91392, 11424, 67032, 61840, 403568, 258956, 1589080, 2520324, 22646880, 10898976, 67039504, 93326800, 819193248, 924489888, 7399407552, 16309883520, 187499658240, 11718728640

Offset: 1

Ross Drewe, Aug 03 2025

In a binary Gray code, the binary expansions of any two consecutive terms differ at a single bit position.

When n is odd, the binary weights of n and the first term in the permutation must have opposite parity, since otherwise it's not possible to step through all of 0,...,n-1.

			For n=5, the a(5) = 4 possible permutations which are Gray codes are
  1 3 2 0 4
  2 3 1 0 4
  4 0 1 3 2
  4 0 2 3 1
For n=8, a(8) = 144 includes 0 1 3 2 6 4 5 7 which is lexicographically smallest, and also includes the binary reflected Graycode 0 1 3 2 6 7 5 4.

Cf. A091299, A350784 (when beginning with 0).

function N = Gcode(L); H = hmap; N = 0; unused = uint8([0: L-1]); for i = 1:length(unused); g = unused(i); u = unused; u(i) = []; gray(g, u); end
function gray(g, u); curidx = g(end) + 1; d = H(curidx,:); if isscalar(u); if d(u+1); N = N + 1; end; else for j = 1: length(u); r = u(j); if d(r+1); nextg = [g r]; nextu = u; nextu(j) = []; gray(nextg, nextu); end; end; end; end
function map = hmap; map = false(L, L); S = uint8([0:L-1]); [X,Y] = meshgrid(S); X = X(:); Y = Y(:);
xb = de2bi(X); yb = de2bi(Y); for k = 1:L^2; v = sum(bitxor(xb(k,:), yb(k,:))); if v == 1; map(k) = true; end; end; end; end

a(2^n) = A091299(n).

a(2^n+1) = a(2^n)/2^(n-1) for n > 0. - Andrew Howroyd, Aug 04 2025

a(27)-a(33) from Andrew Howroyd, Aug 04 2025

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

A240910 The sequency numbers of the 32 rows of a Hadamard-Walsh matrix, order 32.

Original entry on oeis.org

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

Offset: 1

Ross Drewe, Apr 14 2014

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

			This is a fixed length sequence of only 32 values, as given in full above.

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. A240909 "natural order" sequencies for Hadamard-Walsh matrix, order 16.
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 the 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

A144428 Square array read by ascending antidiagonals. A(L, n) is a table of sequences representing the number of valid nodes in level n of a labeled binary tree when the labeling rule forbids 1 of the 2^L states given by the last L digits of the parent label.

Original entry on oeis.org

2, 2, 3, 2, 4, 5, 2, 4, 7, 8, 2, 4, 8, 13, 13, 2, 4, 8, 15, 24, 21, 2, 4, 8, 16, 29, 44, 34, 2, 4, 8, 16, 31, 56, 81, 55, 2, 4, 8, 16, 32, 61, 108, 149, 89, 2, 4, 8, 16, 32, 63, 120, 208, 274, 144, 2, 4, 8, 16, 32, 64, 125, 236, 401, 504, 233, 2, 4, 8, 16, 32, 64, 127, 248, 464, 773, 927, 377, 2, 4, 8, 16, 32, 64, 128, 253

Offset: 1

Ross Drewe, Oct 06 2008

A complete labeled binary tree has the root as level 0, 2 nodes at level 1 (each labeled with one of the available symbols 1,2) and 2^n nodes at level n (each labeled with a unique n-digit sequence). The tree can be constructed by adopting a rule that at each successive level, each child node forms its label by adding one symbol to the parent's label.
An incomplete tree can be created by forbidding certain child nodes, using on a state-driven rule. If the state of a node is the last L digits of its label, there are 2^L possible states. Let a(L,n) be the single value denoting the number of valid nodes in level n after applying any given rule and A(L,n) is the sequence of values a(L,2), a(L,3), ..., a(L,n).
Assume this rule: for a given L, all of the 2^L states permit the usual dichotomous branching, except for one state which restricts the output to a single child node. The forbidden child of the pair has a label with the same last digit as the parent state.
This rule creates a set of sequences { A(L,n) } which are essentially the same as the standard "n-step Fibonacci" or "n-anacci" sequences. These can be displayed as the rows of a rectangular array in order of increasing L:
2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, ...
2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, ...
2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, ...
2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, ...
2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, ...
2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, ...
Taking the antidiagonals of this table gives the present entry F(n).
Comparison with the standard n-anacci sequences:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, ...
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, ...
0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, ...
0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, ...
0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, ...
0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
shows that the A(L,n) sequences differ only in the absence of the L+2 start-up values. This is an artifact of the construction method, since a(L,n) is undefined when labels are too short to contain a state sequence - i.e., for all nodes in levels < L.
This method of construction can be generalized (see link) which shows that the output from simple rule definitions is rich in well-known sequences.
From Petros Hadjicostas, Jul 26 2019: (Start)
The author of this array uses F(n) to denote the n-th term of the flattened table (for n >= 1). In addition, it seems that the author uses A(L,n) to denote the term in the L-th row and n-th column of the table. Clearly, L >= 2, but it is not clear whether n starts at 1 or at 2. Thus, in my comments and formulas below I use m to index the columns and start m at 1.
Let A(L, m) be the term in level (row) L and column m, where L >= 2 and m >= 1. Here L is the order of generalized Fibonacci sequence.
We have A(L, m) = 2^m for m = 1,...,L-1, and A(L, L) = 2^L - 1. Also,
A(L, m) = A(L, m-1) + A(L, m-2) + ... + A(L, m-L) for m >= L + 1.
Letting F(n) be the n-th term in the author's sequence (flattened table), we get F((k-1)*(k-2)/2 + i) = A(k-i+1, i) for k >= 2 and i = 1..k-1.
(End)

S. Christensen, Generalized Fibonacci numbers and Blackwell's renewal theorem, arXiv:1012.5006 [math.PR], 2010.
S. Christensen, Generalized Fibonacci numbers and Blackwell's renewal theorem, Statist. Probab. Lett. 82 (2012), 1665-1668.
Ross Drewe, On a generalization of F(n).
O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Wikipedia, Fibonacci number.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Cf. A172119.

From Petros Hadjicostas, Jul 26 2019: (Start)
Let A(L, m) be the term in level (row) L and column m, where L >= 2 and m >= 1. Then A(L, m) = 2^m for m = 1,...,L-1; A(L, L) = 2^L - 1; and A(L, m) = S(L, m) - S(L, m-L) for m >= L + 1, where
S(L, m) = Sum_{j = 0..floor(m/(L+1))} (-1)^j * binomial(m-L*j, m - (L+1)*j) * 2^(m - (L+1)*j). (See the formula by Richard Choulet for array A172119. It can also be found in Dunkel (1925).)
G.f. for row L >= 2: -1 + (1 - z^L)/(1 - 2*z + z^(L+1)).
(End)

Name clarified by Petros Hadjicostas, Jul 26 2019

More terms from Petros Hadjicostas, Jul 26 2019

A137841 Number of distinct n-ary operators in a quinternary logic.

Original entry on oeis.org

5, 3125, 298023223876953125, 2350988701644575015937473074444491355637331113544175043017503412556834518909454345703125

Offset: 0

Ross Drewe, Feb 13 2008

The total number of n-ary operators in a k-valued logic is T = k^(k^n), i.e. if S is a set of k elements, there are T ways of mapping an ordered subset of n elements taken from S to an element of S. Some operators are "degenerate": the operator has arity p, if only p of the n input values influence the output. = therefore the set of operators can be partitioned into n+1 disjoint subsets representing arities from 0 to n.

Cf. A001146 (in binary logic), A055777 (in ternary logic), A137840 (in quaternary logic).

Subsequence of A000351.

a(n) = 5^(5^n).

A137840 Number of distinct n-ary operators in a quaternary logic.

Original entry on oeis.org

4, 256, 4294967296, 340282366920938463463374607431768211456, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

Offset: 0

Ross Drewe, Feb 13 2008

The total number of n-ary operators in a k-valued logic is T = k^(k^n), i.e. if S is a set of k elements, there are T ways of mapping an ordered subset of n elements taken from S to an element of S. Some operators are "degenerate": the operator has arity p, if only p of the n input values influence the output. Therefore the set of operators can be partitioned into n+1 disjoint subsets representing arities from 0 to n.

Cf. A001146 (in binary logic), A055777 (in a ternary logic), A137841 (in a quinternary logic).

Subsequence of A000302.

a(n) = 4^(4^n).

A129956 L1 ('city-block') distances from the origin to a 2D pseudo-random walk based on the digits of Pi.

Original entry on oeis.org

5, 9, 4, 5, 6, 4, 5, 8, 4, 7, 11, 13, 13, 18, 13, 17, 15, 15, 18, 20, 15, 21, 24, 25, 22, 18, 22, 19, 21, 25, 25, 27, 30, 29, 25, 28, 32, 34, 36, 35, 36, 40, 48, 47, 53, 55, 57, 57, 64, 63, 64, 65, 61, 53, 54, 52, 46, 45, 39, 41, 48, 54, 58, 56, 47, 47, 42, 48, 47, 41, 38, 36, 41

Offset: 1

Ross Drewe, Jun 10 2007, Jun 11 2007

The distance from the starting point has physical applications, e.g., in aggregation models.
All distance metrics generate sequences which coincide at the zero points. The L1 (city-block) metric is the simplest and is intrinsically integer valued on integer-spaced lattices (as used here).
The r sequence is not affected by the dimension ordering (i.e., whether each pair of values taken from the digits of Pi represents [x,y] or [y,x]).

			The first 10 digits of Pi are 3 1 4 1 5 9 2 6 5 3
This gives five 2-tuples (x,y pairs): [3 1], [4 1], [5 9], [2 6], [5 3]
The x & y vectors are x = [3 4 5 2 5], y = [1 1 9 6 3]
Adjusting to zero mean gives x = [ -1.5 -0.5 0.5 -2.5 0.5], y = [ -3.5 -3.5 4.5 1.5 -1.5]
The cumulative x,y position vectors are cx = [ -1.5 -2 -1.5 -4 -3.5], cy = [ -3.5 -7 -2.5 -1 -3.5]
The L1 radii from the origin are r = abs(cx) + abs(cy), r = [5 9 4 5 6]

Hemphill, Scott, Pi (gives 1.25 million digits of Pi)
Eric Weisstein's World of Mathematics, Pi Digits.

function r = find_L1_radius(pidigits, k); d = pidigits(1:2*k); t = reshape(d, 2, length(d)/2); x = t(1, :); y = t(2, :); cx = cumsum(x - 4.5); cy = cumsum(y - 4.5); r = abs(cx) + abs(cy); return; % pidigits is a MATLAB row vector of at least 2*k digits of Pi (including the initial '3'); % k is the number of 2D radii to calculate.

r(n) = abs(cx(n)) + abs(cy(n)), where cx = cum_sum([odd digits of Pi] - 4.5) and cy = cum_sum([even digits of Pi] - 4.5).

A128250 LCG periods: periods of the output sequences produced by multiplicative linear congruential generators (LCGs) with prime moduli, for all valid combinations of multiplier and modulus.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 2, 1, 3, 6, 3, 6, 2, 1, 10, 5, 5, 5, 10, 10, 10, 5, 2, 1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2, 1, 8, 16, 4, 16, 16, 16, 8, 8, 16, 16, 16, 4, 16, 8, 2, 1, 18, 18, 9, 9, 9, 3, 6, 9, 18, 3, 6, 18, 18, 18, 9, 9, 2

Offset: 2

Ross Drewe, May 09 2007, May 11 2007, May 25 2007

The periods of these output sequences need to be known when designing LCG-based pseudorandom number generators. The period of an LCG output is always 1 when a = 1, always 2 when a = m-1 and maximal (i.e. m-1) only if a is a totative of m. There is no fast method for finding totative values when m is large. The sample shows the terms generated by the first 8 moduli (i.e. primes from 2 to 19), as generated by: A = LCG_periods(19) (see program).

Apparently this is A086145 with a top row added. - R. J. Mathar, Jun 14 2008

			Q =
p(2,1) ..................................... [1]
p(3,1) p(3,2) .............................. [1 2]
p(5,1) p(5,2) p(5,3) p(5,4) ................ [1 4 4 2]
p(7,1) p(7,2) p(7,3) p(7,4) p(7,5) p(7,6) .. [1 3 6 3 6 2]
Therefore A = [1] [1 2] [1 4 4 2] [1 3 6 3 6 2] .....

Cf. A086145.

function A = LCG_periods(N); mlist = primes(N); nprimes = length(mlist); A = []; for i = 1:nprimes; m = mlist(i); for a = 1:m-1; x = 1; count = 0; while 1; count = count + 1; x = mod(a*x, m); if x == 1; break; end; end; A = [A count]; end; end

Multiplicative LCG for modulus m, multiplier a: x(n+1) == a*x(n) mod m. Additional restriction: a < m (as assumed in many applications). The output sequence for any explicit combination of m,a,x0 is always periodic and the period is independent of x0. Therefore denote the period by p(m,a). Let Q be the lower triangular matrix that is produced by tabulating all p(m,a) values, such that the rows represent m values (successive primes) and the columns represent a values (from 1 to m-1). Then A is the sequence obtained by concatenating the rows of this matrix.

cp's OEIS Frontend

User: Ross Drewe

A385185 Number of permutations of 0..n-1 which are binary Gray codes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

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

A240910 The sequency numbers of the 32 rows of a Hadamard-Walsh matrix, order 32.

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

A144428 Square array read by ascending antidiagonals. A(L, n) is a table of sequences representing the number of valid nodes in level n of a labeled binary tree when the labeling rule forbids 1 of the 2^L states given by the last L digits of the parent label.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A137841 Number of distinct n-ary operators in a quinternary logic.

Views

Author

Keywords

Comments

Crossrefs

Formula

A137840 Number of distinct n-ary operators in a quaternary logic.

Views

Author

Keywords

Comments

Crossrefs

Formula

A129956 L1 ('city-block') distances from the origin to a 2D pseudo-random walk based on the digits of Pi.

Views

Author

Keywords

Comments

Examples

Links

Programs

MATLAB

Formula

A128250 LCG periods: periods of the output sequences produced by multiplicative linear congruential generators (LCGs) with prime moduli, for all valid combinations of multiplier and modulus.

Views

Author

Keywords