Philippe Beaudoin - cp's OEIS frontend

A261195 Encoded symmetrical square binary matrices.

0, 1, 6, 7, 16, 17, 22, 23, 40, 41, 46, 47, 56, 57, 62, 63, 384, 385, 390, 391, 400, 401, 406, 407, 424, 425, 430, 431, 440, 441, 446, 447, 576, 577, 582, 583, 592, 593, 598, 599, 616, 617, 622, 623, 632, 633, 638, 639, 960, 961, 966, 967, 976, 977, 982, 983

Offset: 0

Philippe Beaudoin, Aug 11 2015

nonn

We encode an n X n binary matrix reading it antidiagonal by antidiagonal, starting from the least significant bit. A given entry in the sequence therefore represents the infinite family of n X n matrices that can be obtained by adding zero antidiagonals. All of these matrices are symmetrical. This encoding makes it possible to obtain a sequence rather than a table.

			391 = 0b110000111 encodes all square matrices with the first four antidiagonals equal to ((1), (1, 1), (0, 0, 0), (0, 1, 1, 0)), for example, the 3 X 3 matrix:
  1 1 0
  1 0 1
  0 1 0
and the 4 X 4 matrix:
  1 1 0 0
  1 0 1 0
  0 1 0 0
  0 0 0 0
and all larger square matrices constructed in the same way. Since 391 is in the sequence, all these matrices are symmetrical.

Philippe Beaudoin, Table of n, a(n) for n = 0..10000

Cf. A231428, A261194.

b[n_] := Select[ Tuples[{0, 1}, n], # == Reverse@ # &]; FromDigits[#, 2]& /@ Join @@@ Tuples[ b/@ Range[7, 1, -1]] (* Giovanni Resta, Aug 12 2015 *)

a((2n+1)*2^(k-1)) = a(n*2^k) + a(2^(k-1)) for n >= 0 and k >= 1. - Eric Werley, Sep 13 2015

A261194 Encoded square binary matrices representing an idempotent relation.

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 16, 17, 18, 19, 20, 21, 23, 25, 27, 33, 37, 49, 53, 65, 67, 73, 75, 81, 83, 89, 91, 141, 144, 145, 148, 149, 153, 154, 155, 157, 159, 181, 209, 217, 219, 272, 273, 274, 275, 283, 291, 305, 307, 308, 309, 311, 337, 339, 347, 513, 517, 529

Offset: 0

Philippe Beaudoin, Aug 11 2015

nonn

We encode an n X n binary matrix reading it antidiagonal by antidiagonal, starting from the least significant bit. A given entry in the sequence therefore represents the infinite family of n X n matrices that can be obtained by adding zero antidiagonals. All of these matrices represent idempotent relations. This encoding makes it possible to obtain a sequence rather than a table.

			For example, 148 = 0b10010100 encodes all square matrices with the first four antidiagonals equal to ((0), (0, 1), (0, 1, 0), (0, 1, 0, 0)). For example the 3 X 3 matrix:
  0 1 0
  0 1 0
  0 1 0
and the 4 X 4 matrix:
  0 1 0 0
  0 1 0 0
  0 1 0 0
  0 0 0 0
and all larger square matrices constructed in the same way. Since 148 is in the sequence, all these matrices are idempotent.

Philippe Beaudoin, Table of n, a(n) for n = 0..6672

Cf. A121337, A231428, A261195.

def getBitIndex(i, j):
  return (i+j)*(i+j+1)//2 + j
def getBit(mat, i, j):
  return (mat >> getBitIndex(i, j)) & 1
def setBit(mat, i, j):
  return mat | (1 << getBitIndex(i, j))
def noBitLeft(mat, i, j):
  return mat >> getBitIndex(i, j) == 0
def squarematrix(mat):
  result = 0;
  i = 0
  while True:
    if noBitLeft(mat, i, 0):
      return result
    j = 0;
    while True:
      if noBitLeft(mat, 0, j):
        break
      k = 0
      while True:
        if noBitLeft(mat, i, k):
          break
        if getBit(mat, i, k) & getBit(mat, k, j):
          result = setBit(result, i, j)
          break
        k += 1
      j += 1
    i += 1
  return result
index = 0
mat = 0
while True:
  if mat == squarematrix(mat):
    print(index, mat)
    index += 1
  mat += 1

A261283 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n, using number 1 for the LSB.

Original entry on oeis.org

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

Offset: 0

M. F. Hasler, Aug 14 2015, following the original version A253315 by Philippe Beaudoin, Dec 30 2014

If the least significant bit is numbered 0, then a(2n) = a(2n+1) if one uses the "natural" definition reading "...set in n": see A253315 for that version. To avoid the duplication, we chose here to start numbering the bits with 1 for the LSB; equivalently, we can start numbering the bits with 0 but use the definition "...bits set in 2n". In any case, a(n) = A253315(2n) = A253315(2n+1).

Since the XOR operation is associative, one can define XOR of an arbitrary number of terms in a recursive way, there is no ambiguity about the order in which the operations are performed.

			a(7) = a(4+2+1) = a(2^2+2^1+2^0) = (2+1) XOR (1+1) XOR (0+1) = 3 XOR 3 = 0.
a(12) = a(8+4) = a(2^3+2^2) = (3+1) XOR (2+1) = 4+3 = 7.

Philippe Beaudoin, Table of n, a(n) for n = 0..8190
Oliver Nash, Yet another prisoner puzzle, coins on a chessboard problem.
Tilman Piesk, Illustration of the first 128 terms

Cf. A075926 (indices of 0's), A253315, A327041 (OR equivalent).

A261283[n_] := If[n == 0, 0, BitXor @@ PositionIndex[Reverse[IntegerDigits[n, 2]]][1]]; Array[A261283, 100, 0] (* Paolo Xausa, May 29 2024 *)

A261283(n,b=bittest(n,0))={for(i=1,#binary(n),bittest(n,i)&&b=bitxor(b,i+1));b}

A253315 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n.

Original entry on oeis.org

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

Offset: 0

Philippe Beaudoin, Dec 30 2014

The least significant bit is numbered 0.
For any x < 2^m, for any y < m, there exist x' < 2^m s.t. x' differs from x by a single bit and a(x') = y.
Because of the above property, sequence a is a solution to the "coins on a chessboard" problem which states: given an 8x8 chessboard filled with coins randomly flipped "head" or "tail" and a cell number (from 0 to 63) find a way to communicate the cell number by flipping a single coin.
See A261283(n) = a(2n) for the version where the terms are not duplicated, which is equivalent to number the bits starting with 1 for the LSB. - M. F. Hasler, Aug 14 2015

			a(12) = a(0b1100) = XOR(2, 3) = XOR(0b10, 0b11) = 1, where the prefix "0b" means that the number is written in binary.

Philippe Beaudoin, Table of n, a(n) for n = 0..4095
Oliver Nash, Yet another prisoner puzzle, coins on a chessboard problem.

import Data.Bits (xor)
a253315 :: Integer -> Integer
a253315 = f 0 0 where
   f _ y 0 = y
   f z y x = f (z + 1) (y `xor` b * z) x' where (x', b) = divMod x 2
-- Reinhard Zumkeller, Jan 18 2015

# requires Maple 12 or later
b:= proc(n) local t, L,i;
  L:= convert(n,base,2);
  t:= 0;
  for i from 1 to nops(L) do if L[i]=1 then
    t:= Bits:-Xor(t,i-1)
  fi od;
  t;
end proc:
seq(b(n),n=0..100); # Robert Israel, Dec 30 2014

a[n_] := BitXor @@ Flatten[Position[IntegerDigits[n, 2] // Reverse, 1] - 1]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 07 2015 *)

A253315(n, b=bittest(n, 1))={for(i=2, #binary(n), bittest(n, i)&&b=bitxor(b, i)); b} \\ M. F. Hasler, Aug 14 2015

def a(n):
    r = 0
    b = 0
    while n > 0:
        if (n & 1):
            r = r ^ b
        b = b + 1
        n = n >> 1
    return r
print([a(n) for n in range(20)])

a(n) = f(0,0,n) where f(z,y,x) = if x = 0 then y else f (z+1) (y XOR (z * (x mod 2))) floor(x/2). - Reinhard Zumkeller, Jan 18 2015

A253317 Indices in A261283 where records occur.

Original entry on oeis.org

0, 1, 2, 3, 8, 9, 10, 11, 128, 129, 130, 131, 136, 137, 138, 139, 32768, 32769, 32770, 32771, 32776, 32777, 32778, 32779, 32896, 32897, 32898, 32899, 32904, 32905, 32906, 32907, 2147483648, 2147483649, 2147483650, 2147483651, 2147483656, 2147483657

Offset: 1

Philippe Beaudoin, Dec 30 2014

From Gus Wiseman, Dec 29 2023: (Start)
These are numbers whose binary indices are all powers of 2, where a binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. For example, the terms together with their binary expansions and binary indices begin:
       0 ~ {}
       1 ~ {1}
      10 ~ {2}
      11 ~ {1,2}
    1000 ~ {4}
    1001 ~ {1,4}
    1010 ~ {2,4}
    1011 ~ {1,2,4}
10000000 ~ {8}
10000001 ~ {1,8}
10000010 ~ {2,8}
10000011 ~ {1,2,8}
10001000 ~ {4,8}
10001001 ~ {1,4,8}
10001010 ~ {2,4,8}
10001011 ~ {1,2,4,8}
For powers of 3 we have A368531.
(End)

Michael De Vlieger, Table of n, a(n) for n = 1..4096
Lorenzo Sauras-Altuzarra, Some arithmetical problems that are obtained by analyzing proofs and infinite graphs, arXiv:2002.03075 [math.NT], 2020.

Cf. A053644 (most significant bit).
A048793 lists binary indices, length A000120, sum A029931.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A058891, A062050, A072639, A326031, A326675, A326702, A367771, A367912, A368183, A368109, A368531.

a := proc(n) local k, A:
A := [seq(0,i=1..n)]: A[1]:=0:
for k from 1 to n-1 do
   A[k+1] := A[k-2^ilog2(k)+1]+2^(2^ilog2(k)-1): od:
return A[n]: end proc: # Lorenzo Sauras Altuzarra, Dec 18 2019
# second Maple program:
a:= n-> (l-> add(l[i+1]*2^(2^i-1), i=0..nops(l)-1))(Bits[Split](n-1)):
seq(a(n), n=1..38);  # Alois P. Heinz, Dec 13 2023

Nest[Append[#1, #1[[-#2]] + 2^(#2 - 1)] & @@ {#, 2^(IntegerLength[Length[#], 2] - 1)} &, {0, 1}, 36] (* Michael De Vlieger, May 08 2020 *)

a(n)={if(n<=1, 0, my(t=1<Andrew Howroyd, Dec 20 2019

a(1) = 0 and a(n) = a(n-A053644(n-1)) + 2^(A053644(n-1)-1). - Lorenzo Sauras Altuzarra, Dec 18 2019
a(n) = A358126(n-1) / 2. - Tilman Piesk, Dec 18 2022
a(2^n+1) = 2^(2^n-1) = A058891(n+1). - Gus Wiseman, Dec 29 2023
a(2^n) = A072639(n). - Gus Wiseman, Dec 29 2023
G.f.: 1/(1-x) * Sum_{k>=0} (2^(-1+2^k))*x^2^k/(1+x^2^k). - John Tyler Rascoe, May 22 2024

Corrected reference in name from A253315 to A261283. - Tilman Piesk, Dec 18 2022

A243112 a(n) is the smallest number that requires at least n adjacent bit swaps in order to pack all the ones to the right.

Original entry on oeis.org

0, 2, 4, 8, 12, 20, 24, 40, 48, 56, 88, 104, 112, 176, 208, 224, 240, 368, 432, 464, 480, 736, 864, 928, 960, 992, 1504, 1760, 1888, 1952, 1984, 3008, 3520, 3776, 3904, 3968, 4032, 6080, 7104, 7616, 7872, 8000, 8064, 12160, 14208, 15232, 15744, 16000, 16128

Offset: 0

Philippe Beaudoin, Aug 20 2014

a(n) = i if and only if A055941(i) == n and A055941(j) < n for all j < i.

Indices where records of A055941 occur.

Philippe Beaudoin, Table of n, a(n) for n = 0..132

Cf. A055941.

a055941(n) = {my(b=binary(n)); nb = 0; for (i=1, #b-1, if (b[i], nb += sum(j=i+1, #b, !b[j])); ); nb; }
lista(nn) = {vmax = 0; print1(vmax, ", "); for (n=1, nn, vnew = a055941(n); if (vnew > vmax, vmax = vnew; print1(n, ", ");););} \\ Michel Marcus, Aug 29 2014

A243112, a = [0], 0
for n in range(1, 2**30):
    s = bin(n)[2:]
    b = sum(s[i:].count('0') for i, d in enumerate(s, start=1) if d == '1')
    if b > a:
        A243112.append(n)
        a = b # Chai Wah Wu, Sep 07 2014

A241816 a(n) is the largest number smaller than n that can be obtained by swapping two adjacent bits in n, or n if no such number exists.

Original entry on oeis.org

0, 1, 1, 3, 2, 3, 5, 7, 4, 5, 9, 7, 10, 11, 13, 15, 8, 9, 17, 11, 18, 19, 21, 15, 20, 21, 25, 23, 26, 27, 29, 31, 16, 17, 33, 19, 34, 35, 37, 23, 36, 37, 41, 39, 42, 43, 45, 31, 40, 41, 49, 43, 50, 51, 53, 47, 52, 53, 57, 55, 58, 59, 61, 63, 32, 33, 65, 35, 66, 67, 69

Offset: 0

Philippe Beaudoin, Aug 19 2014

Equivalently, a(n) is obtained by swapping the first pair of adjacent bits equal to "10", if such a pair exists. [Here the first pair means the first pair from the right, the least significant end of binary expansion. Comment clarified by Antti Karttunen, Feb 20 2015.]
The fixed point of a(n) is equal to 2^k - 1, where k = A000120(n). In other words, applying a(n) repeatedly packs all the bits to the right.
a(n) is related to the "bubble sort" algorithm. If an array of elements from two classes is encoded in a binary number, a(n) is the first intermediate result that will be obtained when starting a bubble sort from n.

			If n = 5 = 101_2 then a(n) = 011_2 = 3.
If n = 8 = 1000_2 then a(8) = 0100_2 = 4.

Philippe Beaudoin, Table of n, a(n) for n = 0..9999

Cf. A055941, A030101, A030308, A007088, A246591, A246592, A246593, A246594.

Complement is A246590.

a241816 n = f (a030308_row n) [] where
   f [] _ = n
   f (0 : 1 : us) vs = foldr (\b y -> 2 * y + b) 0 $
                             reverse vs ++ 1 : 0 : us
   f (u : us) vs     = f us (u : vs)
-- Reinhard Zumkeller, Sep 03 2014

A241816[n_] := FromDigits[StringReverse[StringReplace[StringReverse[IntegerString[n, 2]], "01" -> "10", 1]], 2];
Array[A241816, 100, 0] (* Paolo Xausa, Mar 07 2025 *)

def bitswap(n):
  # Find first bit = 0.
  m = n
  i = 0
  while (m > 0):
    if m % 2 == 0:
      break
    m = m >> 1
    i = i + 1
  if m == 0:
     return n
  # Find first bit = 1 following that 0.
  while (m > 0):
    if m % 2 == 1:
      break
    m = m >> 1
    i = i + 1
  # Swap
  return n & ~(1 << i) | (1 << (i-1))

def A241816(n):
    s = bin(n)[2:]
    for i in range(len(s)-2, -1, -1):
        if s[i:i+2] == '10':
            return int(s[:i]+'01'+s[i+2:], 2)
    else:
        return n
# Chai Wah Wu, Sep 05 2014

;; With memoization-macro definec.
(definec (A241816 n) (cond ((zero? n) n) ((odd? n) (+ 1 (* 2 (A241816 (/ (- n 1) 2))))) ((zero? (modulo n 4)) (* 2 (A241816 (/ n 2)))) (else (- n 1))))
;; Antti Karttunen, Feb 21 2015

a(0) = 0; a(2n+1) = 1+2*a(n), a(4n) = 2*a(2n), a(4n+2) = 4n+1. - Antti Karttunen, Feb 21 2015

Definition clarified by Chai Wah Wu, Sep 05 2014

A243109 a(n) is the largest number smaller than n and having the same Hamming weight as n, or n if no such number exist.

Original entry on oeis.org

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

Offset: 0

Philippe Beaudoin, Aug 20 2014

To calculate a(n), some bits of n are rearranged. The lowest 1-bit which can move down is the 1 of the lowest 10 bit pair in n. This pair becomes 01 in a(n) and any 1's below there move up to immediately below so the decrease is as small as possible. If n has no 10 bit pair (n = 2^k-1) then nothing smaller is possible and a(n) = n. - Kevin Ryde, Mar 01 2021

			From _Kevin Ryde_, Mar 01 2021: (Start)
                           v    vv
     n = 1475 = binary 10111000011    lowest 10 of n
  a(n) = 1464 = binary 10110111000    becomes 01 and
                            ^^^       other 1's below
(End)

Philippe Beaudoin, Table of n, a(n) for n = 0..10000
Joerg Arndt, Matters Computational (The Fxtbook), section 1.24.1 Co-lexicographic (colex) order, function prev_colex_comb(), and second implementation in FXT library bitcombcolex.h (both 0 when no previous rather than a(n) = n).

Cf. A057168 (next of same weight), A066884 (array by weight), A241816 (lowest 10->01).

A243109[n_] := If[# == 0, n, # - 2^(IntegerExponent[#, 2] - IntegerExponent[n+1, 2] - 1)] & [BitAnd[n, n+1]];
Array[A243109, 100, 0] (* Paolo Xausa, Mar 07 2025 *)

a(n) = {my(hn = hammingweight(n)); forstep(k=n-1, 1, -1, if (hammingweight(k) == hn, return (k)); ); return (n); } \\ Michel Marcus, Aug 20 2014

a(n) = my(s=n+1,t=bitand(n,s)); if(t==0,n, t - 1<<(valuation(t,2)-valuation(s,2)-1)); \\ Kevin Ryde, Mar 01 2021

def A243109(n): return c if (c:=((~n&(b:=n-(a:=~n&n+1)))>>a.bit_length())^b) else n # Chai Wah Wu, Mar 06 2025

a(n) = t - 2^(A007814(t) - A007814(n+1) - 1) if t!=0, or a(n) = n if t=0, where t = A129760(n+1) is n with any trailing 1's cleared to 0's and A007814 is the 2-adic valuation. - Kevin Ryde, Mar 01 2021
For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3). - Chai Wah Wu, Mar 07 2025
If n is even, then a(n) = XOR(n,OR(a,a/2)) where a = AND(-n,n+1). - Chai Wah Wu, Mar 08 2025

A237120 Number of white areas in the graph of elementary cellular automaton with rule 150 at generation n.

Original entry on oeis.org

0, 0, 2, 2, 2, 2, 4, 4, 2, 2, 8, 8, 4, 4, 10, 10, 2, 2, 8, 8, 8, 8, 14, 14, 4, 4, 14, 14, 10, 10, 20, 20, 2, 2, 8, 8, 8, 8, 14, 14, 8, 8, 26, 26, 14, 14, 32, 32, 4, 4, 14, 14, 14, 14, 24, 24, 10, 10, 32, 32, 20, 20, 42, 42, 2, 2, 8, 8, 8, 8, 14, 14, 8, 8, 26, 26, 14, 14, 32, 32, 8, 8, 26, 26, 26, 26, 44, 44, 14, 14, 44, 44, 32, 32, 62, 62, 4, 4, 14, 14, 14, 14, 24, 24, 14, 14, 44

Offset: 0

Philippe Beaudoin, Feb 03 2014

nonn

a(n) is also the number of white regions on the line at generation n of rule 150.

Philippe Beaudoin, Table of n, a(n) for n = 0..999
Philippe Beaudoin, Python program for rule 30 (can be trivially modified for this sequence).
Eric Weisstein's World of Mathematics, Rule 150.

Cf. A071036 (rule 150), A237118 (rule 30), A237119 (rule 110).

A237119 Number of white areas in the graph of elementary cellular automaton with rule 110 at generation n.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15, 17, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 39, 43, 46, 50, 52, 55, 57, 59, 62, 65, 68, 71, 74, 78, 81, 85, 90, 95, 98

Offset: 0

Philippe Beaudoin, Feb 03 2014

nonn

Philippe Beaudoin, Table of n, a(n) for n = 0..999
Philippe Beaudoin, Python program to generate the sequence for rule 30 (can be trivially modified for this sequence).
Eric Weisstein's World of Mathematics, Rule 110.

Cf. A070887 (rule 110), A237118 (for rule 30), A237120 (for rule 150).

cp's OEIS Frontend

User: Philippe Beaudoin

A261195 Encoded symmetrical square binary matrices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A261194 Encoded square binary matrices representing an idempotent relation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A261283 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n, using number 1 for the LSB.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A253315 a(n) = bitwise XOR of all the bit numbers for the bits that are set in n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A253317 Indices in A261283 where records occur.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A243112 a(n) is the smallest number that requires at least n adjacent bit swaps in order to pack all the ones to the right.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

A241816 a(n) is the largest number smaller than n that can be obtained by swapping two adjacent bits in n, or n if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs